1
$\begingroup$

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?

$\endgroup$
10
  • 3
    $\begingroup$ 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? $\endgroup$ – Jyrki Lahtonen Feb 10 '20 at 16:09
  • $\begingroup$ Actually, the sequence of fifth digits should be periodic since it depends only on $3^n\pmod {2^5}$. $\endgroup$ – richrow Feb 10 '20 at 16:09
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Feb 10 '20 at 16:11
  • $\begingroup$ @JyrkiLahtonen thanks, i get it, i need to study on residue classes $\endgroup$ – Pruthviraj Feb 10 '20 at 16:16
  • 1
    $\begingroup$ $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. $\endgroup$ – Gottfried Helms Feb 11 '20 at 18:36
0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.