login
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.
5

%I #21 Mar 27 2022 07:55:03

%S 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,

%T 22,13,24,65,28,55,32,45,34,39,17,57,68,19,40,133,30,119,36,161,38,23,

%U 44,69,50,51,52,63,46,75,58,81,29,93,116,31,56,155,42,85,48,95,54,115,62

%N 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.

%C 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).

%C 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).

%C 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.

%C 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.

%C 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).

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

%H Rémy Sigrist, <a href="/A350359/b350359.txt">Table of n, a(n) for n = 1..10000</a>

%H Michael De Vlieger, <a href="/A350359/a350359_1.png">Simple annotated log-log plot of a(n)</a> for n = 1..64, highlighting maxima and minima.

%H Michael De Vlieger, <a href="/A350359/a350359.png">Annotated log log scatterplot of a(n)</a> for n = 1..2^10, showing records in red and local minima in blue, smallest missing numbers in fine gold points.

%H Michael De Vlieger, <a href="/A350359/a350359_2.png">Log log scatterplot of 50000 terms</a>, exhibiting quasi-linear striations.

%H Michael De Vlieger, <a href="/A350359/a350359_3.png">Log log scatterplot of 50000 terms</a>, highlighting primes in red, populating beta QLS.

%H Michael De Vlieger, <a href="/A350359/a350359_4.png">Log log scatterplot of 50000 terms</a> highlighting even terms in red, odd in blue.

%H Michael De Vlieger, <a href="/A350359/a350359_5.png">Log log scatterplot of 50000 terms</a> color coding the relationship between terms b and d.

%e 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.

%p N := 1000:

%p a[1] := 1; a[2] := 2; a[3] := 3; a[4] := 4:

%p R := {$5 .. N)};

%p for n from 5 while R <> {} do

%p success := false;

%p for r in R do

%p if igcd(r, a[n-1]) = 1 and igcd(r, a[n-3]) = 1 and igcd(r, a[n-2]) > 1 then

%p a[n] := r;

%p R := R minus {r};

%p success := true;

%p break

%p fi

%p od:

%p if not success then break fi;

%p od:

%p seq(a[i], i = 1 .. n-1)

%t 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 *)

%o (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

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

%K nonn

%O 1,2

%A _David James Sycamore_, Dec 26 2021