Autogenerated numbers 2

Although this is a follow up to an earlier post, it can be read independently.

Repeatedly squaring the number 5, we get the following.

5^1 =                        5
5^2 =                       25
5^4 =                      625
5^8 =                   390625
5^16 =            152587890625
5^32 = 23283064365386962890625

There is a pattern here, which becomes more evident if the table is truncated to a triangle:

5^1 =                        5
5^2 =                       25
5^4 =                      625
5^8 =                  ...0625
5^16 =                ...90625
5^32 =               ...890625
5^64 =              ...2890625
5^128 =            ...12890625
5^256 =           ...212890625

What other digits, besides 5, have this property? None in the decimal system (ignoring the trivial 0 and 1). But the same pattern is shown by 3 in base 6 (below, the exponent is still in base 10, for clarity).

3^1 =                        3
3^2 =                       13
3^4 =                      213
3^8 =                  ...0213
3^16 =                ...50213
3^32 =               ...350213
3^64 =              ...1350213

and so on.

Here is a proof that the pattern appears when the base is 2 mod 4 (except 2), and the starting digit is half the base.

Let ${x}$ be the starting digit, and ${b=2x}$ the base. The claim is that ${x^{2^k}\equiv x^{2^{k-1}} \bmod b^k}$ for all ${k=1,2,\dots}$ .

Base of induction: ${x^2-x = x(x-1)}$ is divisible by ${x}$ and also by ${2}$ , since ${x-1}$ is even. Hence it is divisible by ${2x=b}$ .

Step of induction: Suppose ${x^{2^k} - x^{2^{k-1}}}$ is divisible by ${b^k}$ . Then
${x^{2^{k+1}} - x^{2^{k}} = (x^{2^k} - x^{2^{k-1}})(x^{2^k} + x^{2^{k-1}})}$
The second factor is divisible by ${x}$ and also by ${2}$ , being the sum of two odd numbers. So, it is divisible by ${b}$ . Since the first factor is divisible by ${b^k}$ , the claim follows: ${x^{2^{k+1}} - x^{2^{k}} }$ is divisible by ${b^{k+1}}$ .

So that was easy. The part I can’t prove is the converse. Numerical evidence strongly suggests that ${b=2\bmod 4}$ , ${x=b/2}$
is also the necessary condition for the triangular pattern to appear.

Autogenerated numbers 2

Related

Leave a Reply Cancel reply