Гипотеза Коллатца связанное интервью

Это был вопрос интервью, который, кажется, связан с Проектом Эйлера Проблема 14

Гипотеза Коллатца гласит, что если вы сделаете следующее

If n is even, replace n by n/2.
If n is odd, replace n by 3n+1.

, вы в конечном итоге получите 1.

Например , 5 -> 16 -> 8 -> 4 -> 2 -> 1

Предполагая, что гипотеза верна, каждое число имеет длину цепочки: количество шагов, необходимых для достижения 1. (Длина цепочки из 1 равно 0).

Теперь задаче задаются натуральные числа n, m и натуральное число k, дайте алгоритм, чтобы найти все числа от 1 до n, такие, что длина цепочки этих чисел

Простой способ - перебрать его и объединить с мемоизацией.

Интервьюер сказал, что существует алгоритм времени O (S), где S - количество чисел, которые нам нужно вывести.

Кто-нибудь знает, что это может быть?