home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10296 < prev    next >
Encoding:
Text File  |  1992-08-14  |  4.4 KB  |  165 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!wri!news
  3. From: roach@bikini.wri.com (Kelly Roach)
  4. Subject: Re: Big primes puzzles
  5. Message-ID: <1992Aug15.010448.9747@wri.com>
  6. Keywords: Ackermann function/Puzzle/Primes
  7. Sender: news@wri.com
  8. Nntp-Posting-Host: bikini.wri.com
  9. Organization: Wolfram Research, Inc.
  10. References: <1992Aug13.050021.737@magnus.acs.ohio-state.edu>
  11. Date: Sat, 15 Aug 1992 01:04:48 GMT
  12. Lines: 151
  13.  
  14.  
  15.  
  16.      A solution to the puzzle concerning the Ackerman
  17. function which was posted in article  
  18. <1992Aug13.050021.737@magnus.acs.ohio-state.edu>  
  19. wjcastre@magnus.acs.ohio-state.edu (W.Jose Castrellon G.): 
  20.  
  21.  
  22.      >=================================================
  23.      >A(0,m) = m+1
  24.      >A(n+1,0) = A(n,1)
  25.      >A(n+1,m+1) = A(n, A(n+1,m))
  26.      >=================================================
  27.  
  28.      >=================================================
  29.      >1. Find a closed form for A(c,n), c in {1,2,3,4}
  30.      >2. Decide whether A(4,4) is a prime or not.
  31.      >=================================================
  32.     
  33.     
  34. SOLUTION (SHORT VERSION):
  35.  
  36.  
  37.      A[1,m] == m+2
  38.      A[2,m] == 2*m+3
  39.      A[3,m] == 2^(m+3)-3
  40.  
  41.      A[4,m] == 2^2^...2^16-3
  42.                \______/
  43.                  m 2's
  44.  
  45.      A[4,4] == 2^2^2^2^16-3
  46.  
  47.      2 | 2^2^16-2
  48.      3 | 2^2^2^16-4
  49.      12 | 2^2^2^16-4
  50.      13 | 2^2^2^2^16-2^4
  51.      13 | A[4,4]
  52.      A[4,4] is not prime.
  53.  
  54.  
  55. SOLUTION (LONG VERSION WITH COMMENTARY):
  56.  
  57.  
  58.      We get
  59.  
  60.      A[1,0] = A[0,1] = 1+1 = 2
  61.      A[1,m+1] = A[0,A[1,m]] = A[1,m]+1, hence
  62.      A[1,m] = 2,3,4,5,6,... for m=0,1,2,3,4
  63.      A[1,m] = m+2
  64.     
  65.      A[2,0] = A[1,1] = 1+2 = 3
  66.      A[2,m+1] = A[1,A[2,m]] = A[2,m]+2, hence
  67.      A[2,m] = 3,5,7,9,11,... for m=0,1,2,3,4
  68.      A[2,m] = 2*m+3
  69.     
  70.      A[3,0] = A[2,1] = 2*1+3 = 5
  71.      A[3,m+1] = A[2,A[3,m]] = 2*A[3,m]+3, hence
  72.      A[3,m] = 5,13,29,61,127,... for m=0,1,2,3,4
  73.      A[3,m] = 2^(m+3)-3
  74.     
  75.      A[4,0] = A[3,1] = 2^(1+3)-3 = 13
  76.      A[4,m+1] = A[3,A[4,m]] = 2^(A[4,m]+3)-3, hence
  77.      A[4,1] = 2^(13+3)-3 = 2^16-3
  78.      A[4,2] = 2^(2^16-3+3)-3 = 2^2^16-3
  79.      A[4,3] = 2^(2^2^16-3+3)-3 = 2^2^2^16-3
  80.      A[4,m] = 2^2^...2^16-3
  81.               \______/
  82.             m 2's
  83.  
  84. Rigorous proof of the last lines of the four groups of
  85. equations above requires mathematical induction.  These
  86. four proofs are easy to do.  Discovery of the formulas
  87. to be proven is what is important and there should be
  88. enough information above to suggest to the reader how
  89. we arrived at them.
  90.  
  91.  
  92.      >=================================================
  93.      >2. Decide whether A(4,4) is a prime or not.
  94.      >=================================================
  95.  
  96.  
  97.      This is an application of Fermat's Little Theorem
  98. which says that
  99.  
  100.      a^(p-1) == 1 (mod p)
  101.  
  102. if p is prime and (a,p)==1.  By part 1 of the puzzle
  103. we get
  104.  
  105.      A[4,4] == 2^2^2^2^16-3
  106.  
  107. Now if A[4,4] is not prime (as we hope since proving
  108. A[4,4] prime seems nearly hopeless) then
  109.  
  110.      2^2^2^2^16 = 3 (mod p)
  111.  
  112. for some prime p.  If 3 is a power of 2 (mod p), then
  113.  
  114.      3 = 2^x (mod p)
  115.  
  116. for some 0<=x<=p-1.  So,
  117.  
  118.      2^2^2^2^16 = 3 = 2^x (mod p) and
  119.      2^(2^2^2^16-x) = 1 (mod p)
  120.  
  121. if (p-1) divides 2^2^2^16-x.  Recursing downward, we see
  122. that if q is a prime dividing (p-1), we need to have
  123.  
  124.      2^2^2^16 = x (mod q)
  125.  
  126. Perhaps the reader now sees the pattern.  Each recursion
  127. will stip off a "2^".
  128.      Trying out the values p=2,3,5,7,11 and determining
  129. their success or failure to prove p | A[4,4] using our
  130. method above will be left to the reader.  We skip straight
  131. to p=13 which happens to work.  We get
  132.  
  133.      2^2^2^2^16 = 3 = 2^4 (mod 13)
  134.  
  135. So we need
  136.  
  137.      2^2^2^16 = 4 (mod 12)
  138.  
  139. Hence we need 2^2^2^16 = 4 = 2^2 (mod 3).  We are now in
  140. good position to work backwards.
  141.  
  142.      2^2^16-2 = 0 (mod 2)     is clear
  143.     
  144.      2^(2^2^16-2) = 1 (mod 3)   by the previous line and F.L.T.
  145.                                 with p=3
  146.  
  147.      2^2^2^16 = 2^2 = 4 (mod 3)   by the previous line
  148.     
  149.      2^2^2^16 = 2^2 = 4 (mod 12)   by the previous line and observing
  150.                                    4 divides both 2^2^2^16 and 4
  151.  
  152.      2^(2^2^2^16-4) = 1 (mod 13)   by the previous line and F.L.T.
  153.                                    with p=13
  154.  
  155.      2^2^2^2^16 = 2^4 = 3 (mod 13)    by the previous line
  156.     
  157.      A[4,4] = 0 (mod 13)     by the previous line and our result
  158.                              A[4,4]=2^2^2^2^16-3
  159.  
  160. Thus A[4,4] is divisible by 13.  Since A[4,4] is bigger
  161. than 13, A[4,4] is not prime.
  162.      The method we used can be used to prove non-primality
  163. of many other large numbers.
  164.  
  165.