[seqfan] Re: Do 20 and 105 eventually reach a prime in these sequences?

[David Wilson]

What we are talking about is the trajectory of iterating A080670 on an 
integer.

I am certain that A080670(n) is O(n log^k(n)) (likely with k = 2, but 
proof would be tedious).
This means that a trajectory of A080670 could potentially have mildly 
superexponential
growth, as you suspect.

However, note that by the prime number theorem, the density of primes 
near n is about
1/log(n). This means that for a "random" exponential sequence a(n) < 
c^n, the probability
that a(n) is prime is about 1/log(c)n = d/n.  If you do the math, you 
find that the probability
of encountering a prime somewhere in the sequence is 1, that is, you 
should expect to
encounter a prime.

As I said, a trajectory of A080670 is mildly superexponential, but not 
enough the escape
the conclusion that said trajectory should encounter a prime with 
probability 1.

I have to qualify this conclusion. Since it is possible for A080670(n) < 
n (for example
A080670(2^67) = 267), it is conceivable that some trajectory of A080670 
enters a primeless
cycle and thus avoids reaching a prime. I don't think this is very likely.

On the other hand, the prime factorization of a very large composite 
number n will tend to
have a largest prime factor p of exponent 1. In this case, A080670(n) 
will end in p. For
example, 104 has largest prime factor 13 of exponent 1, so A080670(104) 
= 2213 ends in
the digits 13. This means that large numbers in a trajectory a very 
unlikely to be divisible
by 2 or 5, increasing their propensity for primality.

At any rate, my bet is that the trajectory of any n eventually reaches a 
prime. Safe enough
bet, since it can't be disproved unless said trajectory enters a 
primeless cycle.

On 9/14/2011 12:35 AM, franktaw at netscape.net wrote:
> I think (though I don't have a proof) that the numbers grow 
> exponentially. If that's the case, it doesn't really matter how small 
> the base of the exponent is (as long as it's greater than 1); this 
> only affects how soon one would expect to reach the point where most 
> numbers do not reach a prime.
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: Charles Greathouse <charles.greathouse at case.edu>
>
>> Most *small* integers quickly reach a prime.  I'm confident that most
>> integers do not.
>
> Interesting.  The numbers don't grow that quickly, so I'd think you'd
> typically reach a prime just 'by chance'.  I guess it all depends on
> their rate of increase: the harmonic series diverges but the sum of
> 1/log(n log n) converges.
>
> ...
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>