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
Re: The tower of Hanoi and the sum of its pieces is related to the primes.
Posted: Nov 18, 2012 8:20 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.

I left out an important fact below that 203 disk
stack is term 203 if you refer back to the original
generating series above. Also 223 stack is term # 223.

> Checking if a 203 disk stack is prime you have to
> first
> find the divisor.
> 2^203 - 204 =
> 1.2855504354071922204335696738729300820177623950262342
> 682410804e+61
> Then --
> 2^204 - 205 =
> 2.5711008708143844408671393477458601640355247900524685
> 364821811e+61
>
> 2.5711008708143844408671393477458601640355247900524685
> 364821811e+61
> /
> 1.2855504354071922204335696738729300820177623950262342
> 682410804e+61
> =
> 2.0000000000000000000000000000000000000000000000000000
> 0000001579090...
> cf =
> [2:633276076555267103661856982203413833506286894101593
> 23558673,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.347997333357531989733350754350981533681857221127028
> 6240551805124384e+67
> 2^224 -225
> =2.695994666715063979466701508701963067363714442254057
> 2481103610248991e+67
> 2.0000000000000000000000000000000000000000000000000000
> 000000000000165430594320658993803...
> cf =
> [2,604483109128938111988049665628242840216079471357411
> 93903819753921,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