OFFSET
1,1
COMMENTS
Every term is relatively prime to its neighbors.
Theorem: The sequence is a permutation of the semiprimes.
Proof (based on the arguments in The Yellowstone Permutation paper):
1. The sequence is infinite. For P^2 is always a candidate for a(n), where P is any prime greater than all those dividing a(1),...,a(n-1).
2. For any m, there is an n_0 such that a(n) > m for all n >= n_0. (Follows from 1.)
3. For any prime p, there is a term divisible by p. Proof: Suppose p never divides any term of the sequence. Then no prime q>p can appear either, or else the first time there is a term q*r, we could have used p*r instead. So only finitely many primes appear, and so the sequence is finite, a contradiction.
4. For any prime p, there are infinitely many terms divisible by p. Proof: Suppose there are only finitely many multiples of p, say p*q_1, p*q_2, ..., p*q_k. Let r,s,t be the next three primes after max{q_1,...,q_k}. None of p*r, p*s, p*t appear in the sequence. Choose n_0 so that a(n) > (p*t)^2 for n >= n_0. Suppose a(n) = x*y for some n > n_0. Then p*r, p*s, p*t are candidates for a(n+1) which are less than (p*t)^2, and since a(n) only involves two primes, one of the three is a smaller choice for a(n+1), a contradiction.
5. For any prime p, there is a term a(n)=p^2. Proof: Similar to that of 4.
6. Every semiprime appears. Proof: Let p*q be the smallest missing semiprime. Choose n_0 so that for n >= n_0, a(n) > (p*q)^2. Suppose a(n)=b*c with b <= c. Then a(n+1) will be p*q (and we have the desired contradiction) unless b is p or q. If b is p or q then a(n+2) = p*q unless a(n+2) is divisible by q or p, and so on. The only way that p*q will not appear is that for all n > n_0, a(n) is divisible alternately by p or q. But this contradicts 5, since there are infinitely many large prime squares in the sequence. QED. - N. J. A. Sloane, Oct 13 2015
LINKS
David L. Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. J. A. Sloane, and Reinhard Zumkeller, The Yellowstone Permutation, arXiv preprint arXiv:1501.01669, 2015. Also Journal of Integer Sequences, Vol. 18 (2015), Article 15.6.7
MATHEMATICA
sp0=Select[Range[1000], 2==Plus@@Last/@FactorInteger@#&]; sp=sp0; le=Length@sp; seq={4}; b=4; sp=Rest@sp; le=le-1; Do[Do[spi=sp[[i]]; If[1==GCD[b, spi], b=spi; AppendTo[seq, b]; sp=Delete[sp, i]; le=le-1; Break[]], {i, le}], {100}]; seq
CROSSREFS
KEYWORD
nonn
AUTHOR
Zak Seidov, Jun 13 2006
EXTENSIONS
Definition revised by N. J. A. Sloane, Oct 13 2015 at the suggestion of Bob Selcoe.
STATUS
approved