cp's OEIS Frontend

If the conjecture in A251604 is true, this sequence is the inverse permutation.

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

The sequence differs from A098550 from a(11) onward.

The sequence is a permutation of the natural numbers. The proof is similar to that for A098550 (with minor changes). - Vladimir Shevelev, Jan 14 2015

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)

All terms must contain two or more distinct prime factors. If a(n) was a prime power then a(n+1) would contain the same prime factor, which in turn would imply that a(n) + a(n+1) is a multiple of the prime. But that would make finding a(n+2) impossible as any factor of a(n) would also be a factor of the sum.

To ensure the sequence is infinite a(n) must also contain a prime factor not in a(n-1). If this were not the case the sum a(n-1) + a(n) would be a multiple of the distinct prime factors of a(n), implying a(n+1) would not exist as any factor of a(n) would be a factor of the sum.

The last even term is a(114) = 210. As a(115) = 119 and a(116) = 255, the first occurrence of consecutive odd values, the resulting sum is even, so a(117) must be odd. This forces all subsequent terms to also be odd.

There is a concentration of terms at a(n) ~ 3.4*n. See the linked image. The only fixed point in the first 50000 terms is 14, although it is possible more exist.

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

To ensure the sequence is infinite another criterion must be satisfied when choosing a(n), namely a(n) + a(n-1) must contain a factor not in a(n-1). If this were not the case, a(n+1) = a(n) + a(n-1) would share a factor with both a(n) + a(n-1) and a(n-1), terminating the sequence.

In the first 100000 terms the fixed points for n > 2 are 3, 6, 441, 1677, 3629, 9701, 17131, although it is likely more exist. The sequence is conjectured to be a permutation of the positive integers.