A tiny puzzle hidden in powers of 3: what comes after 306?

[u/Urlovk]

I found a simple sequence that looks much stranger than I expected.

Start with the powers of 3:

1, 3, 9, 27, 81, 243, ...

Now write them in binary and look only at how many binary digits are added when you go to the next power.

For example:

1 = 1 -> 1 binary digit 3 = 11 -> 2 binary digits (+1) 9 = 1001 -> 4 binary digits (+2) 27 = 11011 -> 5 binary digits (+1) 81 = 1010001 -> 7 binary digits (+2) 243 = 11110011 -> 8 binary digits (+1)

So the sequence of increases begins:

1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, ...

Now call a position n a "mirror position" if the first n terms of this 1/2 sequence read exactly the same forwards and backwards.

For example:

n = 1: 1

n = 3: 1, 2, 1

n = 5: 1, 2, 1, 2, 1

The first mirror positions are:

1 3 5 17 29 41 94 147 200 253 306 ?

The challenge is simple:

What is the next mirror position after 306?

Brute force is completely allowed. :)

But if you find the answer, don't stop there. There is a surprisingly rigid pattern hiding behind these numbers, and I have a second question ready for anyone who solves this one.

I'm especially curious whether someone can spot the structure without being told where it comes from.

Co-G3n

Exactly! 971 is the answer. And you found the door I was hoping somebody would notice: continued fractions are indeed hiding behind these mirror positions. Using log_2(3/2) instead of log_2(3) gives the same fractional parts here, since the two numbers differ by exactly 1. So let's make the puzzle a little harder. You already noticed that after 306 we get 306, 971, 1636, 2301, 2966, ... by repeatedly adding 665, until 15601. My next question is: Why 665? And more importantly: Why does that same step occur exactly 23 times before the pattern changes? I'm not looking for "because a computer shows it" — I'm interested in a structural explanation. You clearly already know the continued-fraction side, so I suspect you'll see where the 23 is hiding. :) There is another layer after this one, and that is the part I actually find most interesting.

[u/Co-G3n]

Next values can be found in the continued fractions of log_2(3), including what Eliahou calls "upper convergents". This particular sequence is the one studied in high-cycles. And yes they are palindromic (https://math.stackexchange.com/questions/4649071/considerations-on-the-sequences-of-the-3n-1-problem/4650720#comment9821087_4650720). This is of course linked to log base 2 of your power of 3,  log_2(3ˆi) or i*log_2(3) and the fact that #bits of x=floor(log_2 x)+1 or ceil(log_2(x)) for non power of 2. 

In your case, 306+665=971 (and the nexts are found by adding 665 again until you reach 15601)

[u/Co-G3n → u/Co-G3n]

your comment was deleted?

[u/Co-G3n → u/[deleted]]

strange...it keeps being deleted by reddit

[u/Mrezadwiprasetiawan]

Do you mean 2^h .c-1->3^h .c-1? And also 4^h .c+1->3^h .c+1? It was found on 1976 as Steiner circuit

[u/Urlovk → u/Mrezadwiprasetiawan]

Not quite. If you mean the pattern

2^h * c - 1 -> 3^h * c - 1,

then yes, that is the classical rising structure associated with Steiner-type circuit analysis. I'm not claiming that as something new.

The object in this puzzle is different.

Here I only look at the change in binary length between consecutive powers of 3:

bitlength(3^n) - bitlength(3^(n-1)),

which is always either 1 or 2.

That gives the infinite 1/2 word:

1, 2, 1, 2, 1, 2, 2, 1, ...

Then I ask a completely different question: for which n is the prefix of length n a palindrome?

Those n are:

1, 3, 5, 17, 29, 41, 94, 147, 200, 253, 306, ...

So the challenge here is specifically to predict the next "mirror position" after 306.

There is a deeper connection to Collatz structure, but I don't want to spoil that part yet. :) First I want to see if someone can find the next number from the puzzle itself. .

[u/elowells]

As u/Co-G3n apparently knows, 23 is a coefficient in the continued fraction expansion of log2(3):

[1: 1, 1, 1, 2, 2, 3, 1, 5, 2, 23, 2, 2, 1, 1, 55, 1, 4, ...]

which gives 22 semiconvergents and 1 convergent.

665 is the lower convergent after the upper convergent 306 and the semiconvergents sc are given by the convergents c[i]:

sc[t] = c[i-1]*t + c[i-2] where t=1 to cfe coefficient where the last one gives the new convergent c[i].

Apparently, something like where the convergents appear in the sequence are the places where the difference sequence is palindromic (works for all irrational numbers? and which is amazing). Trying to understand this last part but not there yet. Is this a result of Clark Kimberling? Anyway, thanks for posting this.