I recently stumbled onto the Collatz Conjecture, which states that any n iterated through the algorithm below will eventually be reduced to 1:
Given an integer n, then either divide n by 2 if n is even or multiply n by 3 and add 1 if n is odd.
Example: Let n=42, which is even so divide by 2 and n = 21, which is odd so 3*21+1 = 64, which is even so n = 64/2=32, which is even so n = 32/2=16, which is even so n = 16/2=8, which is even so n = 8/2=4, which is even so n = 4/2=2, which is even so n = 2/2=1, which generates the following:
42->21->64->32->16->8->4->2->1.
To me the most curious thing about it is the fact that shortly before it reaches 1, it hits a bunch of consecutive powers of 2.
And so does the (n+1)/2 row of the exponentiation table of Z
n. In fact,
42->21->64->32->16->8->4->2->1 vaguely resembles all unique consecutive powers of 43 mod 85, namely 43->64->32->16->8->4->2->1
It might just be a wishful coincidence but it feels like powers of 2 are being generated backwards in some finite field(s) somehow as this algorithm hits an odd integer.
Update: 42->21->64->32->16->8->4->2->1 are the last few terms of the sequence of unique powers of (n+1)/2 for n = 107 since (107+1)/2 = 54 then all unique consecutive powers of 54 mod 107 are:
54,27,67,87,97,102,51,79,93,100,50,25,66,33,70,35,71,89,98,49,78,39,73,90,45,76,38,19,63,85,96,48,24,12,6,3,55,81,94,47,77,92,46,23,65,86,43,75,91,99,103,105,106,53,80,40,20,10,5,56,28,14,7,57,82,41,74,37,72,36,18,9,58,29,68,34,17,62,31,69,88,44,22,11,59,83,95,101,104,52,26,13,60,30,15,61,84,
42,21,64,32,16,8,4,2,1
Another interesting observation is that 107 is in fact
a tough prime. Below is an implementation of the algorithm for generating powers of 2 backwards.
On a slightly different note, to me this is very interesting as I recently made the following observation that I haven't publicly posted about because I haven't been able to prove it in connection to a different problem.
Claim: Given any odd integer n and k = (n-1)/2 then 3k + 1 = k mod n
Proof: (3((n-1)/2) + 1) mod n
= (2(n-1)/2) mod n + ((n-1)/2) mod n + 1 mod n
= (n-1) mod n + ((n-1)/2) mod n + 1 mod n
= n mod n + (-1) mod n + ((n-1)/2) mod n + 1 mod n
= ((n-1)/2) mod n + (1-1) mod n //
since n mod n = 0 mod n
=
((n-1)/2) mod n
.'.
Similarly, it can be shown that g
iven any odd integer n and k = (n+1)/2 then 3k + 1 = k+2 mod n
I already discussed how unique consecutive powers of 2 mod n are essentially all unique consecutive powers of (n+1)/2 backwards and I also conjectured that every consecutive even power of (n-1)/2 is equal to every consecutive even power of (n+1)/2 and the sum of every odd power of (n-1)/2 and (n+1)/2 is equal to n, at least when n is the product of distinct odd primes.
I'll try to illustrate what I mean with an example.
Example: Let n = 35 so (n-1)/2 = 17 and (n+1)/2 = 18
The 17th and 18th rows of the exponentiation table of Z
35 are circled below
Note that 17
2 mod 35 = 18
2 mod 35 = 9 mod 35
Also 17
4 mod 35 = 18
4 mod 35 = 11 mod 35
and so on for all even powers of 17 and 18 whereas
17
3 + 18
3 mod 35 = 35
and 17
5 + 18
5 mod 35 = 35
and so on for all odd powers of 17 and 18 mod 35
I always imagine that there is some kind of an underlying cycle that connects the (n+1)/2 and (n-1)/2 rows of the exponentiation table of Z
n but this might be just wishful thinking to put it mildly.