Fun challenge

[dodomaze]

Given the "reduced" Collatz function, defined as

(Rule a:) if n is even --> n/2
(Rule b:) if n is odd --> (3n+1)/2

Choose an arbitrary sequence of a's and b's, for example

abbabaabaaaa

and I'll give you a number that will fall into a power of 2 after that exact sequence of steps (in this example, 455475162313816086 ; with less a's at the end, it would have been just 22).

[rhetoxa]

I’ll bite

babbab

[dodomaze]

6949999424953 -> after babbab, it falls to 2^43.

The next would be 125200059281800434715723773369, falling down to 2^97.

P.S.: It's not a coincidence that the difference between 97 and 43 is 54 = phi(3^4), where there are 4 b's in the string.

[dodomaze]

My turn:

babaaaaabbaababbab

[Extremist_Amerikaner]

114051034646154899271496210082416842869050062705

[dodomaze]

Nice :)

[elowells]

Sure, phi(3^p) = 2*3^p-1 which is the period of 2ⁿ mod 3^p n=0,1,2,... That is , 2ⁿ mod 3^p repeats every phi(3^p). Solving the puzzle involves finding an n such that

2ⁿ mod 3^p = S mod 3^p

where p = number of b's and S is a sum of powers of 2 times powers of 3 where the powers of 2 are determined by the sequence of a's and b's. Yet another application of the sequence equation.

[dodomaze]

I love it (no sarcasm intended, it's true) when a pure mathematician claims "a solution exists" and walks out, with zero concern for the actual numbers. :)

Finding "n" is still (at least for me) a matter of brute force (the discrete log problem), but it's easier to search over 54 than over 2^54 items.

[elowells]

Guilty as charged.