[seqfan] Re: Sieving method for composite numbers described / used in A146071
dwilson at gambitcomm.com
Fri Oct 31 22:53:19 CET 2008
Alexander Povolotsky wrote:
> Would the sieving method for composite numbers, with which I came up in
> 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
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.
More information about the SeqFan