cp's OEIS Frontend

A373390 a(n) = n for n <= 3; for n > 3, a(n) is the smallest unused positive number that is coprime to a(n-1) but has a common factor with at least one of a(1)...a(n-2).

%I A373390 #83 Mar 30 2025 09:53:06
%S A373390 1,2,3,4,9,8,15,14,5,6,7,10,21,16,25,12,35,18,49,20,27,22,39,11,13,24,
%T A373390 55,26,33,28,45,32,51,38,17,19,30,77,34,57,40,63,44,65,36,85,42,95,46,
%U A373390 75,23,48,91,50,69,52,81,56,87,62,29,31,54,115,58,93,64,99,68,105,74,117,37,60,119,66
%N A373390 a(n) = n for n <= 3; for n > 3, a(n) is the smallest unused positive number that is coprime to a(n-1) but has a common factor with at least one of a(1)...a(n-2).
%C A373390 The sequence uses a criterion for selecting the next term similar to those that define A098550 and A247942, but here all terms prior to a(n-1) can be checked for a common factor with a(n).
%C A373390 Comment from _N. J. A. Sloane_, Jun 19 2024 (Start)
%C A373390 Theorem: This is a permutation of the positive integers.
%C A373390 Proof: This follows from arguments similar to those used to prove that other "lexicographically earliest" sequences are permutations. Here is a sketch of the steps.
%C A373390 1. Sequence is infinite. (Easy: a(n-2) times a giant prime is always a candidate for a(n).)
%C A373390 2. Let w(n) = index of n when it appears, or -1 if n never appears. Let W(n) = max {w(1), ..., w(n)}. Then i > W(n) implies a(i) > n. [In words, the rules imply that there is a threshold W(n) such that if n has not appeared by the time you have looked at the first W(n) terms, then n will never appear.]
%C A373390 3. For any prime p, there is an n with p | a(n). For if not, no prime q > p can divide any term either, or we could have used p instead of q. So all terms are a product of primes < p. Now consider a term a(m) with m > W(p!), and let q < p be the smallest prime factor of a(m). Then q*p < p! < a(m) is a smaller candidate for a(m). Contradiction.
%C A373390 4. For any prime p there are infinitely many terms divisible by p. For if not, choose a power of p, p^r say, that is greater than any multiple of p in the sequence, and then choose a prime Q > p^r. Look at the first term, k*Q say, that is divisible by Q. But then k*p^r would have been a smaller choice than k*Q. Contradiction.
%C A373390 5. For any prime p, there is a term a(n) = p. In words, every prime appears naked. Proof: Choose a giant multiple of p, G*p say. Then p would have been a smaller choice than G*p. Contradiction.
%C A373390 6. (This is the only tricky step.) Every number appears. Suppose k = p1*p2*p3 (say) never appears (we know from 5 that we can assume k is not itself a prime). Find a giant multiple of p1, a(n) = G*p1. Then k is a candidate for a(n+2), unless gcd(k,a(n+1)) > 1. So gcd(k, a(n+1)) > 1 is forced. But then, equally, gcd(k, a(n+2)) > 1 is forced, or else we could set a(n+3) = k. And so on. So every term after a(n) must have a common factor with k. This is impossible by 5.
%C A373390 This completes the proof. (End)
%C A373390 A373790 has several as-yet unproved conjectures related to this sequence. - _N. J. A. Sloane_, Jun 23 2024
%C A373390 The terms appear to follow a pattern similar to the EKG sequence A064413, i.e., the terms are concentrated along just three lines of different gradient, and the lower line consists only of primes. Prime powers appear in the upper two lines, with the powers of 2 greater than 32 falling on the middle line while all others fall on the top line. See the attached image for the first 1000 terms. For the first 100000 terms the primes appear in their natural order, implying that is likely true for all n.
%C A373390 The fixed points are 1, 2, 3, 4, 18, 20, 22, 32, 98, and it is likely that no more exist. Given that A098550 and A247942 are permutations of the positive integers, it is almost certainly true that this sequence is also. [This is true - see the above Theorem. - _N. J. A. Sloane_, Jun 20 2024]
%C A373390 From _Michael De Vlieger_, Jun 07 2024: (Start)
%C A373390 A scatterplot of the sequence shows 3 trajectories as follows:
%C A373390 "Alpha" is a trajectory of odd composite numbers (highest slope).
%C A373390 "Gamma" is a trajectory of even composite numbers.
%C A373390 "Beta" is the trajectory of primes and the number 1 (lowest slope). (End) [The points on the three trajectories are listed in A372080 and A372081 (alpha), A373786 and A373787 (gamma), and A372073 (beta). - _N. J. A. Sloane_, Jun 20 2024]
%H A373390 Scott R. Shannon, <a href="/A373390/b373390.txt">Table of n, a(n) for n = 1..10000</a>
%H A373390 Scott R. Shannon, <a href="/A373390/a373390.png">Image of the first 1000 terms</a>. Numbers with one, two, three, or four and more distinct prime factors are shown as red, yellow, green and violet respectively. The white line is a(n) = n.
%H A373390 Michael De Vlieger, <a href="/A373390/a373390_1.png">Log log scatterplot of a(n)</a>, n = 1..2^16, showing primes in red, odd nonprimes in green, and composite even numbers in blue.
%H A373390 Michael De Vlieger, <a href="/A373390/a373390_2.png">Log log scatterplot of a(n)</a>, n = 1..2^14, showing primes in red, perfect prime powers in gold, squarefree composites in green, and numbers neither squarefree nor prime powers in blue and purple, with purple additionally indicating powerful numbers that are not prime powers.
%H A373390 Michael De Vlieger, <a href="/A373390/a373390.txt">Table of n, a(n) for n = 1..131072</a>
%e A373390 a(11) = 7 as 7 is coprime to a(10) = 6 while sharing a factor with a(8) = 14. This is the first term to differ from A098550.
%e A373390 a(38) = 77 as 77 is coprime to a(37) = 30 while sharing a factor with a(30) = 28. This is the first term to differ from A247942.
%t A373390 c[_] := False; p[_] := False; nn = 120;
%t A373390 Array[Set[{a[#], c[#], p[#]}, {#, True, True}] &, 3];
%t A373390 i = a[2]; j = a[3]; u = 4;
%t A373390 Do[k = u;
%t A373390  While[Or[c[k], ! CoprimeQ[j, k],
%t A373390    NoneTrue[Set[s, #], p] &@FactorInteger[k][[All, 1]]], k++];
%t A373390  Map[Set[p[#], True] &, s];
%t A373390  Set[{a[n], c[k], i, j}, {k, True, j, k}];
%t A373390  If[k == u, While[c[u], u++]], {n, 4, nn}];
%t A373390 Array[a, nn] (* _Michael De Vlieger_, Jun 06 2024 *)
%o A373390 (Python)
%o A373390 from math import gcd, lcm
%o A373390 from itertools import count, islice
%o A373390 def agen(): # generator of terms
%o A373390     yield from [1, 2, 3]
%o A373390     aset, an, LCM, mink = {1, 2, 3}, 3, 6, 4
%o A373390     while True:
%o A373390         an = next(k for k in count(mink) if k not in aset and gcd(k, an) == 1 and gcd(k, LCM) > 1)
%o A373390         LCM = lcm(LCM, an)
%o A373390         aset.add(an)
%o A373390         while mink in aset: mink += 1
%o A373390         yield an
%o A373390 print(list(islice(agen(), 76))) # _Michael S. Branicky_, Jun 18 2024
%Y A373390 Cf. A098550, A247942, A064413, A336957.
%Y A373390 See also A372072, A372073, A372078-A372081, A373786-A373791, A373880.
%K A373390 nonn
%O A373390 1,2
%A A373390 _Scott R. Shannon_, Jun 03 2024