A255582 -id:A255582 - cp's OEIS frontend

A254077 a(n) = n if n <= 3, otherwise the smallest number not occurring earlier such that gcd(a(n),a(n-2)) > gcd(a(n),a(n-1)).

1, 2, 3, 4, 6, 8, 9, 10, 12, 5, 14, 15, 7, 18, 21, 16, 27, 20, 33, 24, 11, 26, 22, 13, 28, 39, 32, 30, 44, 25, 34, 35, 17, 40, 51, 36, 68, 42, 52, 45, 38, 48, 19, 46, 57, 23, 54, 69, 50, 63, 55, 49, 60, 56, 65, 58, 70, 29, 62, 87, 31, 66, 93, 64, 75, 72, 85, 74, 80, 37, 76, 111

Offset: 1

Vladimir Shevelev, Jan 25 2015

nonn

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

Peter J. C. Moses and Ray Chandler, Table of n, a(n) for n = 1..10000 (first 1000 terms from Peter J. C. Moses)
David L. Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. J. A. Sloane, and Reinhard Zumkeller, The Yellowstone Permutation, arXiv preprint arXiv:1501.01669 [math.NT], 2015.
John P. Linderman, Table of n, a(n) for n = 1..1000000 (about 13MB)
John P. Linderman, Table of n, a(n) for n = 1..12940331 (about 61MB)
John P. Linderman, Go program [Revised Jun 29 2015]
John P. Linderman, Notes on computation of first 5 billion terms
John Mason, Some observations
John Mason, Some proofs
John Mason, Proof of theorem: If the sequence is infinite, it is a permutation of the positive integers

Cf. A098550, A247225, A247942, A249167, A251604, A256974, A318826.
For indices of primes see A256213. Sequence mod 2 is A257585.
Changing > in definition to >= produces A255582 (which DOES exist).
Cf. A256528 (partial sums).

a254077 n = a254077_list !! (n-1)
a254077_list = 1 : 2 : 3 : f 2 3 [4..] where
   f u v ws = g ws where
     g (x:xs) = if gcd x u > gcd x v then x : f v x (delete x ws) else g xs
-- Reinhard Zumkeller, May 05 2015

f[n_] := Block[{s = Range@ n, j, k}, For[k = 4, k <= n, k++, j = 4; While[Nand[GCD[j, s[[k - 2]]] > GCD[j, s[[k - 1]]], !MemberQ[Take[s, k - 1], j]], j++]; s[[k]] = j]; s]; f@ 72 (* Michael De Vlieger, Apr 15 2015 *)

More terms from Peter J. C. Moses, Jan 25 2015

A270139 a(n)=n when n<=3, otherwise a(n) is the smallest unused positive integer which is not coprime to the two previous terms.

Original entry on oeis.org

1, 2, 3, 6, 9, 12, 15, 10, 5, 20, 25, 30, 35, 14, 7, 21, 28, 18, 4, 8, 16, 22, 24, 26, 32, 34, 36, 38, 40, 42, 44, 33, 11, 55, 66, 45, 27, 39, 48, 51, 54, 57, 60, 63, 56, 49, 70, 77, 84, 88, 46, 50, 52, 58, 62, 64, 68, 72, 74, 76, 78, 80, 65, 75, 85, 90, 95, 100, 105, 96

Offset: 1

Ivan Neretin, Mar 11 2016

nonn

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.

			a(12) = 30, a(13) = 35, so a(14) must have common factors (possibly different) with 30 and 35, and the smallest unused number with that property turns out to be 14, so a(14) = 14.

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A064413, A084937, A098550, A121216, A121217, A254077, A255582, A336957.

a = {1, 2, 3}; Do[k = 1; While[(MemberQ[a, k] || GCD[a[[-1]], k] == 1 || GCD[a[[-2]], k] == 1), k++]; AppendTo[a, k], {n, 2, 68}]; a

A255482 a(n) = A064664(n)-A255479(n).

Original entry on oeis.org

0, 0, 2, -1, 0, -1, 1, 2, -1, 1, -1, -2, 4, 2, -1, 1, 2, -2, -1, 0, 0, -4, 0, -4, -6, 5, 5, 1, 6, -5, 2, 4, 2, 3, -7, -7, 0, 0, 3, 6, -4, 0, 0, 2, -3, 1, -1, 1, -2, 0, 1, -1, -1, 1, -5, -1, -2, 7, -1, -3, -4, 3, -3, 0, -6

Offset: 1

N. J. A. Sloane, Feb 28 2015

sign

Gives an idea of how similar A255582 is to A064413.

Ray Chandler, Table of n, a(n) for n = 1..10000

Cf. A064413, A255582, A064664, A255479.

a255482 n = a064664 n - a255479 n  -- Reinhard Zumkeller, Mar 10 2015

A256528 Partial sums of A254077.

Original entry on oeis.org

1, 3, 6, 10, 16, 24, 33, 43, 55, 60, 74, 89, 96, 114, 135, 151, 178, 198, 231, 255, 266, 292, 314, 327, 355, 394, 426, 456, 500, 525, 559, 594, 611, 651, 702, 738, 806, 848, 900, 945, 983, 1031, 1050, 1096, 1153, 1176, 1230, 1299, 1349, 1412, 1467, 1516, 1576, 1632, 1697, 1755, 1825, 1854, 1916, 2003, 2034, 2100, 2193, 2257

Offset: 1

Omar E. Pol, May 08 2015

nonn

First differs from A256529 at a(29).

Cf. A065057, A098550, A253768, A254077, A255582, A256529, A256974.

A339670 a(1) = 2, a(2) = 3; for n>2, a(n) = smallest number not already used that shares a prime factor with a(n-2) and has a prime factor not in a(n-1).

Original entry on oeis.org

2, 3, 4, 6, 10, 9, 5, 12, 15, 8, 18, 14, 20, 7, 16, 21, 22, 24, 11, 26, 33, 13, 27, 39, 30, 42, 25, 28, 35, 32, 40, 34, 36, 17, 38, 51, 19, 45, 57, 48, 60, 44, 46, 50, 23, 52, 69, 54, 63, 56, 66, 49, 55, 70, 65, 58, 75, 29, 72, 87, 62, 78, 31, 64, 93, 68, 81, 74, 84, 37, 76, 111, 80, 90, 82

Offset: 1

Scott R. Shannon, Dec 12 2020

nonn

Inspired by A064413 and A336957. The terms show a similar pattern to A064413, and like that sequence they are likely a permutation of the positive integers.

See A339671 for a similar sequence where the prime factor rules are reversed.

			a(4) = 4 as a(3) = 4 = 2*2 and a(2) = 2, thus a(4) must contain 2 as a prime factor but must also contain a prime factor other than 2. The lowest unused number matching these criteria is 2*3 = 6.
a(7) = 9 as a(6) = 10 = 2*5 and a(5) = 6 = 2*3, thus a(7) must contain 2 or 3 as a prime factor but must also contain a prime factor other than 2 and 5. The lowest unused number matching these criteria is 3*3 = 9.

Cf. A064413, A336957, A098550, A255582, A020639.

Block[{a = {1, 2, 3}, b = {2}, c = {3}, p, k}, Do[k = 2; While[Nand[FreeQ[a, k], IntersectingQ[b, Set[p, FactorInteger[k][[All, 1]]]], Length@ Complement[p, Intersection[c, p]] > 0], k++]; AppendTo[a, k]; b = c; c = p, 73]; a] (* Michael De Vlieger, Dec 12 2020 *)

A339671 a(1) = 1, a(2) = 2; for n>2, a(n) = smallest number not already used that shares a prime factor with a(n-1) and has a prime factor not in a(n-2).

Original entry on oeis.org

1, 2, 4, 6, 3, 15, 5, 10, 8, 12, 9, 21, 7, 14, 16, 18, 20, 22, 11, 33, 24, 26, 13, 39, 27, 30, 25, 35, 28, 32, 34, 17, 51, 36, 38, 19, 57, 42, 40, 44, 46, 23, 69, 45, 48, 50, 52, 54, 56, 49, 63, 60, 55, 65, 70, 58, 29, 87, 66, 62, 31, 93, 72, 64, 68, 74, 37, 111, 75, 78, 76, 80, 82, 41, 123, 81

Offset: 1

Scott R. Shannon, Dec 12 2020

nonn

Inspired by A064413 and A336957. The terms show a similar pattern to A064413, and like that sequence they are likely a permutation of the positive integers. Many terms also match the values in A169837. For example a(17)=20 to a(115)=111 (shifted by an index of 1) are the same, but then differ again before more matches occurr.

See A339670 for a similar sequence where the prime factor rules are reversed.

			a(4) = 6 as a(3) = 4 = 2*2 and a(2) = 2, thus a(4) must contain 2 as a prime factor but must also contain a prime factor other than 2. The lowest unused number matching these criteria is 2*3 = 6.
a(6) = 15 as a(5) = 3 and a(4) = 6 = 2*3, thus a(6) must contain 3 as a prime factor but must also contain a prime factor other than 2 and 3. The lowest unused number matching these criteria is 3*5 = 15. This is the first term that differs from A064413.

Cf. A339670, A064413, A169837, A336957, A098550, A255582, A020639.

Block[{a = {1, 2}, b = {}, c = {2}, p, k}, Do[k = 2; While[Nand[FreeQ[a, k], IntersectingQ[c, Set[p, FactorInteger[k][[All, 1]]]], Length@ Complement[p, Intersection[b, p]] > 0], k++]; AppendTo[a, k]; b = c; c = p, 75]; a] (* Michael De Vlieger, Dec 12 2020 *)

A263650 A variation on A098550 (the Yellowstone permutation): a(n)=n for 1 <= n <= 3, a(4)=5; otherwise a(n) = smallest number not yet appearing in the sequence which is coprime to a(n-1) and not coprime to a(n-2).

Original entry on oeis.org

1, 2, 3, 5, 6, 25, 4, 15, 8, 9, 10, 21, 16, 7, 12, 35, 18, 49, 20, 63, 22, 27, 11, 24, 55, 14, 33, 26, 45, 13, 30, 91, 32, 39, 28, 51, 38, 17, 19, 34, 57, 40, 69, 44, 23, 36, 115, 42, 65, 46, 75, 52, 81, 50, 87, 56, 29, 48, 145, 54, 85, 58, 95, 62, 105, 31, 60, 217, 64

Offset: 1

Bob Selcoe, Oct 22 2015

nonn

Proof that this is a permutation of the natural numbers follows the same basic format as the proof contained in A098550.

This sequence is one in a multitude of permutations of definable infinite sets (i.e., "infinite permutations") which share similar properties and similar proofs as A098550 (Yellowstone-type), and which are often (though not always - see for example A119718 and A255582) of the general form: a(n) is smallest number not yet appearing in the sequence which is coprime to a(n-1) and not coprime to a(n-2). But caution is warranted here: many sequences which may appear at first glance to be Yellowstone-type infinite permutations are not (e.g., A263648 is infinite, similar in structure to A119718 and even MORE similar to the general Yellowstone form, yet is not a permutation) or may not be provable in similar fashion (e.g., A254077, which is similar in structure to A255582 but cannot be demonstrated as infinite using Yellowstone-type constructions). What observations or generalizations might we draw from this?

Jean-François Alcover, Table of n, a(n) for n = 1..1000
David L. Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. J. A. Sloane, and Reinhard Zumkeller, The Yellowstone Permutation, arXiv preprint arXiv:1501.01669 [math.NT], 2015.
David L. Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. J. A. Sloane, and Reinhard Zumkeller, The Yellowstone Permutation, Journal of Integer Sequences, Vol. 18 (2015), Article 15.6.7

Cf. A098550, A119718, A255582, A263648.

a[n_] := a[n] = If[n <= 4, {1, 2, 3, 5}[[n]], For[k = 4, True, k++, If[CoprimeQ[k, a[n-1]] && !CoprimeQ[k, a[n-2]], If[FreeQ[Array[a, n-1], k], Return[k]]]]]; Array[a, 100] (* Jean-François Alcover, Feb 11 2019 *)

Corrected and extended by Jean-François Alcover, Feb 11 2019

cp's OEIS Frontend

A254077 a(n) = n if n <= 3, otherwise the smallest number not occurring earlier such that gcd(a(n),a(n-2)) > gcd(a(n),a(n-1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

A270139 a(n)=n when n<=3, otherwise a(n) is the smallest unused positive integer which is not coprime to the two previous terms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A255482 a(n) = A064664(n)-A255479(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A256528 Partial sums of A254077.

Views

Author

Keywords

Comments

Crossrefs

A339670 a(1) = 2, a(2) = 3; for n>2, a(n) = smallest number not already used that shares a prime factor with a(n-2) and has a prime factor not in a(n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A339671 a(1) = 1, a(2) = 2; for n>2, a(n) = smallest number not already used that shares a prime factor with a(n-1) and has a prime factor not in a(n-2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A263650 A variation on A098550 (the Yellowstone permutation): a(n)=n for 1 <= n <= 3, a(4)=5; otherwise a(n) = smallest number not yet appearing in the sequence which is coprime to a(n-1) and not coprime to a(n-2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions