Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
The tower of Hanoi and the sum of its pieces is related to the primes.
Replies:
1
Last Post:
Nov 18, 2012 8:20 AM



dan73
Posts:
468
From:
ct
Registered:
6/14/08


The tower of Hanoi and the sum of its pieces is related to the primes.
Posted:
Nov 17, 2012 9:13 AM


The tower of Hanoi and the sum of its pieces 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^21 3 2^31 4 2^41 5 2^51 6 etc.
Now to emphasize the value of each disk the diameter of the smallest disk and each larger disk. disk #ndia.area for each disk disk #1 = 1.128379167...  1 disk #2 = 1.5957691216... 2 disk #3 = 1.9544100476... 3 disk #4 = 2.2567583341... 4 etc..
Too find the total sum for each (n) stack of disks is t(n) a triangle number. Now to sum each piece as it is moved in the process of 2^n1 moves there are many pieces with the same area that are added many times depending on the size of (n).
To find this sum  disks # sum in tower 1 disk = 2^23 =1 2 disk = 2^34 =4 3 disk = 2^45 =11 4 disk = 2^56 =26 5 disk = 2^67 =57 6 disk = 2^78 =120 7 disk = 2^89 =247 etc. 1,4,11,26,57,120,247... sequence A000295 in OEIS.
Now to find out if the number of odd disks are prime then say checking a (3) disk stack 11/4 = 2.75 = cf =[2:1,3] Where 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 7 disk stack as prime  247/120 = 2.0583333333... = cf =[2:17,7]  so (7) is prime.
Checked all odd disks stacks from here on except 0(mod 3 or 5) stacks. It identifies all primes and composites.
Checking if a 203 disk stack is prime you have to first find the divisor. 2^203  204 = 1.2855504354071922204335696738729300820177623950262342682410804e+61 Then  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?
2^223 224 =1.3479973333575319897333507543509815336818572211270286240551805124384e+67 2^224 225 =2.6959946667150639794667015087019630673637144422540572481103610248991e+67 2.0000000000000000000000000000000000000000000000000000000000000000165430594320658993803... cf = [2,60448310912893811198804966562824284021607947135741193903819753921,223] 223 is prime
I always had a hunch that the tower of Hanoi might be related to the primes!
Dan



