From: roach@bikini.wri.com (Kelly Roach)
Subject: Re: Big primes puzzles
Keywords: Ackermann function/Puzzle/Primes
Organization: Wolfram Research, Inc.
Date: Sat, 15 Aug 1992 01:04:48 GMT



     A solution to the puzzle concerning the Ackerman
function which was posted in article  
<1992Aug13.050021.737@magnus.acs.ohio-state.edu>  
wjcastre@magnus.acs.ohio-state.edu (W.Jose Castrellon G.): 


     >=================================================
     >A(0,m) = m+1
     >A(n+1,0) = A(n,1)
     >A(n+1,m+1) = A(n, A(n+1,m))
     >=================================================

     >=================================================
     >1. Find a closed form for A(c,n), c in {1,2,3,4}
     >2. Decide whether A(4,4) is a prime or not.
     >=================================================
    
    
SOLUTION (SHORT VERSION):


     A[1,m] == m+2
     A[2,m] == 2*m+3
     A[3,m] == 2^(m+3)-3

     A[4,m] == 2^2^...2^16-3
               \______/
                 m 2's

     A[4,4] == 2^2^2^2^16-3

     2 | 2^2^16-2
     3 | 2^2^2^16-4
     12 | 2^2^2^16-4
     13 | 2^2^2^2^16-2^4
     13 | A[4,4]
     A[4,4] is not prime.


SOLUTION (LONG VERSION WITH COMMENTARY):


     We get

     A[1,0] = A[0,1] = 1+1 = 2
     A[1,m+1] = A[0,A[1,m]] = A[1,m]+1, hence
     A[1,m] = 2,3,4,5,6,... for m=0,1,2,3,4
     A[1,m] = m+2
    
     A[2,0] = A[1,1] = 1+2 = 3
     A[2,m+1] = A[1,A[2,m]] = A[2,m]+2, hence
     A[2,m] = 3,5,7,9,11,... for m=0,1,2,3,4
     A[2,m] = 2*m+3
    
     A[3,0] = A[2,1] = 2*1+3 = 5
     A[3,m+1] = A[2,A[3,m]] = 2*A[3,m]+3, hence
     A[3,m] = 5,13,29,61,127,... for m=0,1,2,3,4
     A[3,m] = 2^(m+3)-3
    
     A[4,0] = A[3,1] = 2^(1+3)-3 = 13
     A[4,m+1] = A[3,A[4,m]] = 2^(A[4,m]+3)-3, hence
     A[4,1] = 2^(13+3)-3 = 2^16-3
     A[4,2] = 2^(2^16-3+3)-3 = 2^2^16-3
     A[4,3] = 2^(2^2^16-3+3)-3 = 2^2^2^16-3
     A[4,m] = 2^2^...2^16-3
              \______/
	        m 2's

Rigorous proof of the last lines of the four groups of
equations above requires mathematical induction.  These
four proofs are easy to do.  Discovery of the formulas
to be proven is what is important and there should be
enough information above to suggest to the reader how
we arrived at them.


     >=================================================
     >2. Decide whether A(4,4) is a prime or not.
     >=================================================


     This is an application of Fermat's Little Theorem
which says that

     a^(p-1) == 1 (mod p)

if p is prime and (a,p)==1.  By part 1 of the puzzle
we get

     A[4,4] == 2^2^2^2^16-3

Now if A[4,4] is not prime (as we hope since proving
A[4,4] prime seems nearly hopeless) then

     2^2^2^2^16 = 3 (mod p)

for some prime p.  If 3 is a power of 2 (mod p), then

     3 = 2^x (mod p)

for some 0<=x<=p-1.  So,

     2^2^2^2^16 = 3 = 2^x (mod p) and
     2^(2^2^2^16-x) = 1 (mod p)

if (p-1) divides 2^2^2^16-x.  Recursing downward, we see
that if q is a prime dividing (p-1), we need to have

     2^2^2^16 = x (mod q)

Perhaps the reader now sees the pattern.  Each recursion
will stip off a "2^".
     Trying out the values p=2,3,5,7,11 and determining
their success or failure to prove p | A[4,4] using our
method above will be left to the reader.  We skip straight
to p=13 which happens to work.  We get

     2^2^2^2^16 = 3 = 2^4 (mod 13)

So we need

     2^2^2^16 = 4 (mod 12)

Hence we need 2^2^2^16 = 4 = 2^2 (mod 3).  We are now in
good position to work backwards.

     2^2^16-2 = 0 (mod 2)     is clear
    
     2^(2^2^16-2) = 1 (mod 3)   by the previous line and F.L.T.
                                with p=3

     2^2^2^16 = 2^2 = 4 (mod 3)   by the previous line
    
     2^2^2^16 = 2^2 = 4 (mod 12)   by the previous line and observing
                                   4 divides both 2^2^2^16 and 4

     2^(2^2^2^16-4) = 1 (mod 13)   by the previous line and F.L.T.
                                   with p=13

     2^2^2^2^16 = 2^4 = 3 (mod 13)    by the previous line
    
     A[4,4] = 0 (mod 13)     by the previous line and our result
                             A[4,4]=2^2^2^2^16-3

Thus A[4,4] is divisible by 13.  Since A[4,4] is bigger
than 13, A[4,4] is not prime.
     The method we used can be used to prove non-primality
of many other large numbers.

Newsgroups: sci.math