A350359 Lexicographically earliest infinite sequence of distinct positive integers such that for any four consecutive terms a,b,c,d, d is prime to a and c, but not to b.

1, 2, 3, 4, 9, 8, 15, 14, 5, 7, 25, 21, 10, 27, 16, 33, 20, 11, 26, 77, 6, 35, 12, 49, 18, 91, 22, 13, 24, 65, 28, 55, 32, 45, 34, 39, 17, 57, 68, 19, 40, 133, 30, 119, 36, 161, 38, 23, 44, 69, 50, 51, 52, 63, 46, 75, 58, 81, 29, 93, 116, 31, 56, 155, 42, 85, 48, 95, 54, 115, 62

Offset: 1

Author

David James Sycamore, Dec 26 2021

Keywords

• nonn

Comments

The sequence preserves throughout the coprime relations found in the first four positive integers 1,2,3,4 (4 is prime to 1 and 3 but not to 2).

A prime term p at a(n) is necessarily preceded at a(n-2) by a multiple m*p of p, and followed at a(n+2) by a different multiple w*p of p (m,w > 1).

The sequence is infinite. Proof: For successive terms a,b,c,d we can choose a multiple e = q*c of c, where q is any prime which divides neither b nor d and such that e is not a prior term. Then e is prime to b and d but not to c, and since it has not been seen before we have at least one candidate for the term following d, which we choose as the least such number.

The definition implies that there can be no consecutive even terms (since then they would not be coprime). However, consecutive odd terms are not excluded, and do occur (eg 21 can follow 25 because they are coprime). Although two adjacent primes is possible, and does occur (a(9)=5, a(10)=7), three is not, since consecutive distinct primes p,q,r would imply gcd(p,r)>1.

Similar sequences with the same coprime relations as in 1,2,3,4 can be generated from any start terms a,b,c,d with b=a+1,c=b+1,d=c+1, provided a is congruent to 1 or 5 mod 6 (A007310).

Conjecture: The sequence is a permutation of the positive integers in which the primes appear in their natural order.

Examples

			From the definition a(k)=k for 1 <= k <= 4. a(5) = 9 since 9 is prime to 2 and 4 but not to 3, and is the smallest number with this property. Likewise a(6) = 8 since 8 is prime to 3 and 9 but not to 4.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000
• Michael De Vlieger, Simple annotated log-log plot of a(n) for n = 1..64, highlighting maxima and minima.
• Michael De Vlieger, Annotated log log scatterplot of a(n) for n = 1..2^10, showing records in red and local minima in blue, smallest missing numbers in fine gold points.
• Michael De Vlieger, Log log scatterplot of 50000 terms, exhibiting quasi-linear striations.
• Michael De Vlieger, Log log scatterplot of 50000 terms, highlighting primes in red, populating beta QLS.
• Michael De Vlieger, Log log scatterplot of 50000 terms highlighting even terms in red, odd in blue.
• Michael De Vlieger, Log log scatterplot of 50000 terms color coding the relationship between terms b and d.

Crossrefs

Cf. A084937, A098550, A064413, A336957, A007310.

Programs

Maple

N := 1000:
a[1] := 1; a[2] := 2; a[3] := 3; a[4] := 4:
R := {$5 .. N)};
for n from 5 while R <> {} do
   success := false;
   for r in R do
     if igcd(r, a[n-1]) = 1 and igcd(r, a[n-3]) = 1 and igcd(r, a[n-2]) > 1 then
     a[n] := r;
     R := R minus {r};
     success := true;
     break
   fi
  od:
  if not success then break fi;
  od:
seq(a[i], i = 1 .. n-1)

Mathematica

Nest[Block[{s = #, a, b, c, k = 4}, Set[{a, b, c}, #[[-3 ;; -1]]]; While[Nand[FreeQ[s, k], GCD[a, k] == 1, GCD[b, k] > 1, GCD[c, k] == 1], k++]; Append[s, k]] &, Range[3], 68] (* Michael De Vlieger, Dec 26 2021 *)

PARI

{ s=0; for (n=1, #a=vector(71), if (n<=3, a[n]=n, for (v=0, oo, if (!bittest(s,v) && gcd(v,a[n-2])>1 && gcd(v,lcm(a[n-3],a[n-1]))==1, a[n]=v; break))); s+=2^a[n]; print1(a[n]", ")) } \\ Rémy Sigrist, Mar 27 2022