Все задачи
Средне Решено: 0 Процент решений: 0%

Самая длинная последовательность Коллатца

Найдите начальное число, не превосходящее предела, с самой длинной последовательностью Коллатца.

Чему вы научитесь

  • Строить последовательность Коллатца
  • Кешировать результаты, чтобы не повторять работу
  • Выбирать наименьшее значение при равенстве

Условие

Для любого положительного n правило Коллатца задаёт следующий член как n / 2, если n чётное, и как 3n + 1, если n нечётное. Последовательность заканчивается, когда доходит до 1. Для 6 она такая: 6, 3, 10, 5, 16, 8, 4, 2, 1, то есть девять членов. Среди всех начальных чисел от 1 до limit найдите то, у которого членов больше всего.

Реализуйте longest_collatz_chain(limit).

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

Входные данные

limit: наибольшее начальное число, которое нужно проверить.

Выходные данные

Верните начальное число, последовательность которого содержит больше всего членов (считая само начальное число и завершающую 1). Если таких чисел несколько, верните наименьшее.

Ограничения

1 ≤ limit ≤ 100 000

Примеры

Пример 1
Ввод:
limit = 6

Ожидаемый вывод:
expected = 6
Ввод:
long long limit = 6;

Ожидаемый вывод:
long long expected = 6;
Ввод:
long limit = 6;

Ожидаемый вывод:
long expected = 6;

Пояснение

Длины последовательностей для чисел от 1 до 6: 1, 2, 8, 3, 6 и 9 членов, поэтому ответ 6.

Пример 2
Ввод:
limit = 10

Ожидаемый вывод:
expected = 9
Ввод:
long long limit = 10;

Ожидаемый вывод:
long long expected = 9;
Ввод:
long limit = 10;

Ожидаемый вывод:
long expected = 9;

Пояснение

9 даёт 20 членов (9, 28, 14, 7, ...), больше, чем любое другое начальное число до 10, поэтому ответ 9.

Как подступиться

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

Подсказка 1

Сначала научитесь считать члены одной последовательности, включая начальное число и 1.

Подсказка 2

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

Подсказка 3

Заменяйте лучшее начальное число, только если длина строго больше.

Ожидаемая сложность

время O(limit × average new steps), доп. память O(limit)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

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