[seqfan] Proving a number to be prime using the Tower of Hanoi.
Daniel Joyce
hlauk.h.bogart at gmail.com
Tue Oct 14 17:17:23 CEST 2014
The tower of Hanoi and the sum of its pieces in
all the moves it takes to move to a different peg
is related to the primes and a sequence in OEIS.
Rehashing the tower of Hanoi --
Three pegs where a stack of (n) number of disks
of incremental size have to be moved completely
to another peg one at a time to another peg
without putting a larger disk on a smaller disk.
The correct number of moves for (n) number
of disks is --
(n) disks ----correct # of moves
2 -------------2^2-1
3 -------------2^3-1
4 -------------2^4-1
5 -------------2^5-1
6 etc.
Now to emphasize the value (area) of each disk the
diameter of the smallest disk and each larger disk.
disk #n------dia.----------------area for each disk
disk #1 = 1.12837916709551257389... = 1 in area
disk #2 = 1.59576912160573071175... = 2 in area
disk #3 = 1.95441004761167968634... = 3 in area
disk #4 = 2.25675833419102514779... = 4 in area
etc..
Now we have to find the total sum of each stack
moves where some pieces are added a multiple of times
for each stack in their final placement on the pegs.
To sum each piece as it is moved in the
process of 2^n-1 moves there are many pieces with the
same area that are added many times depending
on the size of (n).
To find this sum of total area moved ---
(n) # of
disks on peg = sum of all moves for each disk stack--
1 disk = 2^2-3 =1 = total sum of area moved to different peg.
2 disk = 2^3-4 =4 = total sum of area moved to different peg.
3 disk = 2^4-5 =11 = total sum of area moved to different peg.
4 disk = 2^5-6 =26 = total sum of area moved to different peg.
5 disk = 2^6-7 =57 = total sum of area moved to different peg.
6 disk = 2^7-8 =120 = total sum of area moved to different peg.
7 disk = 2^8-9 =247 = total sum of area moved to different peg.
8 disk = 2^9-10 =502 = total sum of area moved to different peg.
9 disk = 2^10-11 =1013 = total sum of area moved to different peg.
10 disk = 2^11-12 =2036 = total sum of area moved to different peg.
11 disk = 2^12-13 =4083 = total sum of area moved to different peg.
12 disk = 2^13-14 =8178 = total sum of area moved to different peg.
13 disk = 2^14-15 =16369 =total sum of area moved to different peg.
14 disk = 2^15-16 =32752 =total sum of area moved to different peg.
15 disk = 2^16-17 =65519 =total sum of area moved to different peg.
16 disk = 2^17-18 =131054 =total sum of area moved to different peg.
17 disk = 2^18-19 =262125 =total sum of area moved to different peg.
18 disk = 2^19-20 =524268 =total sum of area moved to different peg.
19 disk = 2^20-21 =1048555 =total sum of area moved to different peg.
20 disk = 2^21-22 =2097130 =total sum of area moved to different peg.
21 disk = 2^22-23 =4194281 =total sum of area moved to different peg.
22 disk = 2^23-24 =8388584 =total sum of area moved to different peg.
23 disk = 2^24-25 =16777191 =total sum of area moved to different peg.
etc. =
Producing the sequence A000295 that makes no reference to the
Tower of Hanoi.
1,4,11,26,57,120,247,502,1013,2036,4083,8178,16369,32752,65519,131054,262125...
This sequence A000295 in OEIS which does not mention a connection
to the tower of Hanoi but a connected sequence A000225 does refer
to the Tower of Hanoi but not in the context I propose.
There is no reference of the Tower in A000295.
Interesting enough this sequence above is the actual
total sum area of each piece moves in the Tower of Hanoi for
any tower (n) number of disks.
Checking the primality of any odd integer stack.
Now to find out if the number of odd disks in any tower are prime
then say checking a (3) disk stack and picking up the
previous sum from the (2) disk stack-- 11/4 = 2.75 =
cf =[2:1,3]
Where if the stack number is prime the cf will always have just
3 terms and the last term will equal the # of odd disks to be prime.
In the above case (3). So (3) is prime.
Checking the 5 disk stack as prime ---
So taking the previous sum of total moves and dividing into
the 5 stack of total moves sum ---57/26 = 2.19230769230769230769... = cf =
[2:5,5] ---
so (5) is prime.
Checked all odd disks stacks from here on except
0(mod 3 or 5) stacks. It identifies all odd primes and
odd composites.
Checking the 7 disk stack as prime ---
247/120 = 2.0583333333... = cf =[2:17,7] ---
so (7) is prime.
For checking larger primes up too 8317,
first set calculator for at least 5000 digits accuracy.
Checking if a 203 disk stack and that number stack is prime you have to
first
find the denominator or previous area sum from stack 202---
2^203 - 204 =
1.2855504354071922204335696738729300820177623950262342682410804e+61
Then the numerator or number to be tested for primality 203 --
2^204 - 205 =
2.5711008708143844408671393477458601640355247900524685364821811e+61
2.5711008708143844408671393477458601640355247900524685364821811e+61
/
1.2855504354071922204335696738729300820177623950262342682410804e+61
=
2.00000000000000000000000000000000000000000000000000000000001579090...
cf =
[2:63327607655526710366185698220341383350628689410159323558673,1,10,3,1,1,2]
203 is not prime because there are more then 3 terms in the cf.
Is a 223 disk stack prime?
Using the sums list and then calculating the cf---
2^223 -224
=1.3479973333575319897333507543509815336818572211270286240551805124384e+67
2^224 -225
=2.6959946667150639794667015087019630673637144422540572481103610248991e+67
(2^224 -225)/(2^223 -224) =
2.0000000000000000000000000000000000000000000000000000000000000000165430594320658993803...
cf =
[2:60448310912893811198804966562824284021607947135741193903819753921,223]
223 is the third term in the cf and also the target prime 223.
Check if 379 is prime --
2^379 - 380 =
1.231312693637327475383720003129487931408741852202045208373384168882678805359287831606695820465153613775207124696708e+114
2^380 - 381 =
2.462625387274654950767440006258975862817483704404090416746768337765357610718575663213391640930307227550414249393795e+114
(2^380 - 381)/(2^379 - 380) =
2.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000307801586029641937798673698131128321359
cf=
[2:3248846157354426056421424810368042035379266100796953056394153479901527190921603777326374196477977872757802439833,379]
Only 3 positions in the Cf and the last position is the target prime.
So 379 is prime
I always had a hunch that the tower of Hanoi might be
related to the primes and the proof is in the sum of each
target (potential prime) stack divided by previous
area sum = a cf that will prove or disprove a prime.
Dan
More information about the SeqFan
mailing list