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} = \, \,\, \frac {a_n} 3 \quad$ 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”?

This problem involves iterating a sequence of transformations, each of which are determined by rules provided in the problem’s prompt. However, because we are given a specific sequence of transformations to perform (“UDDDUdddDDUDDddDdDddDDUDDdUUDd”), we are able to use a backwards method to find the minimum starting value, $a_1$, which generates this sequence.

The reverse transformations would be defined as follows:

For every U in the sequence, the reverse transformation would be:
$a_{n+1}=3a_n−2 \,\,$ if the result is divisible by $4$; if not, we cannot reverse this step.

For every D in the sequence, the backward transformation would be:
$a_{n+1}=3a_n \,$

For d, the backward transformation is
$a_{n+1}=3a_n+1 \,\,$ if the result is divisible by $2$; if not, we cannot reverse this step.

Now that we have these reverse transformations, we can proceed to apply them in reverse order on the “termination” point $a_n = 1$.

Our sequence of transformations is “UDDDUdddDDUDDddDdDddDDUDDdUUDd”. Apply these in reverse (starting from “dDUUdDDUddDdDddDUDDDUdddDDD”) and continue through the sequence until obtaining a valid $a_1$ that’s greater than $10^{15}$.

During each backward transformation, to keep $a_1$ as small as possible, we will choose the smallest possible value that the reverse transformation will allow.

Step-by-step, this looks like:

1. From “d”, $a_1 =3(1)+1 =4$
2. From “D”, $a_{new} =3(4) = 12$
3. From “D”, $a_{new}=3(12)=36$
…etc.

Keep applying the reverse transformations until reaching $a_1 > 10^{15}$.

After these calculations, you should find that the smallest $a_1 > 10^{15}$ that follows the specified sequence is $a_1 = 1125977393124310$.

More Answers: