cp's OEIS Frontend

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.

%I A350359 #21 Mar 27 2022 07:55:03
%S A350359 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 A350359 22,13,24,65,28,55,32,45,34,39,17,57,68,19,40,133,30,119,36,161,38,23,
%U A350359 44,69,50,51,52,63,46,75,58,81,29,93,116,31,56,155,42,85,48,95,54,115,62
%N 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.
%C A350359 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 A350359 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 A350359 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 A350359 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 A350359 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 A350359 Conjecture: The sequence is a permutation of the positive integers in which the primes appear in their natural order.
%H A350359 Rémy Sigrist, <a href="/A350359/b350359.txt">Table of n, a(n) for n = 1..10000</a>
%H A350359 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 A350359 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 A350359 Michael De Vlieger, <a href="/A350359/a350359_2.png">Log log scatterplot of 50000 terms</a>, exhibiting quasi-linear striations.
%H A350359 Michael De Vlieger, <a href="/A350359/a350359_3.png">Log log scatterplot of 50000 terms</a>, highlighting primes in red, populating beta QLS.
%H A350359 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 A350359 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 A350359 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 A350359 N := 1000:
%p A350359 a[1] := 1; a[2] := 2; a[3] := 3; a[4] := 4:
%p A350359 R := {$5 .. N)};
%p A350359 for n from 5 while R <> {} do
%p A350359    success := false;
%p A350359    for r in R do
%p A350359      if igcd(r, a[n-1]) = 1 and igcd(r, a[n-3]) = 1 and igcd(r, a[n-2]) > 1 then
%p A350359      a[n] := r;
%p A350359      R := R minus {r};
%p A350359      success := true;
%p A350359      break
%p A350359    fi
%p A350359   od:
%p A350359   if not success then break fi;
%p A350359   od:
%p A350359 seq(a[i], i = 1 .. n-1)
%t A350359 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 A350359 (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 A350359 Cf. A084937, A098550, A064413, A336957, A007310.
%K A350359 nonn
%O A350359 1,2
%A A350359 _David James Sycamore_, Dec 26 2021