[seqfan] Re: Sieving method for composite numbers described / used in A146071

[David Wilson]

Alexander Povolotsky wrote:
> Hi,
>
> Would the sieving method for composite numbers, with which I came up in
> A146071,
> produce ALL prime  numbers (so far I don't see 13 there ... ;-) ) ?
> If NOT - then could one define / predict what prime numbers will be not
> generated by below described sieving method for composite numbers ?
>   
OK, this is not a sieve. So we can all stop beating Mr. Povolotsky up 
and look at what he has.

He is iterating the map

m(n) = n - A001414(n)

where A001414(n) is the sum of prime factors of n with repetition.

We can show that iterating m on any positive integer eventually reaches 
0 (which is not in the domain of m, so iteration must stop there) or 1 
(at which point we enter the cycle (1)). We can prove that 1 and 6 are 
the only numbers that reach 1. All other positive integers reach 0.

We can also that if a number reaches 0, the number it reached just prior 
is either 4 or prime. This "just prior" number is given by the recursive 
defintion

f(n) = n, if m(n) = 0 or 1; f(m(n)), otherwise.

We can show f(1) = 1, f(4) = 4, f(6) = 6 and all other f(n) are prime.

Since f(p) = p for all primes, every prime is in the range of f.

Mr. Povolotsky's question is whether every prime p is of the form p = 
f(n) for some composite n.

The answer is no. We can show that if n is composite, then m(n) >= 
n/2-2, with equality when n = 2p for prime p. This means that for prime 
p, if we cannot find a composite n <= 2p+4 solving m(n) = p, then there 
is no composite n at all solving m(n) = p, and hence no composite 
solution of f(n) = p (the last value before reaching p would have to be 
a composite solving m(n) = p, which doesn't exist).

For example, take Maximilian Hasler's first value, 13. No composite n <= 
2*13+4 = 30 solve m(n) = 13, so there is no composite solving m(n) = 13 
or f(n) = 13.