home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10495 < prev    next >
Encoding:
Text File  |  1992-08-21  |  2.8 KB  |  98 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!wri!news
  3. From: roach@bikini.wri.com (Kelly Roach)
  4. Subject: u(v^n)w prime puzzle SOLUTION
  5. Message-ID: <1992Aug21.220719.16092@wri.com>
  6. Sender: news@wri.com
  7. Nntp-Posting-Host: bikini.wri.com
  8. Organization: Wolfram Research, Inc.
  9. Date: Fri, 21 Aug 1992 22:07:19 GMT
  10. Lines: 86
  11.  
  12.  
  13.  
  14.  
  15.       Prove or disprove:  There are three non-empty
  16.       strings of digits u,v,w such that all the
  17.       numbers in
  18.            L = {u(v^n)w | n is a natural number}
  19.              = {uw, uvw, uvvw, uvvvw, uvvvvw, ...}
  20.       are prime numbers.
  21.  
  22.  
  23.              THE SOLUTION
  24.  
  25.      I've seen some good solutions to my puzzle already,
  26. but as promised, I now present the solution I said I would
  27. post on Friday (today).
  28.      Let a=|v|=length of v, b=|w|=length of w.  Then
  29.  
  30.      u(v^n)w = u*10^(a*n+b) + v*Sum[10^(a*i+b),{i,0,n-1}] + w
  31.  
  32. Fermat's Little Theorem says
  33.      
  34.      c^(p-1) = 1 (mod p)
  35.  
  36. if p is prime and (c,p)=1.  If uw is not a prime, there
  37. is not much to prove.  So, let p=uw be prime.  If
  38. (p-1) | n, then by F.L.T.
  39.  
  40.      u*10^(a*n+b) + w = u*10^b + w = uw = 0 (mod p)
  41.  
  42. All that remains is to arrange things so that
  43.  
  44.      Sum[10^(a*i+b),{i,0,n-1}] = 0 (mod p)
  45.  
  46. Prime number p does not divide 10 because uw has at least
  47. 2 digits.  Hence
  48.  
  49.      10^(a*i+b) (mod p)
  50.  
  51. is a periodic function of i.  The period divides p-1
  52. and that means that if p(p-1) | n, then each residue
  53. appearing in the list
  54.  
  55.      10^b, 10^(a+b), ..., 10^(a*(n-1)+b)     (mod p)
  56.  
  57. appears a multiple of p times.  Consequently, it is
  58. sufficient to let n=p(p-1) to get p | u(v^n)w.  Obviously
  59. u(v^n)w > p=uw.
  60.  
  61.               QED
  62.  
  63.  
  64.      It is possible to make n smaller in my proof
  65. by using p*ord(10,p) instead.  Also, Arthur Rubin
  66. suggests using p=uvw and n=p.  Then
  67.  
  68.      u*10^(a*n+b) + vw = u*10^(a+b) + vw = uvw = 0 (mod p)
  69.  
  70.      Sum[10^(a*i+b),{i,1,n-1}]
  71.      = (10^(a*(p-1))-1)/(10^a-1) * 10^(a+b)    
  72.  
  73. The Sum is divisible by p since p > 10^a-1 and F.L.T.
  74. applies to 10^(a*(p-1))-1.
  75.      There were two other nice solutions posted which
  76. reduced the problem to an instance of the more general
  77. problem of whether
  78.  
  79.      x_{n+1} = a*x_n + b
  80.  
  81. could always be prime and then solved that problem.
  82.      About the u(v^n)w puzzle itself:  It arises from
  83. the problem of investigating whether any regular language
  84. can generate only prime numbers.  There is a pumping
  85. lemma for the regular languages which basically reduces
  86. the problem down to the u(v^n)w puzzle which I posted
  87. to sci.math.  So, everyone who solved my puzzle also
  88. just proved that no finite state machine can accept
  89. an infinite language consisting of only prime numbers.
  90. If you generalize the proof a bit, you can also prove
  91. that u(v^n)w(x^n)z with |vx| != 0 cannot generate all
  92. prime numbers either.  This shows that no infinite
  93. context-free language can contain only prime numbers.
  94. I'm pretty sure these are old results.
  95.  
  96.  
  97.  
  98.