home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11295 < prev    next >
Encoding:
Text File  |  1992-09-11  |  4.1 KB  |  123 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!elroy.jpl.nasa.gov!sdd.hp.com!news.cs.indiana.edu!news.orst.edu!pmontgom
  3. From: pmontgom@math.orst.edu (Peter Montgomery)
  4. Subject: Re: Prime Factor Numbers
  5. Message-ID: <BuFtz8.7En@news.orst.edu>
  6. Sender: usenet@news.orst.edu (Usenet News admin)
  7. Nntp-Posting-Host: ilanga.math.orst.edu
  8. Organization: Oregon State University Math Department
  9. References: <1992Sep8.040307.6288@cronkite.ocis.temple.edu> <flash.716162039@ellison>
  10. Date: Fri, 11 Sep 1992 23:45:06 GMT
  11. Lines: 110
  12.  
  13. In article <flash.716162039@ellison> flash@unx.sas.com (Gordon Keener) writes:
  14. >In <1992Sep8.040307.6288@cronkite.ocis.temple.edu> 
  15. >sklar@picasso.ocis.temple.edu (Dave Sklar) writes:
  16. >
  17. >
  18. >>      Here's something I was thinking about.  Take a number, n, and write
  19. >>down its prime factors [Excluding n and 1] from left to right, forming a new number.  Repeat.
  20. >>      When you get to a prime number, you end. Let's call the function
  21. >>d(n).  So, d(1001)=71113, d(5)=d(2)=d(11)=[Define something here, say]0.
  22. >>      Does every number eventually go to a prime, and then 0?
  23. >
  24. >Well, I did a (slow) little shell script using the poor UNIX "factor" program,
  25. >and discovered that every n < 150000 either goes to a prime or exceeds 10^15,
  26. >at which point factor can't deal with it. Quite a few of them did overflow,
  27. >though, (including 1001; the smallest number that did was 91), so I would
  28. >guess that some of them will keep growing to infinity. I did notice quite a
  29. >few 12- and 13-digit primes, though, so not all sequences terminate in small
  30. >primes.
  31.  
  32.         Modulo any typos I made while concatenating factors,
  33. it terminates on a 40-digit prime (actually a probable prime)
  34. if one starts at n = 91.  Only one number in the sequence (2331)
  35. has a repeated factor.
  36.  
  37. 91
  38.     7 13
  39. 713
  40.     23 31
  41. 2331
  42.     3 3 7 37
  43. 3737
  44.     37 101
  45. 37101
  46.     3 83 149
  47. 383149
  48.     13 29473
  49. 1329473
  50.     109 12197
  51. 10912197
  52.     3 283 12853
  53. 328312853
  54.     11 29846623
  55. 1129846623
  56.     3 73 5159117
  57. 3735159117
  58.     3 1245053039
  59. 31245053039
  60.     173 977 184859
  61. 173977184859
  62.     3 29 317 6308321
  63. 3293176308321
  64.     3 19 269 2417 88861
  65. 319269241788861
  66.     3 7 13 251 23869 195203
  67. 371325123869195203
  68.     127 86477 33810375857
  69. 1278647733810375857
  70.     166562203 7676698019
  71. 1665622037676698019
  72.     3 3 17 42715741 254857303
  73. 331742715741254857303
  74.     11 197 7753 1101571 17925043
  75. 111977753110157117925043
  76.     71711 1802653 866231224721
  77. 717111802653866231224721
  78.     47 59 131 1974084348402854767
  79. 47591311974084348402854767
  80.     61 179 269 1000651 16192350561847
  81. 61179269100065116192350561847
  82.     43 104647799 13595830142605429571
  83. 4310464779913595830142605429571
  84.     421 1179979043 8676962308986514957
  85. 42111799790438676962308986514957
  86.     7 73 2178619 37826975301590901045673
  87. 773217861937826975301590901045673
  88.     29 1039 73897 31009841 11198554951734379
  89. 291039738973100984111198554951734379
  90.     5497123 52944010707619419123639502873
  91. 549712352944010707619419123639502873
  92.     17 107510547289 300770683219476756223921
  93. 17107510547289300770683219476756223921
  94.     745741 22940284290778300738035349372981
  95. 74574122940284290778300738035349372981
  96.     3810577 19570296818640402956901471361253
  97. 381057719570296818640402956901471361253
  98.     3 232690001463497 545873217834379601755583
  99. 3232690001463497545873217834379601755583
  100.     3232690001463497545873217834379601755583
  101.  
  102.         Let a_k be the k-th term in the sequence beginning
  103. with a_0 = n.  Heuristically, a large integer N has about
  104. ln(ln(N)) prime factors.  We expect a_{k+1} to be about
  105. ln(ln(N))/2 decimal digits longer than a_k (and it could
  106. be shorter if some factors of a_k are repeated).  That is,
  107.  
  108.                           ln(ln(a_k))/2
  109.         a_{k+1} ~ a_k * 10            
  110.         ln(a_{k+1}) ~ ln(a_k) + 1.15 * ln(ln(a_k))
  111.         ln(a_k) ~ 1.15 k ln (k)
  112.  
  113.         The probability that a particular N is prime is about
  114. 1/ln(N).  We expect a_k to be prime with probability
  115. about 1/(1.15 k ln(k)).  Since sum 1/(k ln (k)) diverges,
  116. this heuristic argument predicts we will always encounter a prime.
  117.  
  118. -- 
  119.         Peter L. Montgomery              Internet: pmontgom@math.orst.edu
  120.         Dept. of Mathematics, Oregon State Univ, Corvallis, OR 97331-4605 USA
  121. ``Who do you trust?''  Those whom I trust know English spelling and grammar.
  122. Our economy needs more business, not more Bushiness.
  123.