Закончились рабочие будни. Появилось настроение отметить завершение очередного аврала в череде поддержки и доработки проекта автоматизации бизнес процессов организации, где я мотаю срок программистом. Настроение подогревала мысль, что трудный этап решения технических проблем был пройден именно благодаря моим нововведениям, что смогли освежить кодовую базу. Хотелось упрочить в себе чувство собственной важности найдя себе в спарринг-партнера достойную игрушку для битья. С этого и начнется занимательная история о том как я разбил свое высокомерное выражение лица об одну олимпиадную задачку по программированию из разряда basic.

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

И так! Олимпиадное программирование! Кто еще может так безропотно принимать поражение от моих рук как не безмолвные задачки на сайтах с Judges. Я побродил по разным сайтам, ужасаясь их дизайном и удобством использования, и остановился на Spoj (Sphere online judges). Были сайты и более дружелюбные к пользователям, но на них нет такого объема задач. Ну и нет такого родного моей душе ощущения кондовости. Прибавим сюда высокую активность программистов, решающих задачки, и получаем довольного выбором меня.

Основой язык программирования на моем месте работы - JS/NodeJs, PHP и Kotlin. Только вот тщеславие не позволяет мне быть попсовым и я выбираю своим инструментом решения задач даже не C++, а голый и незамутненный язык C. Решил пару задач для разминки уровня Hello wold и поймал себя на мысли, что меня угнетает писать одни и те же инструменты для разных задач, даже если мне нужно их просто копировать из прошлых задач. Для тех, кто не погружался в проблематику: решением задачи может быть только один файл и если вы выносили служебный код в библиотеки, то в результате вам в ручную придется их объединить в один большой файл исходного кода перед отправкой своего решения на суд автотестов. В результате пишу инструмент, который компонует все мои подключаемые файлы в файл с main функцией: C problem solution inlner. Данный инструмент интересен и достоин отдельной статьи, но больше о нем вы тут не услышите, так как кривыми дорожками я пришел к тому, что решить задачу, о которой пойдет дальше речь, на языке PHP будет более амбициозно. Такова доля пользователей Интернета - иногда можно наткнуться на целый абзац, который интересен лишь тому, кто его писал.

И вот я добрался до задачи FUSC - Obfuscated Property, что сразу шла после задач типа "удалите все нечетные символы в строке".

Постановка задачи

Дана последовательность чисел:

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4...

Последовательность определяется рекурсивными формулами:

В 1982 году Дейкстра назвал эту последовательность fusc, потому что она обладает любопытным загадочным свойством: если сумма двух индексов, и , равна степени , то и будут взаимно просты. Пример:

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

Пример такой закономерности можно увидеть, если записать последовательность делая перенос строки при достижении следующего порядка в двоичной системе счисления:

1
1, 2
1, 3, 2, 3
1, 4, 3, 5, 2, 5,  3, 4
1, 5, 4, 7, 3, 8,  5, 7,  2, 7,  5, 8,  3, 7,  4, 5
1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6

Нулевой элемент последовательности при этом опускается.

Первая закономерность: сумма ряда под номером равна

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

Вторая закономерность: каждая колонка является арифметической прогрессией, шагом которой являются числа самой числовой последовательности fusc. Например, у первой колонки шаг прогрессии , так как . Вторая колонка имеет шаг . Третья: . Четвертая . И так далее. Обладая этим знанием я решил, что уже обладаю достаточной предсказательной силой, чтобы справиться с заданием, но оказалось, что я тут даже близко не рядом.

На этом вводные данные заканчиваются и идет само задание:

Ввод программы

Одна строка, содержащая число в диапазоне

Вывод программы

Одна строка, содержащая число равное .

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

Ограничения

Пример ввода

10

Пример вывода

4

Анализ

Ну что тут может пойти не так? Разве должно меня пугать ? Решил пойти почитать комментарии тех, кто уже пытался решить задачу. И тут меня начали терзать сомнения. Особенно мне понравились комментарии:

bruh who the fck is creating these questions

Time limit 1s and they allow script languages Python?! That's sadistic.

did anyone find max(f(i)) by not using loop ? my code always reach the TLE in test case 5

I have no idea what I’m doing

I need help

10 PRINT "I CAN'T READ"
20 GOTO 10

Я начал понимать, что попытка решить задачу перебором даже используя язык C не даст результата. Даже в том случае, если я придумаю как исключить лишние операции в переборе и исключу диапазоны , которые заведомо не будут содержать максимумов. Так же стало понятно, что если я попытаюсь оптимизировать код по быстродействию в ущерб оптимизации по потреблению оперативной памяти, то ничего не выйдет, так как целочисленных значений - это 4ПБ даже если использовать int (4 байта). Даже если я в тысячи раз сокращу объем хранимой в ОЗУ информации, то нет еще таких компьютеров в мире, которые это осилят. И тут у меня упала планка адекватности и захотелось дать ответ тому комментатору, который писал про Python. Ответом будет то, что я напишу решение задачи на PHP! Это ли не почесывание своего ЧСВ? Написать на далеко не самом быстром языке программирования решение задачи, которое не всякий даже на компилируемых языках могут написать, да еще и доказать, что интерпретируемый язык - не приговор, если подойти с головой. Но тут без спойлеров никуда! Вот мой комментарий к этой же задаче через несколько дней:

I took the challenge to write a solution to the problem in PHP. I was naive. A regular loop of 10**9 iterations with a minimum of arithmetic takes me 14 seconds.

I will rewrite my solution in C later.

Разбор примера ввода/вывода

В задаче нам говорится, что при вводе значения 10, мы должны вернуть значение 4. Это означает, что для получения такого результата мы должны взять значения из fusc последовательности с -го элемента по -й:

Среди полученного числового ряда нужно найти максимальное число. Тут оно находится с первого взгляда. Это число .

Поиск решения путем простого перебора

Создается впечатление, что если просто вычислять элементы числовой последовательности по порядку до порядкового номера, полученного из ввода и записывать в отдельную переменную максимальное (простейший алгоритм нахождения максимального значения), то без труда получится дать ответ. Однако при большом входном значении от нас потребуется очень быстрый способ вычисления элементов последовательности. Я довольно быстро нашел оптимизированный алгоритм вычисления произвольного элемента fusc последовательности. Он есть даже на странице Wiki, ссылка на которую есть выше. Если этот алгоритм дополнительно оптимизировать, то получим:

function fusc($n): int
{
    $a = 0;
    $b = 1;
    while ($n > 0) {
        $n & 1 ? $a += $b : $b += $a;
        $n >>= 1;
    }

    return $a;
}

Как видим, это алгоритм с рекурсией, в котором рекурсия в целях оптимизации заменена циклом. И чем больше параметр $n, тем больше итераций потребуется для вычисления значения. Скажу прямо - это не тот вариант, на который я рассчитывал. Например, для вычисления потребуется 50 итераций. Простые подсчеты говорят, что нахождение максимума перебором с использованием данного алгоритма займет годы, даже если ограничивать область поиска.

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

function fuscIterator(): Iterator
{
    yield 0;
    yield 1;
    yield 1;

    $buffer = [0, 1, 1];
    $n = 1;
    while (true) {
        $n++;
        $nx2 = $buffer[$n];
        $nx2p1 = $buffer[$n] + $buffer[$n + 1];
        $buffer[] = $nx2;
        $buffer[] = $nx2p1;
        unset($buffer[$n]);
        
        yield $nx2;
        yield $nx2p1;
    }
}

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

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

Поиск закономерностей

Это была легкая разминка, чтобы просто прощупать предметную область задачи и научиться быстро генерировать тестовые образцы разных участков fusc последовательности. Я и не собирался всерьез расценивать возможность решить задачу методом перебора. Но какие у меня альтернативы? Можно подглядеть подсказку на сайте всея числовых последовательностей: Stern's diatomic series (or Stern-Brocot sequence). По количеству комментариев к последовательности можно оценить сколько интересных закономерностей в этой последовательности уже найдено. И это не удивительно, так как ее изучают более столетия. Я честно потратил несколько часов, чтобы найти что-то полезное не только в этих комментариях, но и в числовых последовательностях имеющих отношение к fusc последовательности. И не сказать, что это совсем не помогло. Например, обнаружилась связь fusc последовательности с числовой последовательностью Фибоначи. При чем пересечений с числами Фибоначи несколько. Но об этом я уже и так знал, так как одно из таких пересечений прямо бросается в глаза, если попробовать отобразить fusc последовательность в виде бинарного дерева. Почему бинарное дерево? Это просто понять, если посмотреть как работает ранее описанный мною итератор: каждая итерация цикла в нем порождает сразу два числа в конце буфера и лишь одно число удаляется из начала буфера. Так же по формулам, определяющим fusc последовательность

видно, что число с порядковым участвует для вычисления чисел и . Этого достаточно, чтобы поставить как родительский узел для двыух дочерних: и . Конечно, в вычсислении учавствует и , но для визуализации бинарного дерева это не существенно.

Вот черновой вариант, набросанный в текстовом редакторе от руки:

                                                              0
                                                              |
                                  ____________________________1___________________________
                                /                                                          \ 
                  _____________1_____________                                   ____________2_____________
                /                             \                               /                            \
          _____1_____                     _____3_____                   _____2_____                    _____3_____
        /             \                 /             \               /             \                /             \
       1               4               3               5             2               5              3               4
    /     \         /     \         /    \          /     \        /    \         /     \        /     \         /     \
   1       5       4       7       3      8        5      7       2      7       5       8      3       7       4       5
 /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \   /  \    /  \   /  \    /  \    /  \    /  \    /  \
1    6  5    9  4   11  7   10  3   11  8   13  5   12  7    9  2    9 7   12  5   13 8   11  3   10  7   11  4    9  5    6

Что сразу бросилось в глаза:

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

2. На каждом уровне дерева локальным максимумом является число из последовательности Фибоначи: 0, 1, 2, 3, 5, 8, 13. И номер уровня бинарного дерева, если нумеровать с нуля, совпадает с порядовым номером числа фибоначи в числовой последовательности Фибоначи, которое в нем появляется.

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

Заинтересовавшись этими закономерностями я написал диаграмму:

Возмущение!!!

Давно не писал статьи на Хабре. Какое разочарование у меня было от того, что тут нельзя вставлять в статью SVG изображения - не предать! Я мог бы опубликовать тут диаграмму дерева вплоть до 13-го уровня, что было бы куда информативнее чем PNG картинка.

В данной диаграмме:

1. Желтыми сносками подписаны первые узлы каждого уровня. В этих сносках вновь появляется, которое я упоминал ранее и говорил, что оно еще пригодится нам. Число одновременно является и порядковым номером уровня и индикатором того сколько битов требуется для записи порядкового номера элементов fusc последовательности на соответствующем уровне в двоичной системе счисления. Спойлер: далее значимость будет только возрастать.

2. Красные числа - числа Фибоначи. Это однозначные локальные максимумы. Если вводом в программу будет порядковый номер числа, попавший в диапазон уровня дерева и при этом этот порядковый номер больше или равен порядковому номеру красного числа, то мы можем сразу возвращать красное число как результат выполнения программы

3. Синие числа - числа fusc последовательности чей порядковый номер () нечетный и при этом само число больше числа фибоначи, встреченного на уровне дерева выше. Это кандидаты в максимальное число - если в программу введен порядковый номер числа меньше чем у красного числа, то максимум нужно искать на уровне дерева среди синих чисел.

4. Серые числа - это все остальные числа fusc последовательности. Серые они потому что они ни при каких условиях не могут рассматриваться как кандидаты в максимальное число - если вводом в программу будет номер серого числа, я точно могу сказать, что максимум нужно искать среди чисел с меньшим порядковым номером.

Оптимизация алгоритма с учетом знания о числах Фибоначи

Обнаружение того, что первое из двух чисел Фибоначи на уровне с ростом номера уровня располагается все ближе к началу уровня и понимание, что на уровне при обнаружении числа фибоначи искать далее максимум уже не требуется, подтолкнуло меня к следующему алгориму:

1. Определить к какому уровню дерева относится введенный в программу порядковый номер

2. Вычислить поизицию возникновения первого числа Фибоначи на уроне

3. Если введенный порядковый номер больше или равен порядковому номеру с числом Фибоначи на уровне, возвращать число фибоначи как результат выполнения программы.

4. Если введенный порядовый номер меньше позиции с числом Фибоначи, то начинать поиск максимума начиная с начала уровня игнорируя предыдущие уровни и числа с четными порядковыми номерами.

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

Как вы поняли, я вновь вернулся мыслями к поиску максимума методом перебора. Но теперь я существенно ограничил область поиска. И я даже написал оптимизированную функцию определяющую порядковый номер первого числа Фибоначи на уровне:

function calculateNOfFirstLocalMax(int $k): int
{
    $mask = (int) ((1 << $k) / 3);

    return ($mask << 1) | 1;
}

Эта функция работает для всех начиная с первого.

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

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

Я написал программу с учетом всего вышесказанного и она работала примерно на шесть порядков быстрее. Но что такое шесть порядков для ? Это всего лишь снижение количества обрабатываемых значений до . Помните мой комментарий, что я оставил в Spoj, к задаче? А именно, что даже практически пустой цикл написанный на PHP с таким количеством итераций занимает на моем не самом слабом компьютере 14 секунд! Конечно, для некоторых вводных моя программа выдавала результат вообще без задержек. Но в некоторых случаях она требовала несколько дней на выполнение.

Может я латентный фанат решений методом перебора? Эта мысль стоила мне нескольких часов самобичевания.

Но подождите! А, что если сократить число потенциальных локальных максимумов? Я ведь еще не умею высчитывать порядковые номера чисел, которые я раскрасил синими в диаграмме. Без подобного знания мне приходится искать максимум среди всех чисел с нечетным порядковым номером!

Анализ потенциальных максимумов

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

В действительности я рассматривал диаграмму с 16-ю уровнями. Но нет здравого смысла в том, чтобы выкладывать такого монстра в статью. Хабр обрезает изображение даже если я сгенерирую диаграмму всего с восемью уровнями, так как каждый уровень тут примерно в два раза больше предыдущего. К слову, если рассмотреть предыдущую диаграмму, то там каждый следующий уровень содержал узлов в количестве равном сумме узлов всех предыдущих уровней.

Началась долгая работа. Я выписывал цепочки веток, раскладывал их различными методами ища закономерности в бинарном представлении порядковых номеров их чисел. не буду публиковать все свои выкладки. Просто скажу - все было зря. Не помог даже Oeis, в котором я раз за разом искал совпадения со своими выкладками. Это было, как бы сказать мягко, грустно. Я даже затеял поиск в Интернете геометрического смысла fusc последовательности в надежде найти подсказку. Не нашел. Если кто-то осведомлен больше меня в этой теме - буду рад вашим комментариям!

В какой-то момент я даже ударился в идею отобразить радиально это бинарное дерево:

Получилось красиво, не спорю! Но для меня - бесполезно.

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

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

Как видите, это уже не бинарное дерево. Возможно у вас возник вопрос о том как я смог сохранить древовидную структуру. Тут все объясняется свойством нумерации в бинарных деревьях. Если бинарное дерево построено на непрерывной числовой последовательности, то порядковый номер узла уже содержит в себе знание о всех его родителях. Например у узла, чей порядковый номер пять родителей: число битов минус 1. Причем мы знаем, что каждый бит содержит информацию о том по какому пуйти можно пройти к родителю. Последний бит: 0, а значит, чтобы пройти к родителю нужно подняться вверх и вправо. Предпоследний бит: 1. Значит к следующему родителю путь лежит вверх и влево. Так можно проложить путь от узла к его корневому узлу. Почему-то я часто натыкался в Интернете на информацию, что это свойство именно fusc последовательности, отображенной в виде бинарного дерева, хотя очевидно, что все подобные деревья обладают таким свойством. Не удивлюсь, если есть какой-то механизм индексации основанный на данном свойстве. Пользуясь тем, что могу определелить всех родителей узла, я находил в цепи родителей ближайшего родителя-рекордсмена и уже его назначал родителем узлу в данной диаграмме. Как видите, это привело, что некоторые узлы имеют больше двух дочерних узлов.

Диаграмма показывает, что у нас есть несколько семейств или другими словами поддеревьев рекордсменов. И каждое семейство начиная с 12-го уровня плодится визуально предсказуемо.

Я решил вывести всех рекордсменов 19-го уровня в таблицу и найти закономерности в поведении каждой семьи:

Как ни удивительно, самой полезной оказалась последняя колонка. В ней четко прослеживается 5 числовых шаблонов:

Не буду забрасывать вас скриншотами. Скажу лишь, что эти шаблоны сохраняются от уровня к уровню и легко вычисляются для всех нечетных уровней. Меняется только количество рекордсменов в большую сторону с каждым новым уровнем. Для четных уровней шаблоны отличаются. И их всего три.

Есть еще одна причина почему я не стал закидывать вас скриншотами и таблицами. Все же знают анкдот:

— Как вы стали миллионером?
— Сначала я купил мешок картошки. Продал его, купил два мешка. Продал их, купил четыре...
— А потом?
— А потом умерла моя тётя и оставила мне наследство.

Так и в моем случае. Я решил проверить свое разложение порядковых номеров рекордсменов и нашел последовательность Distinct elements of fusc seq, которая содержала все числа и моей диаграммы рекордсменов. Сама эта последовательность ничего не дает - у меня и так есть эти числа, их ведь и предсказывать для каждого уровня надо уметь. Но в ней есть ссылка на одну любопытную статью: Record-Setters in the Stern Sequence. И что вы думали? Эта статья лишила меня возможности сделать научное открытие в математике! Кто бы сомневался в том, что все придумали до меня. Еще бы не придумали за полторы то сотни лет. С одной стороны я уже устал погружаться в такую непривычную для меня сферу заний как анализ числовых последовательностий. С другой - я же уже был почти у финиша.

Именно эта статья вводит понятие все того же злополучноего , который определяет уровень дерева. Но в статье речь про деревья не ведется. В ней - это количество битов в бинарном представлении порядкового номера числа в fusc последовательности. Статья прям на блюдечке преподносит формулы вычисления рекордсменов для каждого :

Возмущение (round 2)

Хабрахабр тренирует наши нервы тем что для ввода формул предоставляет поле в 25 символов? Да еще и не полностью поддерживается синтаксис LaTex. На ровном месте убил время на форматирование формул!

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

Тут видим все те же пять шаблонов для нечетных . И три шаблона для четных.

А вот и функции, которыми я реализовал эти формулы:

/**
 * @return int[]
 */
function recordSettersForEvenK(int $k): array
{
    $result = [];

    $n = $k / 2;
    for ($a = 0; $a <= $n - 3; $a++) {
        $result[] = bindec('100' . str_repeat('10', $a) . '0' . str_repeat('10', $n - 3 - $a) . '11');
    }
    for ($b = 1; $b <= $n >> 1; $b++) {
        $result[] = bindec(str_repeat('10', $b) . '0' . str_repeat('10', $n - $b - 1) . '1');
    }
    $result[] = bindec(str_repeat('10', $n - 1) . '11');

    sort($result);

    return $result;
}

/**
 * @return int[]
 */
function recordSettersForOddK(int $k): array
{
    $result = [];

    $n = ($k - 1) / 2;

    $result[] = bindec('1000' . str_repeat('10', $n - 2) . '1');
    $result[] = bindec('100100' . str_repeat('10', $n - 4) . '011');

    for ($b = 1; $b <= ($n >> 1) - 1; $b++) {
        $result[] = bindec('100' . str_repeat('10', $b) . '0' . str_repeat('10', $n - 2 - $b) . '1');
    }
    for ($a = 0; $a <= $n - 2; $a++) {
        $result[] = bindec(str_repeat('10', $a + 1) . '0' . str_repeat('10', $n - 2 - $a) . '11');
    }
    $result[] = bindec(str_repeat('10', $n) . '1');

    sort($result);

    return $result;
}

Далее решение задачи становится тривиальным: вычисляем к какому уровню () относится введенный порядковый номер, вычисляем порядковые номера рекордсменов для этого уровня и определяем в какой позиции относительно них находится введенный порядковый номер, и тем самым определяем порядковый номер нужного рекордсмена. Далее используем ранее приведенную функцию вычисления элементов fusc последовательности по их порядковому номеру и распечатываем результат.

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

Мой комментарий под задачей изменился на:

I took the challenge to write a solution to the problem in PHP. I was naive. A regular loop of 10**9 iterations with a minimum of arithmetic takes me 14 seconds.I will rewrite my solution in C later.

Edit:
Found a solution that can be implemented even in PHP.

My result: 0.17 seconds; 26M memory

If someone is still trying to find a speed-optimised solution, you will need a mathematical analysis of the fusc sequence: ‘Record-Setters in the Stern Sequence’

Эпилог

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

Помогли ли мне мои диаграммы и деревья в частности? Да - так я обнаружил семейства веток и пришел к правильным выводам. Не думаю, что с моим познанием математики смог бы прочитать и понять статью о рекорсменах fusc последовательности, если бы до этого уже сам не пришел к тем же выводам, что и автор той статьи.

Итоговые впечатления от задачи положительные. Я не силен в матанализе, что обернулось для меня многими открытиями. Например я открыл для себя oeis.org, о котором я и не подозревал. Уверен, что такое хранилище последовательностей мне пригодится еще не раз. Надеюсь, что и вам прочтение моей статьи принесло только удовольствие.