# Observation on digit in base $2$ for $3^n$

Below table shows, representation in base $$2$$ for $$3^n$$

$$3^{00}=000000000000000000001\\3^{01}=000000000000000000011\\3^{02}=000000000000000001001\\3^{03}=000000000000000011011\\3^{04}=000000000000001010001\\3^{05}=000000000000011110011\\3^{06}=000000000001011011001\\3^{07}=000000000100010001011\\3^{08}=000000001100110100001\\3^{09}=000000100110011100011\\3^{10}=000001110011010101001\\3^{11}=000101011001111111011\\3^{12}=010000001101111110001\\3^{13}=110000101001111010011$$

Observation on column from right side

First column shows only $$\{1\}$$ in repeated pattern, May we call 'prefect symmetry'

Second column shows $$\{0,1\}$$ in repeated pattern

Third column shows $$\{0\}$$ in repeated pattern

Fourth column shows $$\{0,0,1,1\}$$ in repeated pattern

But from fifth column don't show repeated pattern

Question

How to show, 5th column and greater than 5th column don't have repeated pattern?

• For $n$th column there will be a pattern of length $2^{n-2}$. This is because the order of $3$ in the multiplicative group of residue classes modulo $2^n$ is $2^{n-2}$ (assuming $n\ge3$). May be you simply haven't run the sequence for long enough to see it? – Jyrki Lahtonen Feb 10 '20 at 16:09
• Actually, the sequence of fifth digits should be periodic since it depends only on $3^n\pmod {2^5}$. – richrow Feb 10 '20 at 16:09
• Your data suggests (didn't check) that in the fifth column you will see the pattern $0,0,0,1,1,1,1,0$ repeating. – Jyrki Lahtonen Feb 10 '20 at 16:11
• @JyrkiLahtonen thanks, i get it, i need to study on residue classes – Pruthviraj Feb 10 '20 at 16:16
• $3^2$ has one leading $1$, $3^3$ had two leading $1$, $3^4$ has one leading $1$, $3^5$ has $4$ leading $1$, and so on. But after that, $3^n$ has seemingly always less than $n-1$ consecutive leading $1$ and it seems, as if there occur true randomness in the occurence of the position of the first zero in the bitstring. The underlying question is here, how good $3^n$ and $2^{n+a}$ can be approximated like: exists one $3^n$ which is $(2^n-1)\cdot 2^a +r$ with $r<2^a$. Reformulated there is an open problem behind this but I tried to find a pattern or some argument by the empirical observations. – Gottfried Helms Feb 11 '20 at 18:36

All the columns have a repeated pattern.

• For the fifth column from the right, the repeating pattern is "$$0,0,0,1,1,1,1,0$$".
• For the sixth column from the right, the repeating pattern is "$$0,0,0,0,0,1,0,0,1,1,1,1,1,0,1,1$$".
• For the seventh column from the right, the repeating pattern is "$$0,0,0,0,1,1,1,0,0,1,0,1,1,1,1,1,1,1,1,1,0,0,0,1,1,0,1,0,0,0,0,0$$".

We can prove that every column is periodic. We do this by showing that the last $$m$$ columns are jointly periodic for every $$m \geq 1$$. It should be clear that if each of the last $$m$$ columns is periodic with periods $$p_1, p_2, \dots, p_m$$, that they are jointly periodic with period $$\mathrm{lcm}(p_1,p_2, \dots,p_m)$$, where $$\mathrm{lcm}$$ is the least common multiple. Also, if the last $$m$$ columns are jointly periodic, each column is periodic (with period dividing the joint period).

The last $$m$$ columns are the least nonnegative member of the congruence class $$3^n$$ modulo $$2^m$$. There are only $$2^m$$ such congruence classes. Consequently, there are only $$2^m$$ possible different values in the last $$m$$ columns and so after $$2^m+1$$ powers of $$3$$ there is at least one repetition in the last $$m$$ columns. If a value in the last $$m$$ columns is ever repeated, say $$3^a$$ and $$3^b$$ have the same last $$m$$ columns, then the sequence of values between $$3^a$$ and $$3^b$$ repeats forever because $$3^a\cdot 3$$ has the same last $$m$$ columns as $$3^b \cdot 3$$, and so on.

This argument allows an initial portion of the powers of $$3$$ to not be repeated, followed by a forever repeating part. We now show that the initial, not repeated portion is empty. Note that $$3$$ and $$2^m$$ share no prime factors. This means $$\gcd(3,2^m) = 1$$. By the extended Euclidean algorithm, we can find integers $$u$$ and $$v$$ such that $$3 u + 2^m v = 1$$. This also says $$3u$$ is congruent to $$1 = 3^0$$ modulo $$2^m$$. Suppose $$3^a$$ and $$3^b$$, $$0 < a < b$$ are the first pair of powers of $$3$$ that repeat modulo $$2^m$$. Then $$3^{a-1} = 3^a \cdot u$$ modulo $$2^m$$ is congruent to $$3^{b-1} = 3^b \cdot u$$ modulo $$2^m$$ (by contradiction, we're done, but the constructive version is nearly done also...) and we can walk both of these back to $$3^0$$ congruent to $$3^{b-a}$$. Thus, $$3^0$$ is the first member of the first period.

It shouldn't be too difficult to realize that $$a^k \pmod n$$ will eventually always have a repeating pattern as there are only $$n$$ values of $$\pmod n$$ there must be a $$a^k\equiv a^r\pmod n$$ with $$r > k$$. And when that occurs $$a^{k+i} \equiv a^{r+i}$$ for all terms there after.

It's not so obvious (but still true nonetheless) that if $$\gcd(a, n) =1$$ then if $$a^k \equiv a^r$$ then $$a^{k-1} \equiv a^{r-1}$$ so that pattern begins "at the beginning with" $$a^0 \equiv a^m \equiv 1$$.

So the 5th column has pattern but you just don't have enough samples. We are looking at $$a^k \equiv \pmod 2^5$$ so the pattern is at most $$32$$

Eulers theorem says that $$\phi(2^k) = 2^{k-1}$$ and $$3^{2^{k-1}}\equiv 1$$ so the last $$5$$ digits have a repeating pattern of at most $$16$$. and if you look the last five digits of $$3^{0}$$ are $$00001$$ and the last five digits of $$3^{16}$$ are ... well you didn't go far enough.

$$3^{16} = 101001000011010111010\color{blue}{00001}$$.

But the pattern doesn't have to be $$16$$ long. It could be something that divides $$16$$. ANd in this case $$3^{8} = 0000000011001101\color{blue}{00001}$$ and the pattern is eight long.

And the pattern is $$0,0,0,1,1,1,1,0$$

Contrary to your belief, all columns have a repeated pattern. The period can be longer, this is why you don't see it.

For any $$a,b,n$$ integer,

$$a^{n+1}\bmod b=(a\,a^n)\bmod b=a(a^n\bmod b)\bmod b,$$ which is a simple recurrence between $$a^{n+1}\bmod b$$ and $$a^n\bmod b$$. Thus $$a^n\bmod b$$ must be a periodic sequence of period at most $$b$$.

In your case, $$b=2^m$$ and you only look at the first bit.

If we consider the fifth column, $$2^m=32$$, the period is $$1,3,9,27,17,19,25,11$$, with length $$8$$ (check that $$3\cdot11\bmod32=1$$), with the leading bits $$0,0,0,1,1,1,1,0$$.

For the sixth column, modulo $$64$$: $$1, 3, 9, 27, 17, 51, 25, 11, 33, 35, 41, 59, 49, 19, 57, 43$$, length $$16$$ (and $$3\cdot43\bmod64=1$$).