A255582 a(n)=n when n <= 3, otherwise a(n) is the smallest positive number not yet in the sequence such that gcd(a(n), a(n-1)) <= gcd(a(n), a(n-2)) > 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, 34, 25, 17, 35, 51, 40, 42, 38, 36, 19, 44, 57, 46, 45, 23, 48, 69, 50, 54, 52, 58, 56, 29, 49, 87, 63, 60, 77, 62, 55, 31, 65, 93, 70, 66, 64, 74, 68, 37

Offset: 1

Author

Bob Selcoe, Feb 26 2015

Keywords

• nonn
• hear

Comments

This is a permutation of the natural numbers: the proof for A098550 applies with essentially no changes. [Confirmed by N. J. A. Sloane, Feb 27 2015]

For n > 3, all primes first appear in order as composites with one smaller prime (proof similar to that in A098550).

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, followed by 12, 18, 24, 36, 48, 54, 72, etc.

Appears to be very similar to A064413. Compare the respective inverses A255479 and A064664; see also A255482. Speaking very loosely, the ratio a(n)/n seems to be about 1/2, 1, or 3/2, just as for A064413, although this is a long way from being proved for either sequence. David Applegate points out that this is (presumably) because primes p >= 13 always occur as part of a subsequence 2p X p Y 3p, and subsequences 2p X p Y 5p, 2p X p Y 7p, etc. that produced the extra curves in the graph of A098550 just do not happen. - N. J. A. Sloane, Feb 27 2015, Mar 05 2015.

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

Links

• Hiroaki Yamanouchi, Table of n, a(n) for n = 1..10000
• David L. Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. J. A. Sloane, and Reinhard Zumkeller, The Yellowstone Permutation, arXiv preprint arXiv:1501.01669, 2015.

Crossrefs

Cf. A098550, A254077, A064413, A064664, A255480, A255481, A255482, A256974.

A255479 is the inverse permutation.

A256424 is a smoothed version.

A256529 gives the partial sums.

Programs

Haskell

import Data.List (delete)
a255582 n = a255582_list !! (n-1)
a255582_list = 1 : 2 : 3 : f 2 3 [4..] where
   f u v ws = y : f v y (delete y ws) where
              y = head [z | z <- ws, let d = gcd u z, d > 1, gcd v z <= d]
-- Reinhard Zumkeller, Mar 10 2015

Mathematica

a[n_] := a[n] = If[n<5, n, For[k=5, True, k++, If[FreeQ[Array[a, n-1], k], If[GCD[k, a[n-2]]>1 && GCD[k, a[n-1]] <= GCD[k, a[n-2]], Return[k]]]]];
Array[a, 100] (* Jean-François Alcover, Jul 31 2018 *)

Extensions

a(41)-a(67) from Hiroaki Yamanouchi, Feb 27 2015