cp's OEIS Frontend

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

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: The sequence is infinite (that is, a(n) always exists).

Ray Chandler reports that the sequence certainly exists for 10^7 terms, Apr 02 2015. John P. Linderman confirms this, and has extended the sequence to 12.9 million terms, Apr 09 2015. Extended to 50 million terms by John Mason Apr 21 2015. John P. Linderman reached 150 million terms on May 04 2015, 2.5 billion terms on Jun 29 2015, and 5 billion terms on Apr 07 2017 (see attached letter).

Note that if a(n) ever divides a(n+1), the sequence will terminate. This has not happened in the first 2.5 billion terms (see the Linderman links), but there have been some close calls. For example, at n=9671, a(9671) = 4973 = a prime p, and a(9672) = 9947 = 2p+1. Conversely, if a(n) never divides a(n+1), the sequence is infinite. - N. J. A. Sloane, Mar 22 2015 and Jun 06 2015

Conjecture: The sequence is a permutation of the natural numbers.

Conjectures: 1) For k>=3, except for k=5, if a(n) = prime(k), then a(n-2) = 2*prime(k) and a(n+2) = 3*prime(k). This conjecture was verified by Peter J. C. Moses for n <= 5000. - Vladimir Shevelev, Feb 09 2015. This conjecture verified for n <= 10^7. - Ray Chandler, Apr 02 2015. Extended to n <= 10^9. - John Mason, Jun 08 2016

2) For k>=3, except for k=4, if a(n)=prime(k)^2, then a(n-2) = prime(k)^2 + prime(k). This conjecture was verified by Peter J. C. Moses for n <= 35000. - Vladimir Shevelev, Feb 12 2015. This conjecture verified for n <= 394349. - Ray Chandler, Mar 07 2015. This conjecture is false - for n = 4488245, a(n) = 2137^2, but a(n-2) = 2137^2 + 2*2137. - Ray Chandler, Mar 30 2015. Next are n = 30655601, a(n) = 5581^2, but a(n-2) = 5581^2 + 2*5581, and n = 922447261, a(n) = 30577^2, but a(n-2) = 30577^2 + 2*30577. - John Mason, Sep 15 2016

Theorem: a(n) does not divide a(n-1). For suppose a(n-2)=x, a(n-1)=b*c, a(n)=c. Then gcd(x,c) <= c, and gcd(b*c,c) = c, which contradicts the definition of a(n). - N. J. A. Sloane, Mar 22 2015

Theorem: If a(n-2) is prime AND a(n) EXISTS then a(n) is a multiple of a(n-2). For: by sequence definition, assuming a(n-2) = p, prime, then gcd(a(n),p) > gcd(a(n),a(n-1)); hence gcd(a(n),p) > 1; but p is prime and has only 1 and itself as divisors; so gcd(a(n),p)=p, and so a(n) is a multiple of p. (Weaker than the similar conjecture above.) - John Mason, Apr 15 2015 [WORDS IN CAPS ADDED BY N. J. A. Sloane, Apr 16 2015]

Theorem: If a(n) EXISTS AND a(n) > a(n-2)/2 then a(n) is composite. For: suppose instead that a(n)=p, prime; then by sequence definition, gcd(p,a(n-2)) > gcd(p,a(n-1)); hence gcd(p,a(n-2))>1; hence a(n-2) is a multiple of p; but a(n-2) < 2p so we have a contradiction; hence a(n) is composite. This theorem improves the efficiency of some sequence generation algorithms. - John Mason, Apr 15 2015 [WORDS IN CAPS ADDED BY N. J. A. Sloane, Apr 16 2015] [Further corrected by John Mason, May 28 2017]

Theorem: If a(n-2)=mp for some prime p, and m divides a(n-1), then a(n), if it exists, is a multiple of p (generalization of previous theorem, which is the special case of m=1). See for example a(33)=17, a(35)=51, a(37)=68; a(37) is a multiple of 17 because a(36) is a multiple of 3, which is "m" in a(35). (It follows that if a(n-2) / gcd(a(n-2), a(n-1)) is p, prime, then a(n), if it exists, is a multiple of p. - John Mason, May 19 2015)

Proof: consider consecutive terms mp,y,z for prime p, and m dividing y. By sequence definition gcd(z,mp)>gcd(z,y). Suppose that z is not a multiple of p. Then gcd(z,mp)=gcd(z,m), and so gcd(z,m)>gcd(z,y). Since m divides y, then gcd(z,m)>gcd(z,mq) for q = y/m, but this is clearly impossible. Hence z is a multiple of p. - John Mason, Apr 17 2015

Theorem: The first occurrences of the primes as factors of terms of the sequence are in ascending order, and without gaps (that is, 2 precedes 3, 3 precedes 5 (factor of 10), 5 precedes 7 (factor of 14), ...).

Proof: Suppose a(n)=mp is the first term having p as a factor. Then the theory states that q, prime and gcd(mp,a(n-1)). As a(n) is the first to have p as a factor, p does not divide a(n-2) and a(n-1), and neither does q. Hence gcd(mp,a(n-2))=gcd(m,a(n-2)) and gcd(mp,a(n-1))= gcd(m,a(n-1)). Hence gcd(m,a(n-2)) > gcd(m,a(n-1)). Hence gcd(mq,a(n-2)) > gcd(mq,a(n-1)). Hence mq, < mp, would have satisfied the conditions of the sequence for a(n), which is a contradiction. Hence no such prime q exists. - John Mason, Apr 17 2015

Theorem: The first occurrence of a prime p as a factor of a term in the sequence is in a term that is not equal to p itself.

Proof: Suppose a(n)=p, prime, the first term having p as a factor. Then gcd(p,a(n-2))=1, and therefore cannot be greater than gcd(p,a(n-1)), a contradiction of the rules of sequence construction. - John Mason, Apr 17 2015

Conjecture. The primes exist as elementary terms of the sequence in ascending order. - John Mason, Apr 17 2015

John Mason reports that each prime p seems to appear at a term n which is approaching 2p, as p increases. See A256213. - N. J. A. Sloane, Apr 16 2015

Conjecture. For any n > 4, the lowest value x missing from a(1) thru a(n) is prime. - John Mason, Apr 29 2015. In fact, taking into account that, apparently, prime p appears in the sequence at position circa 2p, we may conjecture that the lowest k values missing from a(1) thru a(n) are prime, where k = pi(n)-pi(n/2) - see A000720. - John Mason, Jun 03 2015

Theorem: if a(n) = p for some prime p > 3, then a(n-2) is a multiple of p. As a direct consequence, if all prime factors of a(n-2) are already present in the sequence, then a(n), if it exists, is composite.

Proof: by sequence definition, unless p=2 or 3, gcd(p,a(n-2)) > gcd(p,a(n-1)), and hence gcd(p,a(n-2))>1, and hence a(n-2) is a multiple of p. - John Mason, May 19 2015

First differs from A255582 at a(29). - Omar E. Pol, May 21 2015

Conjecture. For n > 778, if a(n) < n, then a(n) is prime. This has been confirmed for n through 10^9. - John Mason, Jun 03 2015 [Corrected, following suggestion by John P. Linderman, by John Mason, May 28 2017]

Conjecture. As for "Conjecture 1" above, which is its mirror image, except for n=2,3,21, corresponding to primes 2,3,11, if a(n-2)=mp is the first occurrence of prime p as a factor in the sequence, then m=2 and a(n)=p. Also, if a(n-2)=mp is the first occurrence of prime p as a factor in the sequence, then p does not divide a(n-1). - John Mason, May 31 2016

Theorem 1: If a(n) is the first term having p (prime) as a factor, then a(n+1), if it exists, is not a multiple of p. For proof, see links. - John Mason, Jul 26 2016

Theorem 2: If a(n)=cp is the first occurrence of prime p as a factor (n >3), than c has exactly one distinct prime factor. In other words, c may be expressed as k^i for some prime k, and i > 0.

Corollary. If a(n)=cp is the first occurrence of prime p as a factor (n >3), and as a consequence c= k^i for some prime k, and i > 0, then k^i divides a(n-2) and k^(i-1) is the maximum power of k that divides a(n-1).

Theorem 3 . If a(n) = 2p is the first term having p (prime) as a factor, then a(n-1) is odd and a(n-2) is even.

Theorem 4. If a(n) = 2p is the first term having p (prime) as a factor, then a(n+2), if it exists, is either p or 2u for some integer u such that 2u < p. (Note that it is conjectured to be always p, and observation confirms the conjecture.)

Theorem 5, generalization of Theorem 4. If a(n) = cp is the first term having p (prime) as a factor (n >3), and as a consequence c=k^i for prime k and i>0, then a(n+2), if it exists, is either p or ku for some integer u such that ku < p. (Note that it is conjectured to be always p, and observation confirms the conjecture.)

Theorem 6. If a(n) = cp is first term having p, prime, as a factor (n >3), and a(n+2)=p, then a(n+3) exists, and is not a multiple of p, and so does not terminate the sequence.

Theorem 7. If a(n) = cp is first term having p, prime, as a factor (n >3), and a(n+2)=p, then a(n+4) exists and is 2p or 3p. Also, a(n+5) exists.

For proofs, see links. - John Mason, Aug 03 2016

Theorem 8: If the sequence is infinite, it is a permutation of the positive integers. For proof, see link. - John Mason, Sep 14 2016

Conjecture: After 2 and 3, no two primes are consecutive terms. This conjecture is derivable from the previous conjecture : "For k>=3, except for k=5, if a(n) = prime(k), then a(n-2) = 2*prime(k) ...". For, if sequence has terms z,2p,2q,p,q for primes p & q, then gcd(2q,z)>gcd(2q,2p)=2. Hence q divides z. So terms are mq,2p,2q,p,q. So we could have used q in place of 2q. - John Mason, May 28 2017

Conjecturally the sequence is a permutation of the positive integers. However, to prove this we need more subtle arguments than were used to prove the corresponding property for A098550. - Vladimir Shevelev, Jan 14 2015

For n <= 2000, a(3n-1) is even and both a(3n) and a(3n-2) are odd numbers. I conjecture that this is true for all positive integers n. This conjecture is true iff for all positive integers n, a(3n-1) is even. - Farideh Firoozbakht, Jan 14 2015

From Vladimir Shevelev, Jan 19 2015: (Start)

A generalization of A098550 and A247225.

Let p_n=prime(n). Define the following sequence

a(1)=1, a(2)=p_1,...,a(k+2)=p_(k+1), otherwise the smallest number not occurring earlier having at least one common factor with a(n-(k+1)), but none with a(n-1)*a(n-2)*...*a(n-k).

The sequence begins

1, p_1, p_2, ..., p_(k+1), p_1^2, p_2^2, ..., p_(k+1)^2, p_1^3, ... (*)

[ p_1^3 is followed by p_2*p_(k+2), k<=2,

p_2^3, k>=3, etc.]

In particular, if k=1, it is A098550, if k=2, it is A247225.

Conjecturally for every k>=2, as in the case k=1, the sequence (*) is a permutation of the positive integers. For k>=3, at first glance, already the appearance of the number 6 seems problematic. However, at the author's request, Peter J. C. Moses found that the positions of 6 are 83, 157, 1190, 206, ... in cases k=3,4,5,6,... respectively (A254003).

Note also that for every k>=2, every even term is followed by k odd terms. This is explained by the minimal growth of even numbers (2n) relatively with one of the numbers with the smallest prime divisor p>=3 (asymptotically 6n, 15n, 105n/4, 385n/8, ... for p = 3,5,7,11,... respectively (cf. A084967 - A084970)).

(End)

By definition, in contrast to A098550, in this sequence there is a priority for appearance of the primes.

The terms appear to follow a pattern similar to the A064413 and A373390, i.e., the terms are concentrated along just three lines of different gradient, and the lower line consists only of primes. In the first 10000 terms the primes appear in their natural order, and the fixed points are 1, 2, 3, 4, 28, 98; it is likely no more exist. The sequence is conjectured to be a permutation of the positive integers.

The terms appear to follow a pattern similar to the A064413 and A373390, i.e., the terms are concentrated along just three lines of different gradient, and the lower line consists only of primes. In the first 10000 terms the primes appear in their natural order except for a(37) = 19 and a(39) = 17 which are reversed. Many fixed points exist, 2228 in the first 10000 terms, these beginning 1, 12, 16, 18, 24, 32, 40, 48, ... . The sequence is conjectured to be a permutation of the positive integers.