This question doesn't support checking answers.
277. A Modified Collatz sequence

Publish Date: 2/6/2010, 1:00:00 AM

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

$a_{n + 1} = \frac{a_{n}}{3}$ if $a_{n}$ is divisible by $3$ . We shall denote this as a large downward step, "D".

$a_{n + 1} = \frac{4 a_{n} + 2}{3}$ if $a_{n}$ divided by $3$ gives a remainder of $1$ . We shall denote this as an upward step, "U".

$a_{n + 1} = \frac{2 a_{n} - 1}{3}$ if $a_{n}$ divided by $3$ gives a remainder of $2$ . We shall denote this as a small downward step, "d".

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"?