cp's OEIS Frontend

This sequence uses the same rules as A336957 except with the additional restriction that a(n) must have a different number of divisors than a(n-1). This leads to the terms showing a greater variation in value. For example in the first 5000 terms the maximum is a(3915) = 228569, compared to a maximum of a(3225) = 11053 for A336957 in the same range. Like A336957 is it likely all positive integers other than the prime-powers eventually appear.

For n > 3, gcd(a(n), a(n-1)) = 1 and gcd(a(n), a(n-2)) > 1. (This is just a restatement of the definition.)

This is now known to be a permutation of the natural numbers: see the 2015 article by Applegate, Havermann, Selcoe, Shevelev, Sloane, and Zumkeller.

From N. J. A. Sloane, Nov 28 2014: (Start)

Some of the known properties (but see the above-mentioned article for a fuller treatment):

1. The sequence is infinite. Proof: We can always take a(n) = a(n-2)*p, where p is a prime that is larger than any prime dividing a(1), ..., a(n-1). QED

2. At least one-third of the terms are composite. Proof: The sequence cannot contain three consecutive primes. So at least one term in three is composite. QED

3. For any prime p, there is a term that is divisible by p. Proof: Suppose not. (i) No prime q > p can divide any term. For if a(n)=kq is the first multiple of q to appear, then we could have used kp < kq instead, a contradiction. So every term a(n) is a product of primes < p. (ii) Choose N such that a(n) > p^2 for all n > N. For n > N, let a(n)=bg, a(n+1)=c, a(n+2)=dg, where g=gcd(a(n),a(n+2)). Let q be the largest prime factor of g. We know q < p, so qp < p^2 < dg, so we could have used qp instead of dg, a contradiction. QED

3a. Let a(n_p) be the first term that is divisible by p (this is A251541). Then a(n_p) = q*p where q is a prime less than p. If p < r are primes then n_p < n_r. Proof: Immediate consequences of the definition.

4. (From David Applegate, Nov 27 2014) There are infinitely many even terms. Proof:

Suppose not. Then let 2x be the maximum even entry. Because the sequence is infinite, there exists an N such that for any n > N, a(n) is odd, and a(n) > x^2.

In addition, there must be some n > N such that a(n) < a(n+2). For that n, let g = gcd(a(n),a(n+2)), a(n) = bg, a(n+1)=c, a(n+2)=dg, with all of b,c,d,g relatively prime, and odd.

Since dg > bg, d > b >= 1, so d >= 3. Also, g >= 3.

Since a(n) = bg > x^2, one of b or g is > x.

Case 1: b > x. Then 2b > 2x, so 2b has not yet occurred in the sequence. And gcd(bg,2b)=b > x > 1, gcd(2b,c)=1, and since g >= 3, 2b < bg < dg. So a(n+2) should have been 2b instead of dg.

Case 2: g > x. Then 2g > 2x, so 2g has not yet occurred in the sequence. And gcd(bg,2g)=g > 1, gcd(2g,c)=1, and since d >= 3, 2g < dg. So a(n+2) should have been 2g instead of dg.

In either case, we derive a contradiction. QED

Conjectures:

5. For any prime p > 97, the first time we see p, it is in the subsequence a(n) = 2b, a(n+2) = 2p, a(n+4) = p for some n, b, where n is about 2.14*p and gcd(b,p)=1.

6. The value of |{k=1,..,n: a(k)<=k}|/n tends to 1/2. - Jon Perry, Nov 22 2014 [Comment edited by N. J. A. Sloane, Nov 23 2014 and Dec 26 2014]

7. Based on the first 250000 terms, I conjectured on Nov 30 2014 that a(n)/n <= (Pi/2)*log n.

8. The primes in the sequence appear in their natural order. This conjecture is very plausible but as yet there is no proof. - N. J. A. Sloane, Jan 29 2015

(End)

The only fixed points seem to be {1, 2, 3, 4, 12, 50, 86} - see A251411. Checked up to n=10^4. - L. Edson Jeffery, Nov 30 2014. No further terms up to 10^5 - M. F. Hasler, Dec 01 2014; up to 250000 - Reinhard Zumkeller; up to 300000 (see graph) - Hans Havermann, Dec 01 2014; up to 10^6 - Chai Wah Wu, Dec 06 2014; up to 10^8 - David Applegate, Dec 08 2014.

From N. J. A. Sloane, Dec 04 2014: (Start)

The first 250000 points lie on about 8 roughly straight lines, whose slopes are approximately 0.467, 0.957, 1.15, 1.43, 2.40, 3.38, 5.25 and 6.20.

The first six lines seem well-established, but the two lines with highest slope at present are rather sparse. Presumably as the number of points increases, there will be more and more lines of ever-increasing slopes.

These lines can be seen in the Havermann link. See the "slopes" link for a list of the first 250000 terms sorted according to slope (the four columns in the table give n, a(n), the slope a(n)/n, and the number of divisors of a(n), respectively).

The primes (with two divisors) all lie on the lowest line, and the lines of slopes 1.43 and higher essentially consist of the products of two primes (with four divisors).

(End)

The eight roughly straight lines mentioned above are actually curves. A good fit for the "line" with slope ~= 1.15 is a(n)~=n(1+1.0/log(n/24.2)), and a good fit for the other "lines" is a(n)~= (c/2)*n(1-0.5/log(n/3.67)), for c = 1,2,3,5,7,11,13. The first of these curves consists of most of the odd terms in the sequence. The second family consists of the primes (c=1), even terms (c=2), and c*prime (c=3,5,7,11,13,...). This functional form for the fit is motivated by the observed pattern (after the first 204 terms) of alternating even and odd terms, except for the sequence pattern 2*p, odd, p, even, q*p when reaching a prime (with q a prime < p). - Jon E. Schoenfield and David Applegate, Dec 15 2014

For a generalization, see the sequence of monomials of primes in the comment in A247225. - Vladimir Shevelev, Jan 19 2015

From Vladimir Shevelev, Feb 24 2015: (Start)

Let P be prime. Denote by S_P*P the first multiple of P appearing in the sequence. Then

1) For P >= 5, S_P is prime.

Indeed, let

a(n-2)=v, a(n-1)=w, a(n)=S_P*P. (*)

Note that gcd(v,P)=1. Therefore, by the definition of the sequence, S_P*P should be the smallest number such that gcd(v,S_P) > 1.

So S_P is the smallest prime factor of v.

2) The first multiples of all primes appear in the natural order.

Suppose not. Then there is a pair of primes P < Q such that S_Q*Q appears earlier than S_P*P. Let

a(m-2)=v_1, a(m-1)=w_1, a(m)=S_Q*Q. (**)

Then, as in (*), S_Q is the smallest prime factor of v_1. But this does not depend on Q. So S_Q*P is a smaller candidate in (**), a contradiction.

3) S_P < P.

Indeed, from (*) it follows that the first multiple of S_P appears earlier than the first multiple of P. So, by 2), S_P < P.

(End)

For any given set S of primes, the subsequence consisting of numbers whose prime factors are exactly the primes in S appears in increasing order. For example, if S = {2,3}, 6 appears first, in due course followed by 12, 18, 24, 36, 48, 54, 72, etc. The smallest numbers in each subsequence (i.e., those that appear first) are the squarefree numbers A005117(n), n > 1. - Bob Selcoe, Mar 06 2015

In other words, C contains all positive numbers except powers of primes p^k, k>=1.

This is a modified version of the Enots Wolley sequence A336957. The modification ensures that the sequence does not contain the prime 2.

Let Ker(k), the kernel of k, denote the set of primes dividing k. Thus Ker(36) = {2,3}, Ker(1) = {}.

Theorem: a(1)=1, a(2)=6; thereafter, a(n) is the smallest number m not yet in the sequence such that

(i) Ker(m) intersect Ker(a(n-1)) is nonempty,

(ii) Ker(m) intersect Ker(a(n-2)) is empty, and

(iii) The set Ker(m) \ Ker(a(n-1)) is nonempty.

Conjecture: The sequence is a permutation of C.

Alternative definition: Lexicographically earliest sequence of distinct positive numbers such that a(n) != a(n-1)+1 and gcd(a(n-1)+1,a(n)) > 1. This makes it a cousin of the EKG sequence A064413, the Yellowstone permutation A098550, the Enots Wolley sequence A336957, and others. - N. J. A. Sloane, Sep 01 2021; revised Nov 08 2021.

The successive gcd's are listed in A347309.

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]

Conjecture: This is a permutation of the natural numbers. Up to 1 million terms the only fixed points are 1,2,3,6,9,10, and it is likely that there are no others.

This is an intermediate sequence between the EKG sequence A064413 (which only involves the first condition) and the Enots Wolley sequence A336957 (which involves both conditions).

By ignoring the second condition when necessary we guarantee that a(n) always exists (because it always exists for the EKG sequence), and so no backtracking is needed in this sequence.

The second condition is ignored precisely when every prime that divides a(n-1) also divides a(n-2).

Conjecture 1: Every positive number appears.

Conjecture 2: The primes are the slowest numbers to appear. That is, when a prime p appears here, all numbers less than p have already appeared. To put this another way, the record high points in A352188 ("when does n appear") are exactly the primes (and 1).

Conjecture 3: When a prime p first divides some term, that term is 2*p, which is followed by p then 3p. [It seems possible that we could see 2*a, 6*b, 3*p, p, 2*p. This does not happen in the first 10000 terms, but I can't prove it never happens. I can prove that every prime divides some term, and that the primes appear in increasing order. Conjecture 3 might be refuted by a more extensive calculation.]

Other possible conditions on a(n) with respect to its common factors with a(n-2) and a(n-1) lead to the following:

Coprime to both: A084937.

Coprime to the latter and not the former: A098550.

Coprime to the former and not the latter: with any initial conditions, the sequence "paints itself into a corner", i.e., is finite. With the added condition of a(n) having an extra prime factor not contained in a(n-1), it is A336957.

Coprime to the latter, regardless of the former: simply A000027.

Coprime to the former, regardless of the latter: A121216.

Non-coprime to the latter, regardless of the former: A064413.

Non-coprime to the former, regardless of the latter: A121217.

This is a permutation of the natural numbers. Up to 500000 terms the fixed points are 0, 1, 2, 4, 5, 15, 16, 18, 21, 22, 24, 25, 29, and it is likely no more exist.

For n > 250 the terms are concentrated along seven lines, see the linked images. Unlike the other six lines, numbers along the second lowest line are somewhat spread out, and these terms contain all numbers with Omega(a(n)) > 1. The lowest line contains all the primes, while the upper five lines contain terms with Omega(a(n)) = 2, 3, and 4. The primes up to n=100000 occur in their natural order except for 11 and 13 which are switched. The only fixed point beyond the first two terms is 10, and it is likely no more exist. The sequence is conjectured to be a permutation of the positive integers.