Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
dan73

Posts: 465
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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.