Problem 277

A Modified Collatz sequence

A modified Collatz sequence of integers is obtained from a starting value a_{1} in the following way:

`a _{n+1}` =

`a _{n+1}` = (4

`a _{n+1}` = (2

The sequence terminates when some `a _{n}` = 1.

Given any integer, we can list out the sequence of steps.

For instance if `a`_{1}=231, then the sequence {`a _{n}`}={231,77,51,17,11,7,10,14,9,3,1} corresponds to the steps "DdDddUUdDD".

Of course, there are other sequences that begin with that same sequence "DdDddUUdDD....".

For instance, if `a`_{1}=1004064, then the sequence is DdDddUUdDDDdUDUUUdDdUUDDDUdDD.

In fact, 1004064 is the smallest possible `a`_{1} 10^{6} that begins with the sequence DdDddUUdDD.

What is the smallest `a`_{1} 10^{15} that begins with the sequence "UDDDUdddDDUDDddDdDddDDUDDdUUDd"?

**
These problems are part of
Project Euler
and are licensed under
CC BY-NC-SA 2.0 UK
**