06.09.2025 13:15
nezhi 6 1600 Источник

Условия задачи

Есть бесконечная плоскость, вымощенная квадратными клетками

У каждой клетки есть две координаты в виде целых чисел

Координаты от минус бесконечности до плюс бесконечности

В клетке с координатами (0,0) находится муравей (в другой версии обезьяна)

Он может перемещаться вертикально или горизонтально только на 1 клетку, только на клетки, у которых сумма цифр координат не больше определённого числа N.

Например, у клетки с координатами (758, -219) сумма цифр координат 7+5+8+2+1+9=32

Случай, когда рассматривается количество клеток без взаимосвязи с тем, можно ли к ним пройти или нет, рассматривать бессмысленно, т.к. существует бесконечное число клеток с координатами вида (0, 1000……000) с различным количеством нулей.

Вопрос

Сколько клеток доступно муравью при заданном N?

Решение

Я впервые услышал об этой задаче с числом N = 24

Из интереса я принялся за её решение

Для решения я взял Эксель, что в дальнейшем оказало влияние на решение задачи. Там я сформирую четверть области с положительными координатами

В эксель в верхней строке и левом столбце я сделал формулы, которые показывают сумму цифр в строке/столбце

В каждую ячейку я прописал формулу, которая устанавливает в ячейку 1, если сумма из верхней строки и левого столбца для этой ячейки меньше 25, и устанавливает 0, если сумма больше 25.

Затем при помощи условного форматирования закрасил ячейки, в которых 0.

При этом образовалась интересная картина

Кусок области
Кусок области
Более крупный кусок области
Более крупный кусок области

Более крупный кусок области

Четверть плоскости
Четверть плоскости

Я заметил, что если у ячейки клетки выше неё и левее неё чёрные, то эта ячейка будет недоступна, даже если в этот момент клетка не закрашена. Я нашёл этому чудесное доказательство, но поля в моём файле слишком узки, чтобы записать его. Доказательство будет позже в нужный момент, т.к. оно проспойлерит алгоритм решения.

Я сделал новый лист в экселе и прописал в нём формулу, что если клетки выше и левее со значением 0, то эта клетка тоже будет 0

Сделал несколько итераций и таким образом закрасил все недоступные клетки.

После заполнения недоступных клеток
После заполнения недоступных клеток
После заполнения недоступных клеток
После заполнения недоступных клеток
Четверть плоскости
Четверть плоскости
Область целиком
Область целиком

Таким образом я получил лист с единицами в доступных клетках

Выделив клетки, я получил сумму доступных клеток в четверти плоскости.

Область 800*800
Область 800*800

Затем я стал рассчитывать количество клеток во всех четвертях плоскости.

Умножил количество на 4

При этом получается, что клетки, лежащие на осях координат (у которых одна из координат 0) задваиваются.

Поэтому нужно вычесть 4 раза сумму клеток по одной из осей

Первая строка
Первая строка

Также нужно учесть, что при этом вычитается центральная клетка, поэтому нужно прибавить 1

Итого формула

(Количество клеток в четверти) * 4 – (количество клеток на оси) * 4 + 1

Проще записать как

(Количество клеток в четверти - количество клеток на оси) * 4 + 1

Для N = 24 получается ( 199 620 – 799 ) * 4 + 1 = 795 285

Пример задваивания клеток на осях координат
Пример задваивания клеток на осях координат

 Решение задачи в общем виде

После решения для N = 24 подумал об общей функции количества доступных клеток от N

Доступная область выгляди как ромб, вершины которого находятся на осях координат.

В общем виде число доступных клеток растёт как квадрат числа до достижения отметки, на которой переходит на следующий уровень.

Например, при росте от 1 до 8 максимальная координата и растёт от 1 до 8.

Однако, при достижении 9 становится доступна и клетка с координатой 10, т.к. сумма цифр её координат меньше 9, и далее вплоть до клетки с координатой 18.

Также и при переходе от 17 к 18. При 17 доступны клетки до 98. При 18 доступны клетки до 198.

Таким образом, при достижении очередного числа, делящегося на 9 без остатка становятся доступны клетки с полями, у которых координаты имеют другие порядки. От единиц к десяткам, от десятков к сотням, от сотен к тысячам и так далее.

Таким образом функция будет экспоненциальной

Для грубой оценки я использовал следующие предположения – фигура выглядит как ромб, вершины которого находятся на осях координат.

Площадь четверти ромба равна половине квадрата значения максимальной доступной координаты на оси.

Площадь всего ромба равна двум квадратам значения максимальной доступной координаты на оси.

 

 

Грубая оценка
Грубая оценка
График грубой оценки
График грубой оценки

 

В общем виде грубая формула

( (10 в степени (Целое от деления N на девять)) * (Остаток от деления N на девять + 2) ) в квадрате

В интернете я не нашёл удовлетворительного решения для этой задачи, поэтому попробовал разработать его сам.

Единственная ссылка, в которой рассчитано до 38 https://math.stackexchange.com/questions/256563/determining-if-data-can-be-fit-by-a-continuous-piecewise-integer-valued-polynomi

Написание кода для решения

Теперь, зная принцип решения, я решил написать скрипт на Groovy (этот язык - надстройка на Java с более удобным синтаксисом и дополнительными удобствами), т.к. периодически его использую.

Для переменных, которые хранят число доступных клеток на оси, число доступных клеток в четверти плоскости и итоговое число доступных клеток, я использую класс BigInteger, который может хранить целые числа без ограничения по размеру.

1-я итерация

Грубое решение в лоб

Я написал скрипт, который формирует большой двумерный массив, который содержит данные по клеткам в одной четверти плоскости

Точнее не двумерный массив, а список, содержащий списки.

Идёт заполнение по строкам.

Первая строка (строка с одной нулевой координатой) рассчитывается по правилам, пока не дойдёт до первой недоступной клетки.

Если клетка доступна, записывается значение 1, если недоступна – 0

Так же значение доступных клеток в четверти увеличивается на соответствующее число

Запоминается количество доступных ячеек в первой строке для окончательного расчёта по формуле. Также это значение используется как максимальная координата, до которой ведутся расчёты.

В следующих строках доступность первой ячейки рассчитывается по сумме цифр координат

Доступность остальных ячеек строки рассчитывается так: если клетки левее и выше недоступны, то и эта клетка недоступна, иначе рассчитывается доступность клетки по сумме цифр координат

Также значение доступных клеток в четверти увеличивается на соответствующее число

После прохода всех рядов рассчитывается итоговое количество клеток, используя число доступных клеток в четверти плоскости и число доступных клеток на оси координат.

Таким образом удаётся рассчитать результат для не очень большого числа N, т.к. для массива требуется много памяти, и скрипт завершается с ошибкой о нехватке памяти. (сейчас у меня компьютер с большим количеством памяти и ошибки не дождался)

Рассчитал до N=38. Дальше скорость значительно падает.

Алгоритм требует O(e^N) памяти и O(e^N) времени

2-я итерация

Решение проблемы с нехваткой памяти

Немного поразмыслив, я понял, что мне нужен большой двумерный массив, достаточно два одномерных массива – один массив для рассчитываемой строки и один массив для предыдущей строки, т.к. для расчёта доступности клетки нужна только предыдущая строка

Алгоритм работает без вылетов, но очень быстро падает скорость, т.к. количество доступных клеток растёт экспоненциально.

При определённых значениях N и данному алгоритму перестанет хватать памяти т.к. количество клеток в одной строке растёт экспоненциально, но т.к. алгоритм довольно медленный этого можно и не дождаться в разумное время.

Алгоритм всё ещё требует O(e^N) памяти и O(e^N) времени

Рассчитал также до N=38. Дальше скорость значительно падает.

Скрипт для первой итерации не сохранился.

Для его эмуляции можно использовать скрипт для второй итерации, в котором списки для посчитанных строк не удалять, а сохранять в список строк

Скрипт на Groovy для второй итерации

Integer max_sum = 0
while (true) {
    BigInteger first_row_cells = 0
    BigInteger quarter_cells = 0
    def sum_of_digits = []
    def prev_row = []
    def current_row = []
    Boolean end_is_found = false
    //calculate first row
    BigInteger row_number = 0
    BigInteger column_number = 0
    while (!end_is_found) {
        sum_of_digits[column_number] = calculate_sum_of_digits(column_number)
        if (sum_of_digits[column_number] > max_sum) {
            prev_row[column_number] = 0
            first_row_cells = column_number
            end_is_found = true
        } else {
            prev_row[column_number] = 1
        }
        column_number += 1
    }
    quarter_cells = first_row_cells
    //calculate other rows
    println(first_row_cells)
    Integer prev_cell = 0
    while (row_number < first_row_cells) {
        row_number += 1
        if (row_number%1000==0)
            println(row_number)
        row_sum_of_digits = sum_of_digits[row_number]
        column_number = 0
        while (column_number < first_row_cells) {
            if (column_number == 0) {
                if (row_sum_of_digits > max_sum)
                    current_row[column_number] = 0
                else
                    current_row[column_number] = 1
            } else {
                column_sum_of_digits = sum_of_digits[column_number]
                sum_coordinates_digits = row_sum_of_digits + column_sum_of_digits
                if ((prev_cell == 0) && (prev_row[column_number] == 0)) {
                    current_row[column_number] = 0
                } else {
                    if (sum_coordinates_digits > max_sum)
                        current_row[column_number] = 0
                    else
                        current_row[column_number] = 1
                }
            }
            quarter_cells += current_row[column_number]
            prev_cell =  current_row[column_number]
            column_number += 1
        }
        prev_row = current_row
        current_row = []
    }
    BigInteger all_cells = (quarter_cells - first_row_cells) * 4 + 1
    BigInteger calculated_cells = first_row_cells * first_row_cells
    println('max sum of digits: ' + max_sum + ' available cells: ' + all_cells)
    println('calculated_cells: ' + calculated_cells)
    println('ratio: ' + (calculated_cells / all_cells))
    max_sum += 1
}

Integer calculate_sum_of_digits(BigInteger coordinate) {
    Integer sum = 0
    while (coordinate > 0) {
        sum += coordinate % 10
        coordinate = coordinate / 10
    }
    return sum
}

3-я итерация

Важные теоритические вводные

Ускорение алгоритма в 10 000 раз.

Разглядывая иногда файл Эксель с закрашенными клетками, я заметил, что узор повторяется по диагонали, параллельной стороне ромба. Это неудивительно, т.к. у клеток по диагонали обычно одинаковая сумма цифр координат.

Дальше я заметил, что можно выделить одинаковые участки размерами 100*100 клеток.

Это объясняется тем, что для участков 100*100 клеток, начинающихся, например, с координат (1200, 1300) и с координат (1100, 1400) начальная сумма цифр равна 7 и эти первые цифры не меняются на протяжении 100 клеток по обеим координатам.

Введём понятие – «число доступности для области».

Будем использовать области 100*100 клеток.

Для примера возьмём начальное число N=25

У области, начинающейся с (0,0), в этом случае число доступности будет 25, в этой области будут доступны клетки с суммой цифр в координатах, которые представляют единицы и десятки, не больше 25

У области, начинающейся с (800, 300), число доступности будет 25 - ( 8 + 3 ) = 14. В этой области будут доступны клетки с суммой цифр в координатах, которые представляют единицы и десятки, не больше 14

И так далее.

Таким образом, можно рассчитать число доступных клеток в квадратах 100*100 у которых число доступности меняется от 0 и до 35 и использовать эти рассчитанные значения и считать квадратами 100*100 вместо отдельных клеток.

При достижении 36 становятся доступны все клетки, т.к. максимальная сумма цифр координат в этой области у клетки (99,99) равна 36

Если число доступности отрицательное, то в такой области доступно 0 клеток.

Таким образом для квадратов 100*100, у которых число доступности 36 и больше, используется значение 10000 доступных клеток.

Введём понятие «проходимость области»

Область проходима, если на дальних краях этой области, есть доступные клетки и наш муравей может перейти в следующие области.

Наши области будут проходимы с числом доступности 18 и более.

При числе доступности 18 и более клетки (99, 0) и (0, 99) доступны и через них есть доступ к следующим областям

При числе доступности 17 и менее клетки на краю области (99, xx) и (xx, 99) недоступны, т.к. сумма цифр единиц и десятков координат больше 17 (9+9+х1+х2), и соответственно нет доступа к следующим областям

Таким образом в нашем алгоритме производится расчёт количества клеток с учётом проходимости соседних областей. Если области выше и левее непроходимы, то обрабатываемая область недоступна и количество доступных клеток в этой области не учитывается.

Алгоритм для расчёта доступных клеток по оси координат вывел эмпирически, глядя на число доступных клеток по одной из очей при работе предыдущей итерации

Алгоритм: Прибавляем к нашему числу 1. Единица добавляется, т.к. учитывается клетка с координатами (0,0) Спереди записываем остаток от деления на 9. Берём целую часть от деления на 9 и записываем столько девяток.

Например, для 24: (24+1)/9 = 2 остаток  7. Получаем 799 – 7 впереди и две девятки.

Хотя «ускорение алгоритма в 10 000 раз» звучит многообещающе, это даёт продвижение в расчётах для N лишь на 18, т.к. при этом максимальная координата два раза увеличивается на порядок, т.е. в 100 раз, а квадрат максимальной координаты (т.е. обрабатываемая площадь) в 10000 раз, что и сводит на нет всю оптимизацию.

Алгоритм до сих пор требует O(e^N) памяти и O(e^N) времени

4-я итерация

Ускорение алгоритма в бесконечность раз.

Развивая теорию разбития на одинаковые участки дальше, я разработал следующий алгоритм.

Он работает гораздо быстрее и требует гораздо меньше памяти.

Алгоритм работает с блоками размером (10^x)*(10^x)

Логика в том, что для расчета доступных клеток в областях (10^x)*(10^x) можно использовать 10*10 блоков (10^(x-1))*(10^(x-1)), потому что в этих блоках будут меняться только цифры младших разрядов и цифры в старших разрядах будут влиять только на число доступности для этих блоков. Для расчёта в более крупных блоках достаточно знать число доступных клеток и проходимость в меньших блоках.

Сначала в алгоритм задают число доступных клеток в областях 10*10 для чисел доступности от 0 до 18. Проходимы области с числом доступности 9 и больше. При числе доступности 18 и больше в области доступны все клетки.

При числе доступности меньше определённого значения данная область непроходима.

Соответственно, число доступных клеток в области для данных чисел доступности равняется числу доступных клеток в четверти плоскости.

Поэтому для этих чисел можно рассчитать и вывести итоговое число доступных клеток по всей плоскости.

Для этого требуется рассчитать количество доступных клеток, находящихся на одной из осей в четверти плоскости

 С использованием данных по областям 10*10 рассчитывается число доступных клеток в областях 100*100 для чисел доступности от 9 до 36. При числе доступности 18 в области доступны все клетки. Число доступных клеток в областях 100*100 для чисел доступности от 0 до 8 равно числу доступных клеток для областей 10*10 с таким же числом доступности, т.к. с этим числом доступности муравей не выберется из квадрата 10*10. Так что эти числа просто копируются в следующий набор данных. Проходимы области с числом доступности 18 и больше.

 Затем с использованием данных по областям 100*100 рассчитывается число доступных клеток в областях 1000*1000 для чисел доступности от 18 до 54. Число доступных клеток в областях 1000*1000 для чисел доступности от 0 до 17 равно числу доступных клеток для областей 100*100 с таким же числом доступности, т.к. с этим числом доступности муравей не выберется из квадрата 100*100. Так что эти числа просто копируются в следующий набор данных. Проходимы области с числом доступности 27 и больше.

Таким образом для области размером (10^x)*(10^x):

с использованием данных по областям (10^(x-1))*(10^(x-1)) рассчитывается число доступных клеток в областях (10^x)*(10^x) для чисел доступности от 9(x-1) до 18x. Число доступных клеток в областях (10^x)*(10^x) для чисел доступности от 0 до (9(x-1)-1) равно числу доступных клеток для областей (10^(x-1))*(10^(x-1)) с таким же числом доступности, т.к. с этим числом доступности муравей не выберется из квадрата (10^(x-1))*(10^(x-1)). Так что эти числа просто копируются в следующий набор данных. Проходимы области с числом доступности 9x и больше.

Итоговый алгоритм такой:

1.       Данные для областей 10*10 с числом доступности 0-18 рассчитываем заранее и вносим в набор данных

2.       Рассчитываем данные для областей со стороной в 10 раз больше на основании рассчитанных ранее данных

3.       Для областей, у которых отсутствует проходимость рассчитываем итоговое число доступных клеток и выводим

4.       Данные сохраняем как исходный набор

5.       Переходим к пункту 2.

 Недостаток алгоритма в том, что он опирается на предыдущие расчёты и необходимо заново рассчитывать значения для всех N.

Алгоритм можно доработать, чтобы сохранялись в независимую область памяти результаты предыдущих расчетов, тогда при запуске расчёта следующих значений будут использоваться рассчитанные ранее данные и это сэкономит время при расчёте следующих значений.

Алгоритм требует O(не знаю сколько) времени и памяти. Скрипт я написал как проверку концепции, и скрипт показал себя довольно хорошо. Мне хватило его производительности, и у меня нет большого желания оптимизировать его и/или приводить к более приличному виду. Скрипты итераций 1 и 2 доходили до N=38 в течение получаса, при этом работали всё медленнее. Скрипт итерации 3 доходил до N=56. Скрипт итерации 4 доходит до N=700 за 4 минуты и до чисел из 150 цифр. Скорость скрипта падает при увеличении N, но следующие результаты не так полезны, и такой скорости мне достаточно для личной удовлетворённости алгоритмом.

 

Скрипт для 4-й итерации

def cells_per_unit = [0, 1]
def max_unit = 1
def previous_border_unit = 0
def border_unit = 1
BigInteger max_cells = 1
def startTimeMillis = System.currentTimeMillis()
for (generation in 1..<1000) {
    //println('generation ' + generation)
    def next_cells_per_unit = [0, 1]
    def max_number = 0
    def reached_max_cells = false
    while (!reached_max_cells) {
        max_number += 1
        BigInteger multiplier = 1
        BigInteger field_size = 0
        def first_digit = 1
        def field_size_found = false
        while (!field_size_found) {
            field_size += multiplier
            first_digit += 1
            if (first_digit == 10) {
                first_digit = 1
                multiplier = multiplier * 10
            }
            Integer current_sum_of_digits = field_size.toString().collect { it as int }.sum()
            if (current_sum_of_digits == max_number)
                field_size_found = true
        }
        BigInteger available_cells_zero_row = field_size
        BigInteger available_cells_quater = 0
        field_size = 10
        int[][] field = new int[field_size][field_size]
        BigInteger add_cells = 0
        for (i in 0..<field_size) {
            for (j in 0..<(field_size)) {
                add_cells = 0
                def unit_number = max_number - i - j
                unit_number = (unit_number >= 0) ? unit_number : 0
                if (i == 0) {
                    if (j != 0) {
                        if (field[0][j - 1] == 0) {
                            field[0][j] = 0
                            continue
                        }
                    }
                    if (unit_number < border_unit) {
                        field[0][j] = 0
                    } else {
                        field[0][j] = 1
                    }
                } else if (j == 0) {
                    if (field[i - 1][0] == 0) {
                        field[i][0] = 0
                        continue
                    }
                    field[i][0] = field[0][i]
                } else {
                    if ((field[i][j - 1] == 0) && (field[i - 1][j] == 0)) {
                        field[i][j] = 0
                        continue
                    }
                    if (unit_number < border_unit)
                        field[i][j] = 0
                    else
                        field[i][j] = 1
                }
                add_cells = (unit_number < max_unit) ? cells_per_unit[unit_number] : max_cells
                available_cells_quater += add_cells
            }
        }
        next_cells_per_unit[max_number] = available_cells_quater
        BigInteger available_cells = (available_cells_quater - available_cells_zero_row) * 4 + 1
        if ((max_number < border_unit) && (max_number >= previous_border_unit)) {
            //println('' + max_number + '\t' + available_cells_zero_row + '\t' + available_cells)
            //println('' + (max_number - 1) + '\t' + (System.currentTimeMillis() - startTimeMillis) + '\t' + available_cells + '\t' + Math.log10(available_cells.doubleValue()))
            println(available_cells)
        }
        if (available_cells_quater >= (max_cells * 100)) {
            reached_max_cells = true
            max_unit = max_number
        }
    }
    previous_border_unit = border_unit
    border_unit += 9
    max_cells *= 100
    cells_per_unit = next_cells_per_unit
}

 

Теперь пришло время для описания теоремы о том, что если клетки сверху и слева от рассматриваемой клетки недоступны, то и сама эта клетка недоступна. Я этим так называемым доказательством не доволен. Думаю, можно написать гораздо лучше.

Здесь тоже помогает разделение нашей области на области (10^x)*(10^x). В этом случае внутри такой области у нас есть координаты по осям из одной цифры, отличной от нуля, которые определяют какой меньший блок мы берём. Если блоки слева и сверху непроходимы, то и рассматриваемый блок также будет непроходим, т.к. число его доступности будет меньше на 1 соответствующих соседних блоков. Здесь очень помогает разбиение на меньшие блоки, т.к. при этом мы рассматриваем только координаты от 0 до 9 и координаты вниз и вправо всегда возрастают. Не возникает проблемы с тем, что координата 9 перейдёт в 10 и тогда сумма цифр координат превратится из 9 в 1. В случае же переходов от 9 к 10 следует рассматривать не эти соседние клетки, а блоки, в которые эти клетки входят.

 Анализ полученной последовательности

Десятичный алгоритм функции
Десятичный алгоритм функции

График логарифма числа доступных клеток выглядит как линия, колеблющаяся около прямой.

Здесь и далее я использую десятичный логарифм ради удобства, т.к. он показывает количество цифр в числе.

Более подробный график в начале кривой.
Более подробный график в начале кривой.

Заметен значительный скачок при достижении N числа, кратного 9, т.к. при этом достигаются клетки следующего порядка. Приятно было увидеть, что реальный график похож на ранее предсказанный.

Log/N
Log/N

График логарифма доступных клеток, делённого на N. График строится с N = 61, т.к. в начале график сильно выбивается. Заметно, что график колеблется около линии Log/N=0.222

Получается примерный график y = 10^(0.222*N)

Откуда же появился этот коэффициент 0.222? До него можно было бы додуматься раньше, но, только видя его перед собой, мне удалось прийти к его пониманию. Максимальная координата по одной из осей увеличивается в 10 раз при увеличении N на 9. Что нам даёт 10^(N/9). Количество же доступных клеток пропорционально квадрату этого числа, т.е. (10^(N/9))^2 =10^(N*2/9)= 10^(0.22(2)*N). При малых N велико влияние различных факторов, однако при больших N подавляющий вклад вносит как раз эта экспоненциальная составляющая. Прийти к такому пониманию помогло использование десятичного логарифма. Если бы я использовал натуральный логарифм, возможно не пришёл бы к такому выводу или это заняло бы больше времени.

Обратите внимание на периодические колебания функции. Это объясняется тем, что функция себя ведёт как квадрат от максимальной координаты, а максимальная координата имеет примерный вид ((N mod 9)+2)*(10^(N div 9))

 

Аппроксимация функции

Буду аппроксимировать десятичный логарифм функции.

Первая аппроксимация y = 0.22222*N

Разница между функциями
Разница между функциями

Видно, что разница колеблется в пределах 0.5

 

Вторая аппроксимация: y = 0.22222*N +(LOG10(ОСТАТ(N;9)+2)*2-0.22222*ОСТАТ(N;9))*0.85

Формула с логарифмом подобрана аналитически. Функция в промежутках между скачками растёт как квадрат, это выражение формирует разницу между квадратом и экспонентой. Коэффициент 0.85 был подобран методом проб

Разница между функциями
Разница между функциями

Разница колеблется в пределах 0.05, что в 10 раз меньше, чем раньше. Тут я немного недоволен результатом. Думаю, можно было бы улучшить, но и так потратил тут слишком много усилий.

 

Третья аппроксимация – выравниваем функцию методом подбора дополнительных элементов

y = 0.22222*N+(LOG10(ОСТАТ(N;9)+2)*2-0.22222*ОСТАТ(N;9))*0.85+50/N-N/5000-0.45

Разница между функциями
Разница между функциями

Разница между функцией и аппроксимацией колеблется в пределах (-0.02;0.02). Это эквивалентно погрешности 5%, если использовать функцию, а не десятичный логарифм функции.

В начале графика разница очень большая, поэтому я привожу график со значения 150, чтобы было видно колебание разницы между функциями.

 Заключение 

Я не был нацелен на разработку быстрого алгоритма, просто дорабатывал скрипт, получал новые значения для этой последовательности и смотрел на отображение задачи и как выглядит график. Эмпирически подбирал функцию для соответствия последовательности.

В итоге в голове сложилось видение решения задачи, разработан алгоритм и наконец написана статья.

Мои выводы:

Мне было интересно, и советую всем любителям математики, алгоритмов брать какие-нибудь задачи и пробовать приложить к ним усилия.

Для окончательного решения очень помогло созерцание полученной области. И со временем мозг начал замечать паттерны и выдал решение.

Итоговый рецепт решения: наблюдение за визуальным отображением задачи, время, заинтересованность и немного усилий, распределённых во времени.

Если кто знает, как добавить последовательность в OEIS, буду благодарен за информацию.

Спасибо всем, кто прочитал.

 

Приложение. Первые 900 чисел последовательности

Скрытый текст

1
5
13
25
41
61
85
113
145
505
1121
2025
3245
4805
6725
9021
11705
14785
47905
102485
181533
287881
424129
592597
795285
1033841
1309537
4216357
9006221
15961125
25353625
37441397
52462177
70629201
92127245
117109345
377329873
807129569
1432989909
2280903889
3375878405
4741454253
6399256189
8368584329
10666056729
34403566089
73684822789
131006415517
208844517173
309609633057
435601980333
588968645965
771663609761
985411627241
3181171588709
6819881667853
12137997006065
19371803180925
28753285946001
40505996973909
54841019267293
71953133111465
92017277680165
297249163014229
637713134959213
1135903535195329
1814425849305873
2695617298636413
3801162910017897
5151716422980001
6766535310712697
8663138836680729
27999240935045301
60103091474582617
107123178953569209
171228135013230785
254571641754976445
359256628051546673
487299604416525405
640595989603738513
820887261202976365
2654178966146876809
5700036783144450337
10164392750411499949
16255844202894993465
24182386767083345285
34148059809667125609
46349582010940030657
60973055833157077429
78190818531302346061
252898376619150128557
543318694643992083317
969251414992336757981
1550810460882765339901
2308118093302246914313
3260989166794496243045
4428612738002623505241
5829238336780531001701
7479874162952577073461
24199370912546895594501
52005222777213037743661
92806265342092607837589
148546309276330555785017
221175339357530280241801
312619667620272699730369
424751704175588655821393
559360027693305763855933
718120437371065477275709
2323849775786030170348165
4995333826844345797045849
8917038643677971771874577
14277193502577428908866725
21265067035504360698842049
30068134781793751958937045
40869200098836914846197849
53843532390143909566908697
69156086905874552950693609
223834801865880301981704793
481261799162470883859762269
859301186731805025867018725
1376213391164945357977748725
2050396490064090940314316929
2900116461414254203662156261
3943232164906450800731043049
5196921082201451846360774177
6677411894805841388428445945
21616241482998455782423216897
46485580319525959855226073821
83018679035598498287844643005
132989925765114140338173043693
198190193085283309145878769001
280401066095964210026416390873
381368500317587924189188723765
502776479837702893864548199901
646221252858771878587924177821
2092274395145881945473709845129
4500185683295101845304447877917
8038404652627647292258227747913
12879607506382250645846378812485
19198339922565393155626620220941
27168547741072070304346174483369
36961047535468030006929164911617
48740991271863681044424814109373
62665380039475812397150911746033
202918998746636190359729520224021
436515347067521321544927189331197
779850218669850604274817984615601
1249750461741519489705222713924033
1863247950764632726149226780685677
2637342379946315006322601064771033
3588757826936947375241829056308969
4733698255476318120343130707783709
6087607211568347851857667007698497
19714820579554859482887399119582105
42415773943584818553069512553633001
75788498951430349835986225592099897
121474745110288116173926726310616273
181138250679118451243533441650161369
256441903035621697850139836637784285
349024261080485610225182851434276121
460475934123476231639203660978371869
592316320832014379983731675233125025
1918428635124990005916830250867706105
4127925684644645913442952711227728153
7376753155114144970229848065924932593
11825271956429837875945384596338560293
17636164499573954304149202247786983181
24972230923359387373585101770858028485
33994120539266491349008180007475658133
44858045929687969741207714922866933369
57713528085431754345747527547677198321
186943644198210432209337570380721022073
402293850591934433663840213469357987493
718999354477144489813763905286783421189
1152739818626746537655900379181881371953
1719437200886579476650288066688176754401
2435042707313160836888010978135138346349
3315317207459173518050431079542951708237
4375609674318805820402496543777224835129
5630638308935789727135839777147755635437
18240128549023669225043855949498214179813
39255689342296516955304630492973215319313
70167259318761504581863267923004940061153
112509403487996171398388566207988680508845
167841756909272345020369925488645011528493
237728392803800255736696905821703067226905
323716533878763921733744921165899196197289
427315046722776164550644048500047367279825
549973169032292640694223839513616128906737
1781744979251860832613342868445136268363337
3834938859390607323480782665053789126666449
6855401477643840039572100847846988544211369
10993451205524148560719196957110439107338737
16401983081060735706896484421488052497318713
23234467600568220877395365492547796099894953
31642883757861202473948404011352598952444685
41775628825627626069039699076938780969148509
53775448371839359776136386095709277381460033
174228380297127884171946784757968861310864565
375030555111887630120314580053433710928835385
670470918691682309425658990906828853815462757
1075285768028332478643192383302182816250545149
1604474834367856184328784392154209204455548197
2273106892020514759132235887889120055980653865
3096118801901816205107018412841370300938561213
4088112103014138416465236998046503947749800093
5263151365196981167461126684975695340100862657
17053320342940750504848702570910730870818375937
36710359719433864696895854122166778819561900653
65635309502596277837970859190389844126091297213
105273904297630692137144525107424563062577926617
157098698503259185506562912956556894663085763853
222590158558091272945764773365277926580187021305
303217100989163892385214782013802337909282122881
400416875082218586792138085727774793053899868593
515575698996767890170334046760393996988657676869
1670634653028976424016132858279852649555582377969
3596586802648262817151613126046124510239468261201
6430906547935556012321688745374858152621900680237
10315528957345593602984605104029701424989246659581
15395110262300238379886450508865928570030460575685
21815186508088208724612257240443239113821466259197
29720267119659172675849578755497841031504908722741
39251902112983792702164477050938144745045902110337
50546762679288651882967217705513610446292346329801
163797148819459639832939573799491642339626097371953
352648873805279058239398756250527336732453544365637
630600610953596995538875503753319558638054647012433
1011595837495391406631829251883405031640795949151645
1509853350172721563782232029657082231339964860029693
2139687740658569842100977932237291044422855639813061
2915323403683602068827702812264788433169053409742777
3850705844539245818141693056420875395759763218787781
4959314151705093402189211926324300707214339516894913
16071513279642539632685520369566312317553507980784249
34603340151086624522229205000542905717100357398705257
61881082230502318370362755460839372096852981962645141
99275350015104629701391493474627661927722198753346629
148184545514444958754665438648219353847000949074837881
210017340949196112105858930329007561137989929598522149
286174515427940339280910495237259257746869047573642861
378030516403765213332488571976902830127337064348982217
486915122546011485268666119961550880719189435542889473
1578007201767308008743376352410022019756772096468306861
3397766415790755539273016033320563107914522400453345045
6076582373664202484217107124000087262668066695974194577
9749258741163668763434303342751084048047263932378655953
14553399109324449210316256828744558125571828939310790945
20627695284090497414693763499975910330316917096224704961
28110151888200572527255857578213065222880225308527506233
37136283038007998475827894289802622554186183566768258369
47837317832698295927420866414337086298232658281438886029
155039256861347749616457527336024521395909841364456806313
333847318488083771620123733199995287806775170370709220781
597087473578676202372571724376861780385148312216607410541
958025071750315989932675000509797112223819398020399847129
1430207089060786209115799205753786852950846240701162544025
2027294754847159938027248489724431105800022064089940204345
2762889864433434468870445205103636666783093790317000370265
3650358268405106303983067668188132407191007309551867533221
4702654125684015009207924918818299166065415649413184100705
15241782129453649653183642662516895654095198147531469752773
32821784439269151571291675213290145414451296663258023771745
58704965872922598412414009297801193263264475779421896037369
94197350217766695540811622705160926112216023272209509488169
140633249226305068260552342855077349381408952302683728638301
199358882913401820630685832071499267468164582081880112420101
271715374132782433252531706110716691259255529009826146465773
359021458500282113112981716470289694999536318019335287755065
462556260284922737517073798567224183545517923898558234104353
1499249697932022235700391083018183555961559694750307505331557
3228637784826019974141693594838274028619995920843309171590645
5775014792808863215904458855539170319657436278792062135430381
9267023710047988995223531582437551889482788848418390697605697
13836145576380477758403268740110935886958384199324220887166137
19615095253960940704126928436620255555401135495083446986841089
26736155210562519675011208841904197078691289997058714464146425
35329480672062017875960520462639088358920539783854378822589361
45521410445628792220755897936568507055528420032505552550622453
147550526167823717920723133757727912795785099333156005046556705
317763380129263936141079309168133941552525181131892665072974741
568404393324940017742139606922285894989739970363232583319579353
912150438746683905454476779620383781382517559376404973418681545
1361962837328389925939397704855103296587319020265543577767117473
1930930124481980642707211457480209143621159832494312923590300977
2632104677340817088543911230416744405841036599236286707993403045
3478336467867305066589068674773220762936336021872658739333357865
4482107300419518623681207416618388181959392084984966362817196749
14528540681323155006221982565648874217271345631394250669724898301
31289723718692792450874811336622359491861435501575505842349105249
55972397554006358462124915697555020663210660588779145667521395169
89826298686034448620529601601338548130318715017065375150769033733
134129648239643977912134893974801956884184122823796770920324262169
190173730650162119288607991102496736947655993774715433390931549089
259246864413796962357258153799670716990895962833151803438017070885
342618084780862819646422351988911493474320336813472763544568266745
441520867505095359135932830966762389617608002733101038675210162865
1431214744139871841159760770329169606144871256307051924451075830341
3082479549575020155705459246764099508913188269608476445452303526341
5514293687730803837477052652976540094985913990763371323840279084509
8849909515810514560701291350230538825336548720284525353687919403857
13215429719548633693158786695152446883425442326428748685083423012045
18738293830732949729201548870292695434330877855611270057583846226093
25545704552339127864011257491912964500754813719327173362103999538693
33763025252451649438176273373098747400630163330896832656823322370885
43512180901041254279553831744101498085191281237622951743334708317913
141051414893278901078067457910742493768063357423280523061526760127825
303799894458712669544450545836100727029602806292753291727936800308413
543492822326248146870739729448305592032631735246183463895859042813133
872290194308250259134265038984779649971779232325802471107123597263745
1302637042017253732703594233436863358767794279742064554117969928177465
1847114806423689216530584861021092191872490836877960874956548808199113
2518286752135696065738904553245665807251518554876470457036828153544165
3328540499282528901546545752409764882093314017248742465790995295594761
4289930840100672879867671248361534720211348353763889144491603256248037
13906863336456931077548427819879245214443741043774421044930662117096285
29953895102045925539757479571345422871204173634360040690871678162703453
53588930120690380623295184817321505287161592540534022698858308139405933
86012088381567178394030705581713456333993890955892606051572823894925369
128451977801549147789565803725887371670143442558838474273023945250658821
182151090553038258577586857314514183576791822307360544652489840464500629
248350609423457191319886328376798863425411018217507873715836754069348045
328274926283571670645697592232777598205692188109152978631509731310605837
423116183657267383134360149551895859186554886729743340329798372243626181
1371671657133906693860300374026992600574473850788293213653594757406107465
2954523660675960050226420037069642234280562938538863859228039512823270609
5285961538034687825869968038440912353449896518416687280226843742511059133
8484469705847217340564794101094473317719968662243667125779759166921300549
12671378422353311114000888652284477827113102349367806996524986517650989289
17969428095555562003323597356382977507107015266693502480342738025722270965
24501275185050839276405739946645790174261478023303524377289310526551225285
32387969372850659192463351515321799197510077713764782964069335522048388909
41747432559550797480595930750525478864183614789246162276319538860024217793
135341603108821687405125240372752840690184140033172216396634759138263913337
291528566367648163076196405755274908423302056004887114192471127515850607401
521592827938884437613813233070654710951939741635481289731335542808451363889
837235737458458069197822752068807893086002210731632529181949401116256863049
1250442813093674680617528029566499688568806529658771350249340736045973540337
1773342526637734177969868686382431536355039429565761968907157555559412586317
2418059306339717160543236496090806660379840594640765864453787816634989534349
3196563674402976642181594478823836827012789514525201132911925982072755352665
4120522523154662567055052107055707595349760200136332600890942571442812735173
13358702726846878368864287942847997499498850685888897546374021294060741427481
28775702613047708567095514660805361030223238094835063993270813917721943270137
51486062719494574723533150547224582389489419830206468888079238015856634773977
82645741386016824096182235114961049215979240470512057746809461123510713795653
123439061761749853803699517153122562631347218317629678855833953568829924096977
175064815222866710611611797231450139186808531385388913962172330401951862993761
238721792321824381892770579224738044563339861119325860759091944652536738060409
315594028145174792837422251180852030589503195822260622136548496354171176616481
406836057562316037966896800280133689120735711043437142998736608701396232736577
1318989547126385007821700118291142859928505302613370693544835829976332804376165
2841281482181962385944859944085419891057737523024146445682313685993472720701469
5083825009286683020102062891822682958700272910574876242918213189322228527730101
8160848432183757182965430576470412551655328740368251709369433467335793760671565
12189410419786216769065636801209003299893136049642460747946458078684873746015569
17288031859867734504456589696965835649501660916853194627674465276658173764814085
23575271033007029009357294144608818326400272215497880637043328068172738067377209
31168270335392431771285844674679424037571839536941163708317442732297007888294469
40181303629655167119886953843556299640937248253691317734474390419900649097560629
130273288569101366496825219155004717725184676475756431158942896134208276265851497
280633161413038599550770212190574993788657484106637588548158151652698140089427293
502142862611282431402459642521039323205264390770007813807925319589335828009143365
806093195139687837907713883181879484916190654870214616123514859066793166965207581
1204057307708623813179271660012939856596090765151543557347139286296830785617077941
1707755940066049536019656204004063726077227571409180615208869456850986175551144277
2328917056106673197809509446739224474060593827256884621381127441557893065616378081
3079132643825116209502954144601451079655746058099947650318953622070693503528629345
3969715545230687976021782136900817567400081073537840857027630839574297757343786521
12870627674906328692781381193400426914628440945051107487950193143722234947859885369
27726403123979801375282631551925949153763577493436102977325358879833010595928477625
49612743208399142840632433137576402381716928498253675570971694464040041766466890985
79645971538516648945295478152704914930403250263197611729269435160380484283395659741
118970570342792163329051821056318022640692257584693636434322971826975126103499068337
168745902469473253949477403550624790533410067876213769505983235230747926962840770281
230132377649686811488200894189011842133307738858007143528440562715528250298212355893
304277336737232548531160856119777623173905651304188441132451655316233373650361544113
392300935952808271414802981334419056166726945871119211856229092313571442056515881581
1271944755224932055518862219934929671319334035266654926010219187076159913718739892509
2740133822791495563030241225114374179858462087555959341171919342541064722821698524269
4903230980968260938736098670015891150219491393877054075316713141397030393539851727317
7871635079201592669877028691691342648794940314114471291467004629244926353936718214465
11758552636960389335561107057729717682890087242953451329893590174791442698710614314065
16678688993912695952349910504202871743490343494098186453732901187006619253084717287213
22746884424300937601668542583686880675039502637170161561608378505785241682306550103473
30076722186219734054675598761081760638484043445987038539820772009857449216596803749017
38779136298407435278822674536060290520182480784636500759196974215200169444261363669621
125734717688056277845740592474016038633395569623477616019814270859956755169473931327213
270874430262333766928675597124500610056945989195403744146935494534408087994116985331313
484717798119267796285245618094284329911511196300690557136909831829619882172666549812613
778185344286679199410904233640555372415309620200803555757908027492473712948853804527961
1162477488020698116556963191198492390060958616138304666483642558852707182366264821581685
1648945480145893941264008759035052424110611361567685036510167555236786178332050645556009
2248956887600152572215595225053106766430869724079255509949394654746220647425265920422925
2973758285852025529020320691938393779514006051376454685807035170096993373053321152604841
3834337899137083138634544702574904659244927561365361456111145056703743985758331319625865
12432408466817525534257483562719031980754693581554596948982010383525049986734143209782025
26784092252453132876001374059990250236647288969885828942993784421423721351234620307534313
47930041291556877027376814230947889283941511639569139439725130706284338009012088577954489
76950749634120113892349821702568961459460783798567340159631850084469662579167608448296093
114954609422377939388128708748816406310851867387336557046758241223456446170059038013405665
163065179450378391025446581710399952127558987397816952898373087996014096197965759776669229
222407913819460101393090900689811695842138239506502450901276076109661066319882048588452325
294096612872971543234103791258732247798774653601500726340266950582508863457302702565707353
379219866632428391761314718579628743087737328823676648404995326929622350168257925859116053
1229598819698147336506999556379334393226832195093407283818683959287552301744215728982838317
2649070856277517835430657272844426668536458999396788594353073394594203716871050483591589497
4740606737883618303789686701908381632573321425080287880905071056566411167731781297402352257
7611135890475140710292716920526615914387538753347377109042061563210175021779072794104051981
11370368013082173763043968184504208555358574921717767799074636423521514721374090987559778097
16129536777972024148233938029180627712622167890846054638014647239473946353263825686659647737
22000090047618577860729295944473261399342325990626490653960396487670250356627958972068060629
29092352473130553563605460332390647845153743667208326986936215770661979799231202695195833477
37514187133994267076803107808766985873807988370902534710124021528012980987825466234552927457
121639617541587448663491234063994807026182798775711721742566320197225879873343396510624925701
262067579155060894961458475930634604852938770794236089296855657508385236210193236054372072565
468989080730219329078937809738128257758854073303140292028392106019089996787108586798112110485
752988470543806725931242429271041508185998593718717651669162886379640950832696171902462649765
1124927137744855156207821237857967549212952909002103769036983025741881628510829351050244050629
1595819504848893810305979850924810305247749305892849054556989716993103961818552309593289132681
2176703721603946457083068176860000106131261135401174190151353898733750963408041603969186192853
2878509612699775650723785424611440253716985351478568333142625730589746615405969812297424854241
3711926510464539955455549017647069406002435389468795355175768145418877295454037223092016352569
12036098263172139466441049878039016408228136932066453076056356592732997490161733346508387450157
25931745483493791800185647010822399522758405646116077221162338474530361745499747539294970854429
46407682999911820156648903895993067475964276539812110068218831279185377360838320946149244603209
74511809713871907386665509162369670580548035353836636366587009508014623647223623178568811768505
111319627173600347990559319196084919727005877595128932839348578821828405196349618186721949003265
157921995235403882275750513340628441065152026393299740824264736792569718320553372030196823059553
215412362729091104151371149015064005428890013595451012491798641868591178163457846163464474017265
284873725104124381985289201223351057992652491409287060116524287707964887075047965618371441460569
367365568817742938345931846641215909568926511263878736415888897998847089752178166014402152019145
1191218348124396115129325530715853927473052235558255266807589438919797836621500269671249238071141
2566521202841242351282184562627715978931867275404130915927293067869124335763472598172170449827445
4593157498619301811071862415299735602427684712804354665444770759796098710489791812811526043058933
7374894312509232384679884578251397126876291111971913342539117303893036883759289609961711502880137
11018248605395563627960654759724995398189189929426291804317995994954083655233455498804235927106461
15631277878799477519780846173187687173630636897103713255114400492820678941630139197630188939284513
21322318808682692428176227723656903777670886385100420204020174846375872167424234635404113183442173
28198698738967080250247236134530269569688951924118170949957950632658931104771787449154069396707085
36365445687888967699095454226118728339259065401582104151102027174500453503718715666554868354597585
117920182886865560425836547303886465934815882372724848205853208592323799536846634310869364212736201
254067306764734578202287035782131576559239201091052406122262891788402369763756164666896441298531173
454698243439266564131123064223219246886505414390600012470469728004906035376394710478961640681698961
730090350605321213244094859821356977277642247628924126914751482190327959112539830064994352877083461
1090794916375009739728903257085568158842628060119547984637252100332804138345970030022154033880998701
1547517682030430295770503699321335087845780018642310125652161149396630720850337961770842831195107745
2110994209139217697932470177874162057710544965459397409094312238362174257272648323122121561927417617
2791862548948847128762858698181880305611471516207342247629263807441749382657326460090164864240581921
3600535748230217830305367180668546557728312236728194376732521404371463331890875717421630908992859689
11675417343663744646115005188883695301027238902414995467489158049201138233627444131708104837828464509
25155904044080328509183450768896009940025116779094812693306300388382220256698662145197023048007990625
45021723774255020855839208939387830917241702866321666351056303762355599177289410194694755284449502865
72290956724760685195895282717919810177469488163647400901522178137953618599478018066806456250599836509
108008968679730626380628715147821566952793981224529268579108540567182021594566903477948791707736635873
153236604082848047776810099154777756165170708254837454894323733512603384774343393658243707781480598701
209037868107925304490196033633363122402291325931505066543451002542990373407502780506398213106230597573
276467340597430196832415666262972184205557021969384805600139572553451114030438560494623543674053080201
356557572281144707665112900226569936205416734688639315062651743009086965283903195715032556407035046817
1156220788035571458548732877059995351360224333758693454193372769198711830615588753694515822846816542301
2491236166941396197589417723946155852380790762626166935122449822806126271173682143074699586635174862669
4458661381258720993109192532382908289238909481713094539317812102319347471874366034341499791660859971205
7159365551468642400445545810150970938361958862736068142299632492625618155699579414266471760632174539181
10696935477294077316613187528454487843326193306651712604923709915855331706413592496188175245181279388137
15176508557949755519482670612725084901579365865874030936016995221261052528603903661818812160988637567573
20703555060068555345372829401189713654692943876489336632367838830519035902965982767179281038032723879189
27382633736939662031334165919565399107980549585466640900403578244143791622686936224928497801609147828325
35316145550104015387090297587262258560678926348321001612834976603784184862214248734321155890509841507837
114522286328064323621274146156759464085697167386113016082905630104588932767692711965669271956094955449925
246757577122017853934455446346354336885780318863574516254701244808365598311015835855038925675992851402549
441638787485669088732024187939222511234184782675787288400391013788427188599320919128611736440935547691117
709161485330380217096528798926643357049790191877543118867876401683779126242358369791832923085465879008737
1059591907600558944248875818636045028627173882835033214356392725398756851007869412042312195404809955359517
1503351569557286780390778168296864768542576627300748605611969875236301484107272220370833825550571438168561
2050896852609515017183533245023353572189824864814011159531603277657764502803524438266800439593913317925573
2712595943742520533781058703791339108460929224261290752990014085957299155931578253066207060317510106046981
3498605573605519666180326778184219076034311655763651195695281148546745721967523102800771586555853643563029
11345328869211975493577315654701205543071900748824832125192174872953474063113726840583610940007900730127109
24445768889196128136301683627771121752207759905070321188128748040441453250345214784569630195325001093204581
43752942963427840228473295845301301803590941484688098851605517282861567136471914213377047888494166133104221
70257516764182666612614354684051679715765506817444097333535224666783447169793128723192988588768659860060605
104977112125295850122693592684912276631069433864332653825857439100341949180363392376773523868976981725023773
148944895512194932354236404798344924149448481692627724152414644976753276837203122158985465333097485821929997
203197668632548320058637803596779955258894338804103848100123147522639183838284940288351087186658525555789233
268763695851533012101466055104345172854688493609463516898197546683853475580906357189741005932922283667807613
346650510405861320762857807075254733987062988004482126239153329019029471022439374737064616290963379530282845
1124136752350163218854273422544592351916863278621930174361559588643539141712324622689037905153377581918532785
2422209261734171800710649322468370378680546228546293826450808605884996082657236634514865251092474746411305717
4335326763520106560601678008272530049584679150988998746624297813222391649082056743298132117546970453564958789
6961689983381825865621027321788085072341541632433796288092597670989228742863080891251960033226338712781470333
10402184124619558397068493787871015496437346266059761044498937577067731022514621193641069630237217271136624165
14759250071994810608191349966526543796991022001124675331689743651796665560215630122386830518072673254634135665
20135706229210256750624938090788788815478467611838750816772217898023523202661782643754006766789486399378558945
26633544200898675625456559004325666220527762151436952729217377283383509291900619232332293191159949694876975765
34352722256064411177404078837110043792457371401976536592568502103873347552081431315720678420271321811283089825
111402124128370796887700043478052682289946721570280754348631096826854820860723958721521856140467910530618107189
240044453403859830385029668998538123064824357072312297399208286164250370572536010722530720163472226839042643613
429643477688994194714213920650584075110704602199194848148526671237867009752085191824382223874607028966615419397
689934912846086308190511319608319830575708874409337528657639098497370935623767113427260588764900517674190203149
1030921804069607147225717127346441265105672703202369507838914722987163813951636554310816222136476744535909257757
1462762844184914915445750595908786761701504065818627151870070456539704401997913941457113625549477540997623414065
1995655796391045181893344632443296047135596791984095495486606331640365261232929669112689923870033359013326789205
2639718317791681375393287018261303846247379189738406314053860336334878058913249715727114677422491247224824950493
3404868551989821180926635102179023945942040565946062341640387904900929813834602891051926218167501957996681907593
11041739531162126615621021824023797194589921321888516260796852319691823202332415422105134111296200353388545390297
23792561017894006273243375184252546438843088881660843303136707351189616429257802344642567821398432701131269988393
42585709514468287474244011471193463857202726021240198666491187440367118838705973578634831066108529627704995502453
68386534308788975629434194094117178499295328768814513033596475859599606659990605366277992185563343872559081119897
102187005486306091618500982337453674234925817743743854009468978518776160080075101777304154475977499739619777761909
144994661958101427415904167518440307921059990154487569365880141990714377765003489132226364970970229617421021721869
197821073955626539141862032662492683160998536344095297603586719674547029553138955928031836637826053324113050171333
261670047229255826912607150613750093810745364288940841464790260850380110646381697543412585903408717967535865039749
337525803314938017576713494053330993343803964026182001607650475264553284018109970521082777712479770117931825817613
1094583241022029722835430467999233836892779227980917838493674599382422988336685778693255506803161435411069939503269
2358618975836542080250708582043501148049671882705763064635372687014468439334110645807157624336853478806166160226725
4221690774012263583632426949761552798174035889701707898274340257851409831082583800965138793110857442306107700433277
6779531788641124445332630130460440864457232803719969159811382652690307736345825142776461536107805468730938069246437
10130526024415866851585819946779325656302541582891082774730162478604472601811333728196364121656992834167517661614257
14374614418077186394417548216281100610442566205526718650096278698202709757626219137392040236161447905925212341645657
19612152759396793611261560326305736579408499270719471335919791810405186539821095586336620712065505412281358780413577
25942743943999123775897851071114069599496258327975517380714212221486861981772313364862554579085036461378892154307133
33464067755592891225500264397646184457378979684265152267816372177186909015187812233404226900321039843362674731640541
108523815405559897738927897330372248162154786462811657396573236220134404744465394063174255617974244657553479005591969
233850965804897846050537396872673895076563243584825926952465746973242582342214952127097090170466241297129373079955253
418575238328223127780298960012356083653973847718069146442083838359403720585508398350484238396011667700701900399780889
672191732844385315776991124110385774290024643570320187474890810987933206783168475536453686167935740850585584396155169
1004459511412215090333070380432537358928866310987750992493911955915434028161888634222407934199547768661359246403986329
1425293301475427979008517581613061246493055627524356994886051433225615176934461252177584938616448429474981583734415877
1944650421684419746551429749711709851178279023932457990131943728688822875592124208876515707633689595149802275662638593
2572415156928973312417499638323401617188600268020131751384442076009929955580276397159817598908013512314463333696900977
3318282879163712720499893658359756412170828050516405270409103955010587973727805571392123814202430725520828683885092285
10761283845956752520991164191370808607219670943381970645387587677787248295596640570560685690940620878434422558191468721
23189060288583091984248693148824274205527518960304409248152073601986518170937179478613493817265753471536485631532533749
41507163701182187752425325289329908745536145175743394520489733583621974610942680244851961360281379155759236272086514489
66657470877508402180007997229974057319636627645455400070116546584999142944115317495564112773896517990423627862930135681
99608142633648713531562021553375130820310780392231064016015365829467105071090113861227574369598784534047416629370400953
141342900531483764075360750799687953043321262160808741748305867101462605889081874848819331471781966398727900683777891413
192849829642933916976761770519640927092138741152559298516497827728830585369160036451863071755689016721946676844894416705
255109927824914859996542539660749343324202786850771323167562949447134537358223292719618254197450515659988230864051872097
329085628913288907626711116816083443793107035470349684364754799038607171368459327683862329493455564909835021687027826481
1067244220560394130835314961882729554577988304704381954398996177872329628697095341518613086789587226242595092927136274157
2299787244997320594246049412826936022721455170493103123887047716609546441041513323336807383443022337658540285232388925985
4116545595916250451563425297016864161572329776252660381033553582802766933212438239466018878506304950036052431425263260281
6610961725601262389019041650803510209641825866838387373357720636404653015383401967913684713868254000830167074751989316301
9879095289218377366170779084565725849354716233166017114195222238873476119135640346198671098731052076167220254621767181629
14018561160551281815222791825163180847242856288822897388301955465653189315093091753101941337181547643610124641388605751069
19127420421913267057536035450277427084659624055391805917221572304990776599098899421172887956722256627494086419778328329829
25303046162680707548523097016617917848099437721775123867824677075071852233563068332673720122445708877604264217068296543989
32640986608731067083672065435152701647616310766550036024083500610863713098263105177691515091835767453982675219685226289857
105857650188970193471038808732228575943017774161939070365657015037499045529657497002562798126345940093311480412814716794397
228113364635894045052574210496132895163437084092351458214384150163246366420412585524710890024675530138844945868791140636809
408320502715141285946511528486514347727439553442372396856679063786527073842044965561803073909994020306190408564719179459917
655750525913050908023638312801300018866106119145357668645953966713968168608969043556484526903744869951640788531751207397273
979935499012425861119749619964264000399705430078326839696649124284401466776295639498724855171681430822883506544736321505389
1390562897627844876690902875264627275811525757692984788402504042170472541457715423973067081636232443098035743523504953510121
1897365749417995494679776769699159974339099655723890838988872498320630385515113460195131676030328071375046925648874593832761
2510010271765518351195843396201266004429620140590381694537838886046720597937864527272733369602140814647166433704716060872981
3237983236912652413697329734853695502198045379940272249780051818124566966221533024417482174374002698189812750854738285476553
10501165808519985951575525501856382183596961646016809147933475285405903694289867603989412461331309730840926805574363073404965
22629266710296947837398669513869668580038119568947836212061068369306367665086262620043364900666192830296635794382260820690333
40506615844226649210388276662541579078787271123399665309313780377739402390294280151747291956907886447726688642153595565735649
65053248231451079345587490035109110939538043890858590242428726337900788424067562504402931310747251583515679517832446195934101
97215147898723987921865629453179290136476491518641048211596409231151950668074324909758870995387442367703876398188532529696173
137953826514781151013645658854506527453322931826917918135522513169858669401485175215652600707709681892268139863297371003652573
188235438947358022180003673393986535888085797146745862246580389045156324117288257803274391327086842735116466852771301054266673
249019650011813948660760023839123202867061261672144825375516981149042499070679578959498979960982144307597882280383689045409265
321248473444848330356700474558455829449181225843394279496112810142322250670282812189997664165647517417310056764773038240912741
1041856285784103006049255626115240481901195786334062375492124346809444136618308515454412908008712992174566271327009394927800217
2245148777663167746793455459310960630713118941256677575753739725281544286094559934128865082725741384603068256306381080662655045
4018884004519758092321246879067037190725076649656957799115077453130028667731129525640050387305457809107070715541557104752485277
6454370450405307276638142497885295788119038461494570561464452805603848840806013958883425169215729367417586440395178304423906345
9645500412192800363407729467239820835714671684340419021807498827762764815842774317428907011045882426152318052367931840844282649
13687717391866194426227230965212205384512487798854501100569440201427889323435192825181516773123825214779008713575374289678474265
18676937529069597647804977687679677580967215922900836100357596412149256288351215825448540176559373020820103911328845228237884077
24708446305676472266090889631659246241847366018825767593762335456997692246173348129401303387059688891529490494348031913679529929
31875792424796279196489311315931481422151782637438672010370809153580761889870302758973664425639286422613285487472280668225076921
103378788791903509381411220652628578211600466769749205689258747464256263789038396974863185161418278761517429468118364736171471213
222778337445573565583685902302919961228026903118332293650629160060166275698991590193110915777408433746395854088905236344575664985
398784271420526368336836118092836492896337883357570654809261768213308140392664661485297673244666144130940163478170142454483046417
640459487054014114365681631239681293183582568297434136224821367404987675687076588531666925444517581539862271695507762864021819013
957124158289579745157025140559473882320345725255576449242878638185477925504878109097463876295838127751968873245984146254614868365
1358253403910047788836973629746851232677773708879438449085986984064023913101652978962407229911211518338496016170924535357500343489
1853370392925581210691723647547816482914751899165597224317519992113434554514198460583350372054836546292437009663276281204141944281
2451936992282369738492538080890227378008683913564329612854757267229918093763739092366911797544210993535924238243935265331763284017
3163244127576251029318246357513355133756019681051066124271759646309262287436104706460626309934999220396165553722792920532427867493
10259040709956129366601937096301596559620887201526091130082471088100930697282580524748425828734137115357963133233145025098276791873
22108147540710925138937737995166548792714620586946424417301437961098638512785652217963158692388018190516706201729167618797479187461
39575097145537556073101952588077074187516971011648899889445499169636578815399766912428690016023997660441423910417472740891679467937
63559533257560961844922584658679067476651607608125081694414340833473877309499335689302172066999948573311039406138270605843111316613
94986717568463946130258135857923640673723024350967068079568499181735547933947600500782937438007890670877853483308238692326359577417
134797386869940826242553455000431105235455681515931463991861275566404961992752812200467280252833049719473349031557211079412940561713
183937157356431523099956645676555582379748464786865367358791847215035058117407259093293188422017440649449824497170870939875157322501
243345684654680201716764984449275801410061189255268564228948154140156082300544665974487851468394563008581651851663155898483421992345
313945794744054052338251332886709621640772239858788709144883323589562283749331472829164930177232499678095633240449326424241889591133
1018197903378325546284844830868510616674708297726280608276780007233362755185124985870601972559196456490642052744755899858351742765713
2194228033933591713137844907720432255623693427226819967392158830969779012596904104623185284680093015144897156381178182283284855551517
3927858474820273514546885975350303409718180617115035624859434603363763511804791500282907252727662247502131086051363320892118972551457
6308403401706757867522033715490830103125784532670948547886680394573802557360268095452835408707211360426851123368844056371347404767909
9427727867362412756671120084521602002354576967014573912994683465380629063059733311263676790799432072742307476939374428704432578115969
13379242329192848959162531703084385919082433114168319323224204395035407873558243202262950729098327208900166682309115024666574314029461
18256852220952768427142564212590825337447664081677141327793096229691469293849214439458514013989630271814730507877176320775069865710937
24153883244878765458686651838481491671112699340636452218448941888412086206731286478260206563417674438165105024033676167358815345788505
31162003715093021419203110405353252809518204659174912017707202867788692797588845758045119636619113492865876676956699159002572322787945
101066281244607088851673555440554003744496313747337157519607189066872530715084200947519373157604554061681140554074475438300168603564349
217800910137470399136238238729936267653864775514664448507097785145596564797138848593758727099903131102726824234485740373415273183705661
389886383492395317163022648725910780147557076579275417045119620322486343805523101274427691181345653700335428296266311958939151063312417
626190487207124000538093601350365511395553296489790621377247376289234720497762394329499660270507819907970594262498136916086855384911749
935835009589206342559874886314894299419473630590992556799487163371996344764496832864066093334964000620469949713874185897821690384328481
1328096053531313802043238214367620232926321103051783981927553792536031089679774982375008842190405612554205695699424529146122541167706165
1812299885274548400285558877326935630565577695375847506181329916559939718969412345015253821686069115787262071143634288973329027367315525
2397716369811532603412228961530417992272257383879026804994395160511557593429761620024504021710389255921424873126301498214728783472831105
3093452107930249411794778515329383078053235084674008683340633388788432942472664826939702972953373529883718871317962056296247750797415709
10032925610347444257549853630741870870941388092930779490751329529566932548718493492786396319994770346580715238848955457665076594340457917
21621445631732121196540222831368667370483443160081681254285257433868183198220916865661056388561611476368108064954301352127944524022002109
38705019157324116746112717160818496179434509274725518139143221106890982590629218473471186216073376485150529479371839681735685135931003229
62164195555473595835371963384432265786972115198279315704953054763593206482165297395027619807690139184290621965296974438931997709911679605
92904816600597422048752429075137833973608357428401038569803867256320907170057059112227544722770901176504697991075402268901549125100098313
131848131528625024112800438842168834943636709454834737713226748199537814701423478670003387751518263496717854703675940666399447460784138997
179920468906551761494776494015766004888391774763501549831551030469199004683153197775203564794026649069025411656176869083609964871466674833
238042668608007907886747224490800384188710469596056925941995487856583347953659117799796088207108622677989672002214555453166491603020053805
307119483631604057060191883373620008523367142785201974457502199067695584988000166450745919029461588377493386139353876989610334905459444685
996081225741835460354038580548130661672990218916868069348122075001822653712245088141970457668285443936300966812778172581253280583202714273
2146621699079212719488036847430522757197623977019579692011950675148227275159431934966671523405212552452942110089726609995224079547935077857
3842750036420029137658452425393711591968362429552312441249954378136576656921867994317185649296674879875290616935720887022892990182044291873
6171911184104435891206656133850742248924126379363751491619759577968579835199674477364499079261870691692938854130480109301430833382877578165
9224068618373679709792418336023422435321961800452437295832126365163966068612978567950206994123862890816018341175967160012918633016317767285
13090724032552191699851636341621596540309611443114270503366776701969601040063861971188738126159574339771770759230125587438597051834959282533
17863893015170211934193827094205168038510590111152836536137318037916337274851788712460698553662473991028216990536108926278799092387420694937
23635056881108863384087894196129258480860177336289381948687508745588205036150415117207238139279509981673324916321810235254190562198134093889
30494111457434933105895430432023196447879026536755487661648729006231526337810669298269865738465164879889192291271033510242690828402067355865
98902317692157061619164941243895561613072922523196987317074606348126128947126379734017044892694826580027010475113715898384920735841705868861
213142841895549846628066203758076749203026944614414929313122932040710473987557712338625496475882639180344192996487348664753406401860649511773
381558663825030634601584984035111847264323555325210435239876280491832165865202389270964283634494462764011056915740084786101094463832588695701
612834528146284810418446629674453844772721915594319452697858660421212087333550959268578390898714670505147300002425560785246154836938244696157
915905969006940484134456436123788852099931933226420860135699960712618069210209724055847564119234866813711707953578313729996815170174963373809
1299862077486269344319107531618236108200973281147127901162462555290538192293265637298510664933198757665884266498321655949509313189224649107405
1773843898508370891941560541064697642333908814969933921767706824399502104181542694265423842225864243019397961418093118808742296556017611217057
2346940457121023865641975925554515343275886467413207544544136861378476097093367202722029769908264218776821313024372100957838790335968454232185
3028084477521255400338954131302734817747420690853256093201734236782920987822190182507716510030714809573822461729348975721460681793703592989205
9821130602171060814308585833546429244302948172919763916124667636576396092057803931767303472686394435044428902928555172379372603658978131032373
21165532232082378974307884614723565432339531574213839036847115864386825939278409300527003084165796000584984566130217840565252374365140796737637
37889912142003914682751373108425485259350439366703435942496528199880615192442216893583347504105775414175265148805770368349652531606002866511633
60856890508752811046563032336259818787616575384962152486400538717494219549213399309057177829680280309565370667585918272220737519437107393961265
90954060887219973407455366628217922642960520435730868231318641671531612879766389861770098713533258770384469880404505835936157599332605882831213
129084344959460119235153619342357118533758091256349242441243036222210633625987587810566922881102199763341019828103567759382210887546829511408333
176155913210323726139347022438634329654322096018898852734079799592292262375846115143096956041978561793587473892951685154211661707238492292093733
233071869928136429608477239879293888375970590256595364632079666426121480950340133395828943274966799686902997626127558823695939364035644668087197
300719907229851115199260353621180206633119627578442637745805633487825807989311177157883939769178292452610994654339900947710854507017820974285753
975345779492129382610657618554513356649312688334422002426129331694668283670066272267667068777452776671058085811409096114219842815121738396454045
2101985166212729414868647072657946981181491171751975153230088246104736456733638552863705449934722720332485596132895877506454409120639421064407093
3762944243905849418081670386582252466599606373366481236905903867586518790138983718363445254467369534919681913947902985310426839897661160777741329
6043911271379810475807655354429435716724029353319050212948571582741527122595143969272966101750263633278159493673577150285951855738533869611822701
9033061368400606938872199183855024707447049780855991627259413547522519322565134891391998768947545441862203377479963399321595370222925214291271877
12820099611145015238264998527165492203841450291754763356718444009027626752478734370975785546776232374172939461478729046459390624765448717848073889
17495261012807944071760530735392514806492199057519185918703513018258581191966016408717335682526374284255239745640884648229198534953657503105542185
23148287073780713905503243522220242840642692447921057297793198711859089845253962275457986980473222396809113226743113089469590123882527205554975929
29867399211309059519603123009625340668123366466047249408785322826299114467868235830652631737824014782937614513089368745272709405658656221464154529
96871648103825893341002656721970937226627494336041124454755274179214647715204020345125187673555441009948084785155545281222993423373999766667661313
208771382246995907631169134785602058802499475532960532076253267737367692844560915390181105715470025600559617799709566761617362661700360066316678081
373742713345681644528968720775159269973637223516321545624588331252093885143564930768131033942407498931877976870473508984762242210152837309166341805
600298220177924139133858746186530017509492191800736775787780817749901474887929317857771399540126110357272608537176459418104453822447214273300465429
897198128126307301548180053212717873921445145605634223057833669585133067854427557291448647071439139553345192024663349168803865316849530636442699509
1273355363458425381675317694898766358470661623754868209279597270306198721108323930290386665881175563645856708498139248635592617383579876104712589373
1737736324835930832018229846457926284237612688312032469412698366532446665186305273795171338711398700315657997241452687151764719088151092617766328501
2299259325309855118504138994201222568738665553637096015372199453464828080303708122305967162989631489757086550793631170563827708285162032731169475653
2966692720158500185126453006070889069420264141381630293316829113585056742714651165342302198228051916787801394654944675169364713755768849177150446253
9622205389470586587282082612629748323338012662667187355064111308300764787642366038851490819050125307270148648686928448432064990191137628112790633621
20737292552562353341071370114775937902308461137622705173525609769350714212378551806835716056413596299541974261090701718002785757222144398920835636925
37124221596237181711964329302985663245827955841694156451650515515686769261593932658303753918808664453064659816338214386055556301124543970399726390445
59628734916758128704849502654341024810683816060960166134979427768506818925474468689362310073434690057527376372091541826187292998656406274119392269845
89121236455987370468842476424273527020988682231628109910117125413656872696004010078432224769024929515249323697256461855190491689265207461161523123997
126487369934410230772008261963646927042545652737256239325122715336773859239682987374467577843747541380800340075349409856699231241863866674283183351857
172618171626108901732456874193557546244735184977332523563179329100991430325895209247613869650734111821081602327731003650854197696803875855219591891749
228399991517640683947042799996665382823501817243581322207135263762192224667989295884306014824220227762454322591325809481764629739039152439740186804973
294704382858484538275881287031879292610597102729891136575126283657406680383194657884586854755844053924327043703502498437245504223382407586646589352753
955853541546516498618630760198619221618764295136281683019332098114842517718221053800712642192307313633287800812157818052638938962198248582326315651457
2060021987551735992611062403551671773029732427451702574726186447726426570904334699295954230949746130110651287548062169312424330436185893824148673156553
3687912418132488026682173172196072789628803050393930315311527255072730344527926047375120039924429215132864037852859339334072688562525488881254615958325
5923558098956706522010441476864324698031933171962730093464999157730543816833530467383709272322601165327222580936563445440636217013671050657496221578189
8853448223425462975609235155948998335779050612006057716476276429648772670225195647578787002371402032489278357920827702619156946374595788789171664513165
12565592855642569378567313316821046986397535561643746894750445166819493520191499992147679730080253531717526074366729936415043787290328800183148639329933
17148545604407393429547130536375214240437467064102127471369177428193614052102411403393462016493224522543215476233888066029634482905900419236931287856965
22690403267374489504947118693650764894836782003328313831383625340617106469719789524927377722813204725040039762343186255674457725012143225403509718907557
29277802296767490181573528910901477572390628417393275394367457271487526139689593831166190393795569486980428348500656833368302490984408995892402744074485
94961127881164287720217542480311750755641746533341625493623342210122208700280716653670213812147903666140559061875022376059906884862831738413662449976593
204658297505475269836233873586339473963009036633248940315845417604697894433929682847464150848855009689053380278981522849066325186712599968330907739811357
366388177564635791188823035599956600800207949331550424470386663299099882947083194637667348444536285092385691122268234449659670960535975796257967199428661
588501021318479176673708427585774268808650545017660376049723459661849498196642464311064916829738253148094355554612245462904376841893621177730823463158653
879591660683399030304978484321095590963543624456816222726217229824778903020003845084239778076144404530287726188211068276952130766943169135841414345171029
1248406696985734630847706644497004843255944800941245905763962002715214804502912267700863302731463784924539608623245624490324226153139974314259115378371349
1703747492005906963755836936491530390962606636884230489535286254336621356483494685950559886019396626747444008137324065367934154285070018971541983593049861
2254370869043215689464153733230818032491124909408698240350112911979661521768882156017595133419100619346791012586887600048451566033246155890620005096926773
2908889494531426675325542882337318120396915418611133313659242386697400704059386638462626894852013453024393119415321869201289218156987019489743543469580193
9434897306675781564951212127234183234154866904432049663580221005508912897491030704310305798599749145644880438586025871241940975995887375781900132027894693
20334035811070757076533155852865426944500973595795861681680260966542074648115695971957500394213035622503772300153097296264200283924169787531513758375482269
36403148251443687158849125585068097709318290978877843185747694874167997723887660128841698161063693510644320664346038814318383871556083161696339275998500893
58472051844015924569730238860936207763134069355925731894910730642825536979870169349087998840405123123979096043149041268827449319416477624528671652267203333
87394921123503585357517417111936719471650300786641156016785865021792124781476611707020332716208458162844714052711065976434872635825922713014070960049028609
124041075167569566988832342408769555140288266845971137450868787934453309650584915089077785189035715601782207110821595847563391906086495444193801588425319661
169285347521079985901919065523705835586877541411070692568333768984713278304839704390888138552259017102278943045914296949551151398522922559450748476629409021
223998228405624494200707890094800000884404766903996776160540390330978157437110061284224166169034247806527904185343926662387584666737828196986344219267019105
289035974838193554943727484866630064381867272728713721429673641930311354147030948711997359630745908593882734070069058591973819080575347453094857130000093917
937485056111386540174820120214934360249171992394520852602626316190640066228532289228286621833020969414361054038837904507098521502972315755314986450139577629
2020475553372603318208822229642218075414416720395048809677790955139113051528479430406399899731562790091234958953020509217043523521574781083295968194060107893
3617196844416254667455488592584134269620213274843535669891505590667433804600573523098440871117308282532907795764739998001777784616941773764976132146032487437
5810119456896348523755550669423648193996190741955488743639178509604299055881108313808031109746221684197994613555680692613040251691346028701905452412261800057
8684139682656401828248486813987205121892915941731215536532568353808709094794618067202208022131020733680306804876020096749420568846169403207738284185642350009
12325664970622459484930305215720657144866495108607747154702792748477799875478087542768486115898530660609501959846771639474446623763656058753991958651033123177
16821657852066462871994044039090551878897525857090169917486545183957624609532804892197358689445554726261792883169224913646413694396286728352950680036799620817
22258657221013824721950299164965333444560118832487912605496069484818984553349832674949793700988129182705782193693821180638445075711880195429463580107409700981
28721796392333922604324940540979556582928369412921884831578156744983726296160181108363923713381907575379737463116903724288381165743865447755551671389982364349
93159358308567057461977685626667291212457200037487984671551776075941172393578631571391979363525474231123992931026853982907187790544689806835253696428238839185
200779100212612655162169650797524129404947446286060256211919367588266060681598822133090984670106720756437735041044594171111401975496697381401108457399266877917
359451375741971744849881643750679239948970195356131536141598358199182180615228694680777413054548685270553345874664507531002416032708665260962462400266216514925
577373050753694452313447419140690313599066214904601853192971132701792047443708958341987292263987137647624495829639081669153017966381311728728204892307368251845
862982579507021153015035938668825211069459585511303521652552574076356040151218072123181161320704651368448609056474715064857694022930351569098037862519834806897
1224869197045546546612580211733038679445274341924629133625705763239435349211128787753169356988239902788679336617286173953062845164569516738338281858719091382997
1671677990599526167096760276590154333255977753204238725398825303694604129869331216080480962729951457607185394323779203592046647764815630620561242638584882833265
2212012718996121301106749086614136088845540825939287250682138430841202478137174559023754268578977801462934193532697134322783899213101166275166621142439602504617
2854338308641805882314790275908023173109840270398723858954082631913232058048423768600645703169100079102891477568409499129562138616132515139002461481407826941225
9258117990433633557838921464253373424539979635492007220889396592171731286769382893217119858785486692903673510383006158177150776495257180508633312633558426438773
19953423800225394976467659652007917720742447989509739874136746698347308121077435320250962412407181267583200443947055602762152447163911302400161942105457248209405
35722520982696934405594098474735951167497074185983316956999530602670564786954315999272383095034869015835402004557212509763169885974247234872707217351983596318849
57380167882959709881985672576046951030101549145593180043022512978157065165589877963812509773040794707862399264229995643579766397361700248805238465459638470754709
85765183762438654753533795158136873362481241587654919963766888619472546123847174680749047835874760612080793949952012981446773790400005815240885036108375122255777
121731431998320986180006041900295246189515466657955641800219585061386193234763382048778447542209078624706966390220362625640727992682320853233661883577259831818241
166138393718943529959722387140065296875931736357869500172994934922751080744325335537705896786711129940377479422059454282550112699077009367307073707347585922966821
219841517472703017176981901669661112060001479124058873793267933452548230178771996007866654536328386082161567382490568331507336397250467695093910302675983546150645
283682536446466972554606129768283245232189080261076292217733764696602498252427776762279404752352923575828377776541736324187838612953420257748499642467035832599069
920136342148630216535552371661244473754333408069483941415428910734050255087703305709380315275415549358580647986805736405826299157599649187929335255303235560240005
1983122463228641371446963549199230012581575968189426253162016867871086546449633935753104028572450947512522170419408583449709722843530939259471042014365844882050717
3550398977650352751442520176405530921899303480524771178010443367689525354665282506973397085370816831721287570128990168342785676343623798122828872784490043858873833
5702957672638785401890403476789341045187430081546416961552641068994015172565020014245358368483085820907911210369972905561057093023243475256155150383143913022757901
8524186722585379248908816188443526782429274576979083310789672661330730014975139963217925317531874116336358944876400034845112313106564471570788753448847165029029001
12098975274807511972024656357252451679409240728316411208088090015821764988960199970595446013331454309166860541111773294235390241794000155334245471376359627833954533
16512777327971950086687514027705441498094594224123515111140994661979934155868069637920589620405832320684241891457173918908037023654835236888950372520529441317718057
21850653335502495526336370521594835216572215086267795107986057506394497381643027184902285003874951201182053239027393869286755975900103285653876598373827967563338205
28196308554279847538200373760976256364924393807851124596107468361179372729677408060794371840344608880008502364765166239410559894912154887512662544901931566255690941
91456399306381260656772973377477745593457433021950562297437751969664773099463109526983328311073743188475788344739308245130939067600533653826146436106074245630162377
197112433381038684375770158887330017085380215462102503999779959798993271887814149922213782417754839981151197446822878021968121887539693915433553167056215907855520513
352894205145953324767802069235226752779664060032934989701274676284721739313620455543889648556192517878041056701140267068779398434295225668498008807420992421202677185
566853340547059370852010998065265767202562544512250933304372734968138125132393290347066734354607343412258723342015440028041036595687075076810556830570968869676822781
847280142595640405232965222981183949728347823467816065565270982178915843346533153788562171688029924717467878543835743343613079797590896926723243658890877524908545513
1202614663924113842681445016113116421685249567753559151271883023638871570132462053834325577226379156111650745307780313483279841024404512589830258955678253072327701449
1641353733094236075545786618789945203676410823266965248215721483959685176895776034497799261930003595520016068152462526128692693466356452628252596418438397993014991865
2171955765405011737500687714888675742826543964044402385972999523893884347382604166243007735438670036189688341425188233266176197216568452089360593765644656242049668441
2802745247368336401502184889180801001180201487045171623389444737553514791367172252279227648000157883553831042788450407895199520071908487370002767611826586755342882889
9090916672768392868110309272623329811975509741666540973619909936056288461212464043310865478215179414995447481880066731927945534843893217418925164370310212954655441037
19593413632780456770160224566911508537469989851206623628005627602564291517018975163885419930973906250657326303548900739978678394800366644210921448809131469275780681369
35078694915123528845083236167068050815012538978147944736766250799687726651784124354498465070254648396598031610267560449095355159050215607436195640592717916871746529493
56347250563666710236913711585429006652296336385709905983939458548537079201406452834570246721739019167499811450182382247926543055647378043363396080751356415540040004357
84223343042372536459002712499557355936185798758674351680626001166219096353366192458760103383262185900029690360042136884456492853633458295094841653728339246230216383469
119546174669690316073605914453805170658504667973969646027566528116391088825822980097056730618124563190307285724536882979473984190438765206139379823951535803316916252145
163160652835785274734246362637456159393367869932268239873613816898250561321480577171809441647793702206253733133810111784288488441486965791865569669524650654702508752365
215907934853901364283669221416503171343719662255092393629446609810960509106735551065142890753683326977949968896206502053900889503711329860059490239372894989632880885025
278615940102119262029646708825177905225396845201808660625804130903573756841255715047523116740018151705328843327645250033419568086004123570947090187259483747396990768585
903716407927570950868151005547879298010629420460070904260146648176277179417797352192168932260726688012034805812524438868047007646385760543843939864717050856809038946269
1947767197200372985435747310965758176916039845829038877578450983944093847864793702369348928462505599636968486119993038661576708932144060645944268637812765489595119144393
3487169958146074868681695618675342103475693011890798184282505021995543141502132218615428055934438980447725467773510005420823813208648077964254261689743975938338837423473
5601514475834223721463424548167653932322743143306959399904087568134171211948968205907849802971918443797485458594026558341506740369611292765253956822748597734930367367189
8372758336386893554989795358998876440678459039824678800552742359496831965705519515200096184854722927186840512797796522491957080247924117146683306841426419180424788592301
11884349570300215229172181434681855064612830338583774717051290898901263906505251469456739549909744929352945565955496746841394281088532688139449528235724503999259194994805
16220309310813347994326105919604657038511084388978925226950718204969050943420364579555657693754774635860774719086033877333025260576724524465490113626906702672046342523905
21464292532533599677145393191102906357152174128511563024858826373235664009551702105333879803497156540646052571756358552438698055889852469888096061014680507217222323962753
27698645512378900511929508339090844970816792397660604973589117834677472977391329419219588485351615195881909468405210936575329440832486372236037759053496505495861680852809
89843537909518406039329205050749946052546561861884618996926896996347797389569237456788591897992459440525508018073001380895304535889052476752187131000302838121753964951657
193639574080667444871030695732098592281678583134133862612086709201043678051687911108824935489619475459052936739601940073595181198521270927993197269200668236618412164061133
346683257458211189561621071535151975582347296458575649332795987789625252528592343173360895003286238192201399361898068613673405883444784763963380257474875873952893774016349
556888425437636467546376263674605711813217958849614156079535015379990074900371647997316162100849775940812996095477871579115956976053286794988356077854864264563536037029769
832404760165801206804225824322220357151649542386999915174888810385558940999496222867579603735886110561774637732163582083170240120172834272913643634391558589280604520034217
1181530631435953053076683896895578466633355942320131948477497862212158595843656314425338514339106552663801574717453654393943253131110489004925540786882099332027543553111589
1612621964374526269819537944761484175575230640689643866228266572712176359101219888180939573270899113342523510006210257177503203412154747991164147312596105623533403546603849
2133998926682808588565072218743250105220232339506066210390271703937281447328766003688600191074960517045949109414149106343449269588450395260682512038537963358490018535646525
2753852287523964208573213830198637744109786808829490403172142409781733240413049083047764897152112624460084249754191455696265588710722787752621303840403353105583958467235865
8932458595119820675343550453676246814079376156805424517688177595350911346676230684421776995915703212641189561814214009488135430081729652217427345016532020854335218979692037
19252211455026705107984728088502134786921545204840071364542411504745598142279639599796369732225760174751876799710951283922400109068717637368379820691058787382601752329316093
34468469029135142504338620831028696202030443637482631156262481110970182268972171549486798054194546778051377971041065155923588586937363561053397488306331469705718424874485613
55368176841484931102563478491997968370607291561064913269601350361016854006940705061376643941505453225224295236981918875018054736581585151790461957197096608629385903238896781
82761772226566038556882655471647058669913557718509225719857271241553184692637688290520089295025560698407592403587094139576968762308973804695852213336566836837951583413763057
117474525368405947467318110319544105155233611092849918523213072769272565282855499877770749134788025164398243312026931389348739919043079905500019794195162451961948050744811973
160337485109590170449801818006618163934996192256495638583080708368779035686203213146180571961641465523045480461236029585596203998798296965465517461849960308285653802893678609
212178207853428453811453833674367371874838214329522775497142214509293034053292888228306148872848824573808840549076097018160845817825612616060208695511160187331136753664396693
273811453580067897022601585205339855608065091627268669187274807184142227718383551021941778549071824312845136175021396308060026617446472000201888904487564952599754497408668953
888145236671986045950580999713056257638707887787365427755388148670521248646626964138804714074664907779846218357719322881188125116627865240356030172102276595494856969823325713
1914237796232402697505599033731637137415124999833736838173430567703759308896945962248031253213122901302598974729707677639832466150988515186808002557212856258524762973572964077
3427202921597538426130176131623286972450041118439524229923566815345560785732049202509180272590514246582194876524897892645389989427467188300157346299130933914604783734049746453
5505298723015272735450862263983700859078112353351258239316026172453735052531208743524073340376272566290615176199163801219767122288898148094985484128920536327026894839766706173
8229123311961976166200931588961599174331711230779973210266556569373512036244868899307617685759389281083625893775528136897743536345202105448604932562147511695378480734912231089
11680754472769638939870322083087968333843898498466405090344667718521490020774888320754590406183331575206919863529574330475768971602412773655929420774097570209914402492167178141
15942850036622589922219119118640076131982329332648472732786624637205912915797506553712888986305665445385784015801655468353618685026102053378462928955027039766691468958675548953
21097726677131674903545121783258892466505590632225916122742481301742959427485568613267567018801573510218603741890218294498140806066611880570911407683813904339328681313830209281
27226435412999266909675057438933018905248248522621339642646835530020990003828293213502485081656511936572366105209819310109246025430855015617115528508532222541809851792678573073
88313100130533622038068928192552362987997337824056160939956443968554629090360048416795946380403578760596955253822350993177819879745119265897636706371680548861057788553909649829
190344029962415660610314594914912503884778774299241899977331607004635074113534977023219345682825480163180085950515924284515673708424647147824130050269696703026125762919354695545
340789100434306723975858607138620737427158345127160006303414531677976850290175816337965465151241267767174964408213694090319992231750611703119030185365218299239310766315698939969
547431196083259157704983575347227398500236221465782924851458513557542997762905818714491958964438353217545758216359141022838105759061041285786326363073172545116826971748444869137
818286292204703690458460678377982599418604056013683718665788784760694614429774201357770212701858897034831209128472716054798137439043013837659028324224895694459538451699631490549
1161517968391460390577258805532287539167833009221795954444763231346461713492635159004622682746950981781921940429710193112965717474365413575360659499201334470676922881439167744549
1585348014486658979288363407989363020619898183186918493684229224779758754966522933789761719716334260725231546786542580387243620651631186776832295753134943592060764243456354789677
2097964889772774317690650509997664226849806037065451111690441770674333525725802385011137651954095258382231730491063852422258879909585264929326635520226551898333000511321954272921
2707431852510196643656977561107847585604638777406648893634788642171164845247567469809087803830411537451607111248420381275890056940992824023424171213207207886171691949060178346721
8782007421919611280406413724878599363357622636744533234785229646411153808734529917837162087276267441401936802016559156860377970889386052055250371923643691849845812155007832392997
18928234728635642360810310438875410649456680511755360621731781325518562982570784049185331038261886469391579593840650883117595389002025456476634529262582396943307107543157724869461
33889019002918632604037063836271674759095911904253892173155641662281787236145757698594082493647325517605513716469997253524005535662028519944718410949386472347728261394155592873669
54438425877935452265435927636896764003805782547527675962305036077746079915372823910269449743543809149270346982452905519732959747429127340625603959232558807970354527500305743465413
81373739982604105936974624638159809357281160981682435121441756184623018768623389555146621359035900200130151745874025321078452549434878350170190515523209807177787008018513449558981
115506969925043121078170383368370975623549255878993882258443379678792555690251427513717494616801301430058431975183390325680355275452457507249133461464405631490499586551720754640557
157655964699934627789761201718409515916381719683137722419563869659690753315534420343863298055408234861871634328463865408557875903904992839351868850180384754802576388971085737618793
208635316512781838392416093179011760423750895934396012116029840059055508298927854657277794171625938690512972883319323925312820435642174836292591615483381448362355862095068894498973
269247230609812911112581464291087812728834579769230004350260743735340183324663161601654794771457888384231173660437383581911892216260681447221379231970482218793347203227651940749509
873352141290168823085260332718037106594720633489562174731222392631868142551127506953953824713552561933025854212328500072480338329266384554137883693785433594927500890561470679873277
1882382333241750066376467155457891769781288999634624386871053055035344093998329281105308967882659073913432526787043348936855143787437346678424412750155501430888500473018835857212117
3370226715400985549673504876209215954727348722528035497756189926524924225139736856125735357673655247841362575388445245700455252778935865998192209883536697099985039908034630044561709
5413876364690772216516848058409985418850914700477161577982977152258591661028165465843330053665216475706619211768927000845502986658128949819808096302232024179463063432061235575080525
8092635334651588529866369221352798739838104376594644036911040246724160781481080187004573112975874501175367108874659221129679483680199688358615843158511717308264376051219897679602281
11487276418950132411260605988325041094284079386909577411531864033279957311957657865611967798314578725586866212426406770798174714843326126452593023783110000301951284034123156677755885
15679158272101074711082749625336743721619940146753028455535584810387129341892322289303836637301299869815070409822646751438595339026607893721908826860408363448317491752026771934062897
20749321279774886553662424283445985256668736826919608993205222615727298939169329116757063730492080493772041755204978970301052916856061537043152699540259301974206608304763982967377489
26777580127363586699770434119650398662377250287591524842474207357902045928346886957625427140027924661426832196504606188769566848741478415007622486491910446407767903012426754327227905
86858296915780825160696655977129172345464587708303368502416723903557569915514881731666089870775757372835941426727277500462076696641459755001487381414951203629244216573440784647191641
187211208833065104531372588766073061917580736824630515755188801992258660778240019111191720326676871456643502317952028282761763331475906747175167038243672433080982876777154242499402869
335185689494127456582515947395292001457462866225544635638235597988185147023115595900095828425632997339406332516683628050144841652046938108292527488295550337371001671998879640384257677
538439959495952771905875564394066113575993167733401425476454418365031633374231033621712940019967418299579322172247610939791213766124033548625104475914197472528792672167592708239718393
804862653243816269197181742137925422243001684793652605071218372872863520667613412508929750358038673675363696743513441638766325532940508695466931925662445673100268666303872808426099909
1142488912328760577250919964773014447583055858617392497187267848368108948340958707672365271141856843494532982243001931535537099174602649373226008553975757737249564321592376303597188473
1559412635773901667904707855677684941460953208526264465543153097864411712535987293445699741102239718223870678651790757173029760305658050043112164769670109691500509455005931134602129785
2063696615888205742046132373589993819488348269104454622365343125090003901099353595846917797845777159057204649330087896109661837512406081326619629437193280583568994447266180217284229985
2663282343773968060715705774830280263083069762983908984970008932555279314299978053728998732210973217772822891400770867400594310047209100736527977737855353957746668703952805957926905269
8638910806454596061818433756298834802832443063357179437578094056553633945035880246919138120658965526541432894420994942352380893897846238257317047578702924936952666713782930891513544353
18620081267415151384534040541297307447002666467635280779939721773355471530462024378085259046738221559348137164684081409230455705781401921669453250528502981171717144389506845468085772549
33337842070336907968935115257124285331004742366949096364571160918754210863603956740812141403245464958262846854980050609877123817605027574426566445165522334583624979431397504329567758653
53553990983768355321599737266518102883994603922892100006576309643610318726781621830868599373343891003375724976758264911633661397246799106858951181907157612733049866157855508263118133737
80053279609304048134053171330658997588667137275784203900994178768189586479346783769300644777521213986450952813247579638401816123586540580398173230673732966418800003328903403766243291633
113635073500782639668203219466230521584996211769948553261335713384030070288102521504527321279994778274579385146070146408656159957948031278788756720115544737566608991783036104032270830877
155104630052466903101362981191415246354639685558089875204552728689604685037681580292511846820354553343473616981522240147371462690117280626548178066084082286757330537590511503826821179229
205264165999012414363339956168072597788161757975727747723551516007095886003091450327031826427451510660064640060555254899148022447650972054456380796943117205226870075630201762882664536793
264903891869098126458559435977856119450684637530229637927960216293929428459530899337506889954830988952309460939935627350325479867074932964338641462857908988143617206392669552596584481949
859274410842758695072243185290394459937876745256303411191597383416117106032683121083484909334316878250773538757915235202884924927246124047547661563441450929788362568731065559520511166465
1852066009426105960276459494271053432152913739931619178615252216181182074697381346284384182405456660014592821829718619544801192204352177275950648200541148695417076043512785609595941163981
3316000727151549597623762674728795776580716217839828110422421590154986885405696594720185769463448585832275803370256953988959185385090571857442539643321417026791111612725922513846799709553
5326862186302020081166923356888142904576533039014774968367989067260885268754787870944299139829491994203729759787363033047992700739284423356475520718302550366882316543551358730394855128273
7962720720743197406565292129776725186991590664992707659826281796260845469335936264051494048026090895085543480987438635402205285314046566998531136877379792470579014381151769070774476682909
11303104376532580858524586081336360941455914343877162346775149261103179918185913877677785033242983874464790226452123690956916367163852043367616535123147516675263148955403676692249725423161
15428131894450165499945283471445415417898846625864179150878091617053310843945090045658168990878421875961219844996324211425603334155118275059850794703703750504903777806251085806527228642617
20417624757451007273123912245202663131861406228399352073602387357413381182173987061704755812498357452746793541639447874864003383361523609920936998332397532389173561069930696562983809060461
26350215932829723285258434816795803184274862643182521555723509535500554422526724921996407776704464977180152657882790399985244932409998984654189512528653841162154075633442690889631965260701
85473097126045864878428162513988892812903563849361162833667575837461906829853450347420860100292761340880003632685788631700741176219071295535919921923826011046368825114916537453503518182533
184228146148334758057692336739293626595251977528464792094251066004295110870636280962509672481066935827977006676193863434948629064610359263849419478354400424359281080221888632503593766560617
329849882352239034807022808241658189337775665826209031647563438094634997880836354051543175908348724461534782641208323847530163410916052525317085161861730752662231803114210987054043366242557
529877663835298926406585878971697925581479027133674345431838266544445134911849574191296912503305451998577355561635328827689785966810560152884091667976293993314853921733726931256217058287589
792078660913874913197207230079046662000857668685910224931082206653206183505140999681517099216514575412416060050005860592918470324575228502932306339438651696672505697683433459852486182176361
1124365446363385208528469495202552513831436341974049799809773700175485108358190178881889489280058922085479735277456770356827069218612338059914531418821337058076210363227139654009531944828625
1534709804042024599896639682171188060454510294911302098170458197759111589639230266128390749275387518932948797151128164319665751562449286268084757096315263347585606646597111797629658536919433
2031054454247174810094787726937686904855291904808410793020932828507923849880726776577127962481320744267762718608859724786325113391007033228683875804273468973320741005234275275083504943057793
2621224448526100777010412399434794031337538487244720700320309577615017703444855453503595359532872561305976635790102738524512873311979815589923809843508914853879920003957715313601088438076993
8502588462321973384448161054018808161871076994906824142162436608499101324472395497460792077253917969112249435920336429419974389043038236968773904078354450850064358014650762697499457131344633
18326503644370652558516510406231113527268887604528205693263871401641844329024441097132181575505248453472392406193875600121054454893714365571520242152929745929956683520526470260081647504370089
32812711433684081097939064524429449901448364816350913975088618854038006950096309952471748239691198196585573241872615526890038500959024623578127055791982157569886104637759275049000821496606457
52711306804209038761572473565200306496494230083196314188729899792947983180340947956821476616198524741298415250259531846464266307095789358458001820823345878247770201708590497682845635709906513
78795080873557633720932958371136828349328371322461381840673152813409468403823453934132809760680520365198201574942872731853713758661109159540979216254026316110289415497256157265260270049128949
111851328100599873455363621285976857781919816208866205497726796440469117407039261198017214525236506637294490987448742056964644856843163065683771406446734223701679517965814440159848673935250813
152673277310173733282237266526362821678728681479918288073576335544309776346247000971743579090848060049890242388307805571138455895689528100323543558250172156070170639082309313435119627037451813
202051315401963723585382011109517439813101188553695212689724041773508652767268988132634137574506113195326550095926178514236818318227413077966032292535789698610349834450406922317713299790375017
260764178007674583499500507775212099802317225121610133545059556122622388355036002638597643707735592135880558588119047981215893142330460588616746334255615343732288464611110635389023322707932033
845856189521183800842914766147782039728631349255656258927907714169530840457246451630249864112731558923934276172608336910334267627523117817318467414098029321185304434130323717165241503240192145
1823168748953142588500317094356485137516324316194222317423368449099773615824018213899350336418914669649236425593460242282364587081274281956212424134538715957903096309936514591349450198765066581
3264310599929110067907079905822154137450418381265479732012431492178675479972371641197669091598318096227323563231544799816732104804058794052623485469016990528269317221781060144874328311570616705
5243912963933408937133042167378765823759204849058848653945503583216531473053419538218081427894115772242259216071249539159073749857769240496356383487684387036126726157616158715096913983736320637
7838868249791892701312659142393253980308955359268636823620195949001877501393281754618988171284843220541946710807506807478325363388969372696235615185082001846605424244561619103005204629674045841
11127515508715882959192357679826853384401290743634413161004916416994571885144070310772151494603139737686025498699338887713389632732207694287348427771493892602744898038905613709796644457328047157
15188788467970166584363415012465296931847026685764589143843275836331392871777625872313387419235494065729299577258540165424996034305374698909765167363293493284131546876138968354395307014227199633
20101342932755331481716855590345467625670742901322085802339900558471241103552336760796029252598171226505373838826708784263948587327503595441401601607843511317619710346854500754435256490254685517
25942680883634364881674824973765556257925067775121054888092611983985919045644848866640525501661938134444678226498768089414516245768375350060217009217290375017407760245389772928776483498008360537
84152122111815344849048680560041103910097825908004925343660709532179528875946290711191407828628414506668116385433128827246516537269389170633906037492518930009186911327781420126798495168405131945
181383278796684845100043712844850624012932709010528372122001351430564185407240330024508244840916757260602343623059086720575992350311446366870809203197913845040355822094079393766391223165576133625
324761036021418152158431593624727634562528958435068893599906207620700474587362943555850992977837639822345834386681908981771718924769975697576202002189440025402673732008091438425329172560872645777
521711254628348692443619633963969691137067077039906236795621407054100361174379675135839374572723578561125600498465817705324438833804478729504403124365193977951875197859524531723215046746928904513
779885079491650715052913473014031263173747480611189884314090146560889597020375936698005827284988179316372827640702387869211522753459438181923727884511195312890912983198972874207328898007376976217
1107077950570336675862939859667387746002044657006818310968931916260722065875140602410320618109713765066222417541586375960462028106929392520267211360240773577335687996382676865313253665482109954653
1511144891125373094462637351913055598125623393966659012875606360476498176136548187595165124037406915903723164597046773096780966827129567976868564497187899513270378116431989736970843204757681501789
1999913742610971329340409771562503210138240075220613541664356150219378071641571421086388237514829250972278009250725033292285753932584873292895614009334252594341668910745197322609794442142179558897
2581098069231995081818280038012815487648153495512289756778132924087112888255783557971136758505126927331626877042169492263457474000857498191824480629858119214200688762834018805086390617750925709413
8372522242179803387410514223488329153823615017382237585394297212255035650113159353984641930834225864043820929325087352263079939225472241648097716821596845376289069699922825252108022754089075776461
18046387901933102579783759479255476063308599392473569596953087049160149420456044293085902534453596139652295071220458171405001245137943168873123082350785841910240736669952586462745460706646233215665
32311638334384966192534770553641183464565991023386341834141441336118240567953366719888636191166884611166921134699880545573841040845206965808726228617630495460408679182185693271733737844505873987637
51907188723472856253787304530071795389346128125622245409332342217974996718111215870323109283344747544144462805206880582089930225812858383215698187206487717322320662309416537015153464205212973885609
77594399978001237253413001657475125783413965197231491639667645430244070488773074126426611689922742847731103780979710107597050173908694965378302949433281298235558741521369468704996918835809449999301
110149025615688029595976998286773618006044625810729640835656213779064593256558965645994811807792011733419093282574990780550460846300576255185587980763313184575347573436376648197698120851412536449241
150352788265515464853970077310086534638109335540022664349118715693270025260443461120790123623576493361014442338286943714587980241431296616447084436900023255237121642446548333423531783437013830547813
198984751810292486750111102417499909128568281889440403388675167695159623449072786261065147142174248658046082542812296945408618305544670440312079423580240098337626585466006594222091415866171799847697
256812660510775774018042243297232242861247175625352634837147476013770950763686170552499177928449026588410932162392987597147711069634237694318327785133000715192348594272795096018768131114967967536325
833047542363284631252900404066791363224793300153452833655011972640482118132462796423020466606359230846624949039419516439179582147797241950740466018464225609030122497822520100462226532701092096938033
1795583193996143803496831797183761621574931762368271187800492556814963040474433353244756554013906124079942475594770062890976760020190015819500328259674115031764079735352329890669931778245154381740085
3214964660094822857022271272819886573254072636723793751496242993578370875830530126553944842850259101498453574916348843998337329966758770011875699560353937261380896601124669605517960541396868506679749
5164721757020030373884502035129899965711691719334769341894342596558024070784850193500726548405871845266450769360807595506407087236939685809956514042034181012979511252086976320863304561204878771822477
7720620684155371762972153835691316073947779038543711846507031186783898182987158433325122418747532576012691819483748294124893503844352946437499043922925513409521311007458430664447229904669426111232217
10959863214680428090902744503847091743875453435257570106938348565982415774816300624475480267278093388191549669655011146778419509563107248967734270766683264518316164601306193372777834768795637947900109
14960249035600928299943281796007212076798195137670071469298912902274245752628276888203860136690762199826859406408293736561614578566016141791135960349766178569493471202816561239623885195752151528505585
19799317747853239999527007711202071271575580418809487481278118791600652714906198460341153944093166650577908619475701068323074001876266815087796803280265658060479433032362166908405112426663619040296849
25553487566414313736765876526858655416348408569602373311205578801570991672416665548466562372600848514566322869532853003911405568908908680920459385785411079414744039231969532161736431112442288061012277

  

Приложение. Десятичный логарифм первых 900 значений

Скрытый текст

0
0.698970004
1.113943352
1.397940009
1.612783857
1.785329835
1.929418926
2.053078443
2.161368002
2.703291378
3.049605613
3.306425028
3.511214701
3.681693392
3.827692289
3.955254683
4.068371418
4.169821329
4.680380845
5.010660305
5.258955585
5.459213003
5.627497969
5.772759449
5.900522791
6.014453751
6.117117774
6.624937376
6.9545426
7.203063499
7.404040062
7.573352045
7.719846308
7.848984293
7.964388084
8.068591552
8.576721189
8.906943258
9.156243132
9.358106986
9.528386795
9.675911565
9.806129497
9.922651997
10.02800389
10.53660346
10.86737804
11.11729256
11.31982308
11.49081446
11.63908985
11.77009218
11.88742802
11.99361768
12.5025871
12.83377684
13.08414703
13.28717005
13.45868748
13.60751933
13.73910552
13.85704971
13.96386938
14.47312064
14.80462536
15.05534145
15.25873922
15.43065823
15.57991648
15.71195195
15.83036635
15.93767527
16.44714626
16.77889681
17.02988345
17.23357513
17.40581002
17.55540479
17.68779606
17.80658422
17.91428352
18.4239302
18.75587766
19.00708144
19.21100953
19.38349916
19.53336603
19.66604582
19.78513796
19.89315576
20.40294604
20.73505465
20.98643644
21.19055872
21.36325803
21.51334936
21.6462677
21.76561181
21.87389429
22.38380408
22.71604696
22.9675773
23.17186187
23.3447367
23.4950163
23.62813513
23.74769143
23.85619729
24.36620805
24.69856452
24.95022065
25.15464285
25.32766676
25.47810649
25.61139614
25.73113354
25.83983041
26.34992761
26.68238139
26.93414541
27.13868578
27.31183785
27.46241544
27.59585235
27.71574612
27.82460817
28.33478018
28.66731826
28.91917582
29.12381874
29.29708216
29.44777966
29.58134482
29.70137495
29.81038124
30.32061864
30.65323043
30.90516986
31.10990263
31.28326368
31.43406642
31.56774427
31.68789436
31.79702768
32.30732271
32.63999952
32.8920112
33.09682331
33.27027065
33.42116651
33.55494415
33.67520057
33.78444662
34.29479283
34.6275274
34.87960331
35.084486
35.25801017
35.40898899
35.54285562
35.66320694
35.7725537
36.28294565
36.61573187
36.86786525
37.07281114
37.24640414
37.39745734
37.53140381
37.65184035
37.76127762
38.2717107
38.60454339
38.8567285
39.0617313
39.23538632
39.38650658
39.52052509
39.64103857
39.75055763
40.26102789
40.59390261
40.84613451
41.05118882
41.22490002
41.37608105
41.51016488
41.63074819
41.7403415
42.25084554
42.58375844
42.83603289
43.04113405
43.21489636
43.36613273
43.50027606
43.620923
43.73058404
44.2411189
44.57406665
44.82637995
45.0315239
45.20533291
45.35661986
45.49081762
45.6115228
45.72124586
46.23180895
46.56478864
46.81713754
47.02232073
47.19617259
47.34750596
47.48175369
47.60251237
47.71229244
48.22288149
48.55589055
48.8082722
49.0134915
49.1873828
49.33875893
49.47305271
49.59386071
49.70369335
50.21430634
50.5473425
50.79975439
51.00500703
51.17893477
51.3303504
51.46468674
51.58554034
51.69542162
52.20605677
52.53911802
52.7915579
52.99684143
53.17080291
53.32225516
53.45663096
53.57752686
53.68745326
54.19810898
54.53119352
54.78365939
54.9889716
55.16296444
55.31445071
55.44886319
55.56979843
55.67976682
56.19044168
56.52354789
56.77603796
56.98137687
57.15539893
57.3069169
57.44136357
57.56233549
57.67234304
58.18303575
58.51616219
58.76867484
58.97403869
59.14808801
59.29963559
59.43411421
59.55512041
59.66516456
60.17587397
60.50901933
60.7615531
60.96694027
61.14101512
61.29259042
61.42709895
61.54813725
61.65821571
62.16894076
62.50210385
62.75465743
62.96006647
63.13416526
63.28576656
63.42030316
63.54137159
63.65148225
64.16222199
64.49540173
64.74797391
64.9534035
65.12752479
65.27915053
65.41371351
65.53481028
65.64495123
66.1557048
66.4889002
66.74148989
66.94693883
67.12108129
67.27273004
67.40731789
67.52844135
67.63861085
68.14937745
68.48258762
68.73519381
68.94066099
69.11482342
69.26649389
69.40110518
69.52225385
69.63245029
70.14322919
70.4764533
70.72907509
70.93455949
71.1087408
71.26043178
71.39506523
71.51623771
71.62645964
72.13725016
72.47048747
72.723124
72.9286247
73.10282386
73.25453426
73.38918869
73.51038372
73.62062977
74.13143132
74.46468112
74.71733161
74.92284776
75.09706383
75.24879263
75.38346695
75.50468336
75.61495229
76.12576429
76.45902594
76.71168968
76.91722048
77.09145261
77.24319887
77.37789207
77.49912878
77.60941944
78.12024135
78.45351426
78.70619059
78.91173531
79.0859827
79.23774555
79.37245669
79.4937127
79.60402402
80.11485538
80.44813899
80.70082729
80.90638525
81.08064716
81.2324258
81.36715402
81.4884284
81.59875939
82.10959973
82.44289353
82.69559324
82.90116381
83.07543954
83.22723324
83.36197772
83.48326961
83.59361934
84.10446825
84.43777177
84.69048235
84.89606495
85.07035387
85.22216191
85.35692192
85.4782305
85.58859813
86.09945521
86.43276801
86.68548897
86.89108305
87.06538455
87.2172063
87.35198113
87.47330567
87.58369038
88.09455527
88.42787693
88.6806078
88.88621285
89.06052639
89.21236123
89.34715024
89.46849002
89.57889108
90.08976344
90.42309357
90.67583393
90.88144948
91.05577452
91.2076219
91.34242446
91.46377884
91.57419554
92.08507505
92.4184133
92.67116273
92.87678833
93.05112439
93.20298377
93.33779932
93.45916768
93.56959937
94.08048572
94.41383175
94.66658989
94.87222511
95.04657174
95.19844262
95.33327062
95.45465239
95.56509845
96.07599137
96.40934486
96.66211134
96.8677558
97.04211257
97.19399448
97.32883443
97.45022907
97.56068891
98.07158814
98.40494878
98.65772328
98.86337661
99.03774311
99.18963562
99.32448704
99.44589403
99.55636713
100.0672724
100.4006399
100.6534221
100.859084
101.0334598
101.1853625
101.320225
101.4416438
101.5521297
102.0630408
102.3964149
102.6492045
102.8548745
103.0292594
103.1811719
103.3160449
103.4374752
103.5479733
104.05889
104.3922705
104.6450672
104.8507451
105.0251386
105.1770606
105.3119438
105.4333851
105.543895
106.0548171
106.3882037
106.6410073
106.8466928
107.0210946
107.1730256
107.3079187
107.4293706
107.5398918
108.0508191
108.3842117
108.6370218
108.8427147
109.0171245
109.1690643
109.3039669
109.425429
109.5359612
110.0468935
110.3802917
110.6331082
110.8388081
111.0132257
111.1651739
111.3000856
111.4215576
111.5321004
112.0430375
112.3764412
112.6292639
112.8349706
113.0093957
113.161352
113.2962726
113.417754
113.528307
114.0392488
114.3726578
114.6254864
114.8311997
115.005632
115.1575962
115.2925253
115.4140159
115.5245787
116.0355251
116.3689392
116.6217735
116.8274932
117.0019324
117.1539042
117.2888415
117.4103411
117.5209134
118.0318641
118.3652831
118.6181231
118.8238488
118.9982948
119.150274
119.2852193
119.4067274
119.5173089
120.0282638
120.3616877
120.6145329
120.8202646
120.9947172
121.1467034
121.2816564
121.4031728
121.5137633
122.0247222
122.3581507
122.6110012
122.8167386
122.9911975
123.1431906
123.2781511
123.3996755
123.5102746
124.0212375
124.3546705
124.607526
124.813269
124.9877339
125.1397338
125.2747014
125.3962336
125.5068411
126.0178078
126.3512451
126.6041055
126.8098539
126.9843248
127.136331
127.2713057
127.3928454
127.503461
128.0144314
128.347873
128.600738
128.8064917
128.9809683
129.1329808
129.2679622
129.3895093
129.5001327
130.0111068
130.3445524
130.597422
130.8031807
130.9776629
131.1296815
131.2646695
131.3862236
131.4968547
132.0078322
132.3412818
132.5941558
132.7999195
132.974407
133.1264315
133.2614259
133.382987
133.4936254
134.0046063
134.3380597
134.5909381
134.7967065
134.9711993
135.1232295
135.2582301
135.3797978
135.4904434
136.0014276
136.3348847
136.5877673
136.7935403
136.9680382
137.120074
137.2550806
137.3766548
137.4873074
137.9982948
138.3317555
138.5846421
138.7904197
138.9649225
139.1169637
139.2519761
139.3735567
139.484216
139.9952065
140.3286708
140.5815613
140.7873432
140.9618509
141.1138973
141.2489154
141.3705021
141.481168
141.9921615
142.3256292
142.5785236
142.7843098
142.9588221
143.1108736
143.2458972
143.3674899
143.4781622
143.9891586
144.3226296
144.5755278
144.7813181
144.955835
145.1078914
145.2429204
145.3645189
145.4751974
145.9861967
146.319671
146.5725727
146.7783671
146.9528884
147.1049496
147.2399839
147.361588
147.4722726
147.9832746
148.3167521
148.5696574
148.7754556
148.9499812
149.1020472
149.2370865
149.3586961
149.4693866
149.9803914
150.3138719
150.5667806
150.7725827
150.9471125
151.099183
151.2342273
151.3558422
151.4665385
151.9775459
152.3110294
152.5639415
152.7697472
152.9442811
153.0963561
153.2314052
153.3530254
153.4637272
153.9747372
154.3082236
154.5611389
154.7669483
154.9414862
155.0935655
155.2286194
155.3502446
155.4609519
155.9719644
156.3054536
156.5583721
156.7641851
156.9387268
157.0908104
157.2258688
157.347499
157.4582116
157.9692265
158.3027185
158.5556402
158.7614565
158.936002
159.0880897
159.2231526
159.3447876
159.4555054
159.9665227
160.3000174
160.5529421
160.7587618
160.933311
161.0854027
161.22047
161.3421097
161.4528326
161.9638522
162.2973495
162.5502772
162.7561001
162.930653
163.0827486
163.2178201
163.3394644
163.4501923
163.9612141
164.294714
164.5476445
164.7534707
164.928027
165.0801265
165.2152022
165.336851
165.4475836
165.9586077
166.2921101
166.5450434
166.7508727
166.9254325
167.0775357
167.2126154
167.3342686
167.445006
167.9560322
168.289537
168.5424731
168.7483055
168.9228686
169.0749754
169.2100591
169.3317166
169.4424585
169.9534868
170.2869941
170.5399329
170.7457682
170.9203346
171.072445
171.2075326
171.3291942
171.4399406
171.950971
172.2844806
172.537422
172.7432602
172.9178298
173.0699437
173.2050351
173.3267008
173.4374516
173.948484
174.2819959
174.5349398
174.7407809
174.9153536
175.0674709
175.202566
175.3242357
175.4349908
175.9460251
176.2795393
176.5324857
176.7383295
176.9129053
177.0650259
177.2001246
177.3217982
177.4325575
177.9435938
178.2771101
178.530059
178.7359056
178.9104843
179.0626082
179.1977104
179.3193878
179.4301512
179.9411894
180.2747078
180.5276591
180.7335083
180.90809
181.0602171
181.1953227
181.3170039
181.4277713
181.9388113
182.2723318
182.5252855
182.7311373
182.9057218
183.057852
183.192961
183.3146459
183.4254172
183.936459
184.2699816
184.5229375
184.7287918
184.9033791
185.0555124
185.1906248
185.3123131
185.4230883
185.9341319
186.2676565
186.5206146
186.7264715
186.9010615
187.0531977
187.1883133
187.3100052
187.4207842
187.9318294
188.265356
188.5183163
188.7241756
188.8987683
189.0509075
189.1860263
189.3077216
189.4185042
189.9295512
190.2630796
190.5160421
190.7219038
190.8964991
191.0486411
191.183763
191.3054617
191.4162479
191.9272965
192.2608269
192.5137915
192.7196555
192.8942534
193.0463982
193.1815231
193.3032251
193.4140149
193.9250651
194.2585972
194.5115639
194.7174302
194.8920306
195.0441782
195.1793061
195.3010113
195.4118045
195.9228563
196.2563903
196.509359
196.7152275
196.8898304
197.0419807
197.1771115
197.2988198
197.4096164
197.9206698
198.2542055
198.5071762
198.7130469
198.8876522
199.0398051
199.1749388
199.2966502
199.4074502
199.9185051
200.2520425
200.5050151
200.710888
200.8854957
201.0376512
201.1727877
201.2945021
201.4053053

Комментарии (6)


  1. nezhi Автор
    06.09.2025 20:25
    #28805498

    Вкратце алгоритм такой:

    Рассчитываются все возможные варианты области 10*10 с координатами (0;0)-(9;9)

    Потом из этих кирпичиков рассчитываются все возможные варианты для области 100*100

    И так далее каждый раз увеличивая размер области в 10*10 раз


  1. Dimonogen
    06.09.2025 20:25
    #28806104

    Вот интересно, если рисунок и узор повторяется, нельзя ли вывести аналитическую формулу?


    1. nezhi Автор
      06.09.2025 20:25
      #28806502

      Можно попробовать. Но мне кажется будет сложно. Если бы чистая область была больше, было бы проще. Тогда можно было бы обсчитывать недоступные клетки на краю. Проблема в том, что при N=1800 например, при максимально доступной координате из двухсот девяток недоступные клетки будут начинаться в квадрате со стороной в сто девяток, что на сто порядков меньше максимальной координаты и помощи от внутренней пустой области нет.

      Другой вариант, который хочу попробовать - использовать ряды Фурье, т.к. отклонение функции периодическое. Но в этом случае будет приближенное значение, а не точное.


  1. lightln2
    06.09.2025 20:25
    #28807642

    упс, хотел написать длинный комментарий, но случайно опубликовал его. Напишу его заново и опубликую


  1. lightln2
    06.09.2025 20:25
    #28807744

    Спасибо, интересная задача!
    Я немного подумал над ней, но в комментариях хабра мало места, чтобы подробно написать. Примерно так получилось (рассуждения, в принципе, повторяют ваши, но только в более привычных обозначениях):
    Во-первых, возьмем основание системы счисления произвольное b вместо 10, мне так формулы легче воспринимаются. Для положительных x обозначим сумму цифр d(x, b)
    Теперь сначала рассмотрим одномерный случай: посчитаем количество таких x, что d(y, b) \le n для всех 0 \le y \le abs(x), будем называть такие числа достижимыми (из нуля).
    Для этого введем две функции: f(n, k) - количество достижимых чисел в отрезке [0, b^k] и q(n, k), равная единице, если сумма цифр последнего числа в отрезке [0, b^k] не превосходит n, иначе нулю. То есть, она говорит, можем ли мы продолжать смотреть следующие отрезки, или надо остановиться.
    Тогда f и q можно выразить такими формулами:

    q(n, k) = 1 \ if \ n \ge k(b-1) \ else \ 0f(n, k) = f(n, k-1) + \sum_{x=1}^{b-1} f(n-x, k-1) q(n-x+1, k-1)

    Теперь точно так же рассмотрим двумерный случай. Удивительно, что условие на то, надо ли нам рассматривать следующий квадрат или нет, сводится к той же самой функции q (не зависящей от размерности!). Я строго не смог доказать это, но там должны быть примерно ваши рассуждения. Для двумерной f формула почти такая же:

    f(n, k) = f(n, k-1) + \sum_{1 \le x, y < b-1 , (x,y) \ne (0,0)} f(n-x-y, k-1)q(n-x-y+1, k-1)

    Или можно ее сократить до одной суммы, если взять diag(t) равной количеству пар x, y в квадрате bxb, в сумме не превосходящих t:

    f(n, k) = f(n, k-1) + \sum_{t=1}^{2b-1} diag(t) f(n-t, k-1) q(n-t+1, k-1)

    Теперь, имея одномерную и двумерную функции, можно получить ответ по принципу inclusion-exclusion.
    Что касается кода, то проверить правильность результата можно обычным поиском (в глубину или ширину, неважно): код на питоне

    Вычислить сразу все решения до заданного n можно по этой рекуррентной формуле: код на питоне, вроде бы результаты совпадают с вашими c b=10, N=900.

    Сложность алгоритма O(n^2 * b), так как надо итерировать f до значений k=O(n).


  1. lightln2
    06.09.2025 20:25
    #28809010

    Это, конечно, баловство, но я уместил решение в восемь строчек на питоне! Тут смысла не очень много, это просто формальное преобразование ранее полученных формул с целью уменьшения количества кода.

    def cnt(N, b):
    f1, f2 = [1]*N, [1]*N
    for k in range(1, N//(b-1) + 2):
        for n in reversed(range(N)):
            f1[n] += sum(f1[n - min(b-1, n, n+1-(k-1)*(b-1)) : n])
            for t in range(1, min(2*b-1, n+1, n+2-(k-1)*(b-1))):
                f2[n] += (b - abs(b-1-t))*f2[n-t]
    return [f2[i] * 4 - f1[i] * 4 + 1 for i in range(N)]