From: pmontgom@math.orst.edu (Peter Montgomery)
Subject: Re: Prime Factor Numbers
Organization: Oregon State University Math Department
Date: Fri, 11 Sep 1992 23:45:06 GMT

In article <flash.716162039@ellison> flash@unx.sas.com (Gordon Keener) writes:
>In <1992Sep8.040307.6288@cronkite.ocis.temple.edu> 
>sklar@picasso.ocis.temple.edu (Dave Sklar) writes:
>
>
>>      Here's something I was thinking about.  Take a number, n, and write
>>down its prime factors [Excluding n and 1] from left to right, forming a new number.  Repeat.
>>      When you get to a prime number, you end. Let's call the function
>>d(n).  So, d(1001)=71113, d(5)=d(2)=d(11)=[Define something here, say]0.
>>      Does every number eventually go to a prime, and then 0?
>
>Well, I did a (slow) little shell script using the poor UNIX "factor" program,
>and discovered that every n < 150000 either goes to a prime or exceeds 10^15,
>at which point factor can't deal with it. Quite a few of them did overflow,
>though, (including 1001; the smallest number that did was 91), so I would
>guess that some of them will keep growing to infinity. I did notice quite a
>few 12- and 13-digit primes, though, so not all sequences terminate in small
>primes.

        Modulo any typos I made while concatenating factors,
it terminates on a 40-digit prime (actually a probable prime)
if one starts at n = 91.  Only one number in the sequence (2331)
has a repeated factor.

91
	7 13
713
	23 31
2331
	3 3 7 37
3737
	37 101
37101
	3 83 149
383149
	13 29473
1329473
	109 12197
10912197
	3 283 12853
328312853
	11 29846623
1129846623
	3 73 5159117
3735159117
	3 1245053039
31245053039
	173 977 184859
173977184859
	3 29 317 6308321
3293176308321
	3 19 269 2417 88861
319269241788861
	3 7 13 251 23869 195203
371325123869195203
	127 86477 33810375857
1278647733810375857
	166562203 7676698019
1665622037676698019
	3 3 17 42715741 254857303
331742715741254857303
	11 197 7753 1101571 17925043
111977753110157117925043
	71711 1802653 866231224721
717111802653866231224721
	47 59 131 1974084348402854767
47591311974084348402854767
	61 179 269 1000651 16192350561847
61179269100065116192350561847
	43 104647799 13595830142605429571
4310464779913595830142605429571
	421 1179979043 8676962308986514957
42111799790438676962308986514957
	7 73 2178619 37826975301590901045673
773217861937826975301590901045673
	29 1039 73897 31009841 11198554951734379
291039738973100984111198554951734379
	5497123 52944010707619419123639502873
549712352944010707619419123639502873
	17 107510547289 300770683219476756223921
17107510547289300770683219476756223921
	745741 22940284290778300738035349372981
74574122940284290778300738035349372981
	3810577 19570296818640402956901471361253
381057719570296818640402956901471361253
	3 232690001463497 545873217834379601755583
3232690001463497545873217834379601755583
	3232690001463497545873217834379601755583

        Let a_k be the k-th term in the sequence beginning
with a_0 = n.  Heuristically, a large integer N has about
ln(ln(N)) prime factors.  We expect a_{k+1} to be about
ln(ln(N))/2 decimal digits longer than a_k (and it could
be shorter if some factors of a_k are repeated).  That is,

                          ln(ln(a_k))/2
        a_{k+1} ~ a_k * 10            
        ln(a_{k+1}) ~ ln(a_k) + 1.15 * ln(ln(a_k))
        ln(a_k) ~ 1.15 k ln (k)

        The probability that a particular N is prime is about
1/ln(N).  We expect a_k to be prime with probability
about 1/(1.15 k ln(k)).  Since sum 1/(k ln (k)) diverges,
this heuristic argument predicts we will always encounter a prime.

-- 
        Peter L. Montgomery              Internet: pmontgom@math.orst.edu
        Dept. of Mathematics, Oregon State Univ, Corvallis, OR 97331-4605 USA
``Who do you trust?''  Those whom I trust know English spelling and grammar.
Our economy needs more business, not more Bushiness.
Newsgroups: sci.math