Cycles of nth digit in powers of n.

[Daniel Mondot]

After misunderstanding the last thread from Ali Sada about "Ordered Cycles of the Last Digit Under Repeated Multiplication", and going down my own rabbit hole...

I discovered this:

if you keep multiplying n by itself (or looking at the powers of n in order), you see that the last digit makes a cycle going through 1, 2 or 4 values.

Now if you look at the second digit, or the last 2 digits, the cycle is 1, 2, 4, 5, 10, or 20. But it's always a multiple of the last digit cycle. 

With each new digit added, the cycle becomes larger and larger, but the cycle for the last n digits is always a multiple of the cycle for the last n-1 digits.

So, if instead you take the ratio of the cycle for n digits to the cycle for n-1 digits, you always get 1, 2, 5 or 10, which makes sense because they are the factors of 10, and we operate in base 10.

So we get this:

2:  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
3:  4  5  5  5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
4:  2  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
5:  1  1  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2
6:  1  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
7:  4  1  5  5  5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
8:  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
9:  2  5  5  5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
11:  1 10  5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
12:  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
13:  4  5  5  5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
14:  2  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
15:  1  2  1  1  1  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2
16:  1  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5

Now if we look at the values of n for which, from the 2-digit cycle to infinity, the ratio of a cycle to the previous cycle is always 5, we get these:

2, 4, 6, 8, 12, 14, 16, 22, 28, 34, 36, etc...

74 for example is not included because the first ratio is a 1 not a 5.

74:  2  1  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5

And this end-up to be exactly A376508, which is obtained completely differently.

A376508 is the "Natural numbers whose iterated squaring modulo 100 eventually enters the 4-cycle 16, 56, 36, 96."

Someone might be able to prove that the 2 sequences are identical...

Daniel.

[Daniel Mondot]

PS: in case someone wonders, I checked over 10000 terms between this sequence and A376508, and they match.

[Elijah Beregovsky]

Daniel, if I understand your procedure correctly, it is not very surprising that it results in A376508, because it closely matches the sequence’s definition. “Iterated squaring” means you “keep multiplying n by itself”, “modulo 100” means “take the last two decimal digits”. The only nontrivial part is the cycle itself. To prove that the sequences are indeed identical you’d need to prove the cycle 16, 56, 36, 96 is the only cycle that results in your property. Notice that the cycle members are all divisible by 4, so really your question is not about decimal digits, but quinary. What you are asking boils down to “What is the cycle length of 16 under repeated squaring mod 25, 125, 625 etc.?” 

The proposition 3.1.(6) of https://arxiv.org/pdf/1101.3482 seems to answer this question nicely. In your case k=2, p=5, x=16. Order of 16 mod 5^m is 4*5^(m-1). ρ=5^(m-1), therefore gcd(ρ,ord16)=5^(m-1). Collecting all of this we get that the cycle length you seek is c_2,5^m (16) = order of 2 mod 5^(m-1), which happens to be 4*5^(m-2). Thus you can easily see that indeed if you divide the cycle length mod 5^m by cycle length mod 5^(m-1) you always get 5.

Now we plug all the other residues mod 25 into that formula and see that the other ones don’t give the correct cycle length. By looking at row 25 of A216327 we can see that indeed our 4 values are the only ones that have order 5 mod 25. (Technically, now we have to look at residues of 100 that are not divisible by 4, but I’m lazy and leave it to you) 

Elijah

[Elijah Beregovsky]

Correction: I’m a dummy and order of 16 mod 5^m is 5^(m-1). Thankfully, that changes nothing in the following logic

[Elijah Beregovsky]

Now we plug all the other residues mod 25 into that formula and see that the other ones don’t give the correct cycle length. By looking at row 25 of A216327 we can see that indeed our 4 values are the only ones that have order 5 mod 25. (Technically, now we have t

Correction: ignore this, my logic here is bad 😞

[Elijah Beregovsky]

The theorems in section 4 say when squaring mod 5^m there is one cycle of length 4*5^(m-1) — the one you’re working with, one cycle of length 4*5^(m-2), one of length 4*5^(m-3) etc. I think, the numbers that end up in the 4-cycle mod 25 all end up in the 20-cycle mod 125, 100-cycle mod 625 etc. 

This paper gives us the structure for arbitrary power mod arbitrary n. In our case n is 2^m*5^m. And if I am not miscalculating that means there should be two of each cycle length > 1. I don’t really understand how to use this structure to fully prove the equivalence, but I have a hunch that knowing it is enough

Elijah