## A Modified Collatz sequence

### Problem 277

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

`a _{n+1}` =

`a`/3 if

_{n}`a`is divisible by 3. We shall denote this as a large downward step, "D".

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

`a`+ 2)/3 if

_{n}`a`divided by 3 gives a remainder of 1. We shall denote this as an upward step, "U".

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

`a`- 1)/3 if

_{n}`a`divided by 3 gives a remainder of 2. We shall denote this as a small downward step, "d".

_{n}
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"?