Задача 277
Модифицированная последовательность Коллатца

Модифицированную последовательность Коллатца, состояющую из целых чисел, получают из начального значения a_(1) следующим образом:

a_(n+1) = a_(n)/3 если a_(n) делится на 3 без остатка. Обозначим это событие большим шагом вниз, "D".

a_(n+1) = (4a_(n) + 2)/3 если, при делении на 3, a_(n) дает в остатке 1. Обозначим это событие шагом вверх, "U".

a_(n+1) = (2a_(n) - 1)/3 если, при делении на 3, a_(n) дает в остатке 2. Обозначим это событие малым шагом вниз, "d".

Последовательность завершается на элементе a_(n) = 1.

Для любого заданного целого числа мы можем перечислить последовательность всех шагов.
Например, если a_(1)=231, то последовательности {a_(n)}={231,77,51,17,11,7,10,14,9,3,1} соответствуют шаги "DdDddUUdDD".

Разумеется, существуют другие последовательности, начало которых совпадает с упомянутой выше "DdDddUUdDD....".
например, если a_(1)=1004064, то получится следующая последовательность шагов DdDddUUdDDDdUDUUUdDdUUDDDUdDD.
Между прочим, 1004064 является наименьшим возможным значением a_(1) > 10^(6), соответствующая которому последовательность шагов начинается с DdDddUUdDD.

Чему равно наименьшее значение a_(1) > 10^(15), которому соответствует последовательность шагов, начинающаяся с "UDDDUdddDDUDDddDdDddDDUDDdUUDd"?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net