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

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, 55, 26, 33, 28, 45, 32, 51, 38, 17, 19, 30, 77, 34, 57, 40, 63, 44, 65, 36, 85, 42, 95, 46, 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

Offset: 1

Author

Scott R. Shannon, Jun 03 2024

Keywords

• nonn

Comments

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

Comment from N. J. A. Sloane, Jun 19 2024 (Start)

Theorem: This is a permutation of the positive integers.

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.

1. Sequence is infinite. (Easy: a(n-2) times a giant prime is always a candidate for a(n).)

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.]

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.

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.

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.

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.

This completes the proof. (End)

A373790 has several as-yet unproved conjectures related to this sequence. - N. J. A. Sloane, Jun 23 2024

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.

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]

From Michael De Vlieger, Jun 07 2024: (Start)

A scatterplot of the sequence shows 3 trajectories as follows:

"Alpha" is a trajectory of odd composite numbers (highest slope).

"Gamma" is a trajectory of even composite numbers.

"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]

Examples

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

Links

• Scott R. Shannon, Table of n, a(n) for n = 1..10000
• Scott R. Shannon, Image of the first 1000 terms. 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.
• Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^16, showing primes in red, odd nonprimes in green, and composite even numbers in blue.
• Michael De Vlieger, Log log scatterplot of a(n), 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.
• Michael De Vlieger, Table of n, a(n) for n = 1..131072

Crossrefs

Cf. A098550, A247942, A064413, A336957.

See also A372072, A372073, A372078-A372081, A373786-A373791, A373880.

Programs

Mathematica

c[] := False; p[] := False; nn = 120;
Array[Set[{a[#], c[#], p[#]}, {#, True, True}] &, 3];
i = a[2]; j = a[3]; u = 4;
Do[k = u;
 While[Or[c[k], ! CoprimeQ[j, k],
   NoneTrue[Set[s, #], p] &@FactorInteger[k][[All, 1]]], k++];
 Map[Set[p[#], True] &, s];
 Set[{a[n], c[k], i, j}, {k, True, j, k}];
 If[k == u, While[c[u], u++]], {n, 4, nn}];
Array[a, nn] (* Michael De Vlieger, Jun 06 2024 *)

Python

from math import gcd, lcm
from itertools import count, islice
def agen(): # generator of terms
    yield from [1, 2, 3]
    aset, an, LCM, mink = {1, 2, 3}, 3, 6, 4
    while True:
        an = next(k for k in count(mink) if k not in aset and gcd(k, an) == 1 and gcd(k, LCM) > 1)
        LCM = lcm(LCM, an)
        aset.add(an)
        while mink in aset: mink += 1
        yield an
print(list(islice(agen(), 76))) # Michael S. Branicky, Jun 18 2024