Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

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

 Messages: [ Previous | Next ]
 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^2-1
3 -------------2^3-1
4 -------------2^4-1
5 -------------2^5-1
6 etc.

Now to emphasize the value of each disk the
diameter of the smallest disk and each larger disk.
disk #n------dia.-----------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^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 ---
disks # -------sum
in tower
1 disk = 2^2-3 =1
2 disk = 2^3-4 =4
3 disk = 2^4-5 =11
4 disk = 2^5-6 =26
5 disk = 2^6-7 =57
6 disk = 2^7-8 =120
7 disk = 2^8-9 =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

Date Subject Author
11/17/12 dan73
11/18/12 dan73