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

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

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

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

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

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

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

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

Чему равно наименьшее значение a1 > 1015, которому соответствует последовательность шагов, начинающаяся с "UDDDUdddDDUDDddDdDddDDUDDdUUDd"?

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