A119718 a(1)=4; thereafter a(n) is the smallest semiprime not yet appearing in the sequence that is relatively prime to a(n-1).

4, 9, 10, 21, 22, 15, 14, 25, 6, 35, 26, 33, 34, 39, 38, 49, 46, 51, 55, 57, 58, 65, 62, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 121, 122, 123, 133, 129, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 169, 177, 178, 183, 185, 187

Offset: 1

Author

Zak Seidov, Jun 13 2006

Keywords

• nonn

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

Crossrefs

Cf. A098550.

A001358 gives the semiprimes.

Programs

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

Extensions

Definition revised by N. J. A. Sloane, Oct 13 2015 at the suggestion of Bob Selcoe.