A089088 a(0) = 1, a(1) = 2; for n > 1, a(n) = smallest positive number not already in sequence which has GCD > 1 with some earlier term.

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

Offset

0,2

Comments

This is a permutation of the natural numbers.

For n > 2: a(n) is prime iff a(n) < a(n-1); a(A112988(n)) = A000040(n); inverse: A112990. - Reinhard Zumkeller, Oct 08 2005

For n > 3, a(n) can be described as follows: all composite numbers in natural order, with primes inserted so that every prime p immediately follows 2p. - Ivan Neretin, Apr 26 2015

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

Index entries for sequences that are permutations of the natural numbers

Mathematica

A089088 = {a[0] = 1, a[1] = 2}; a[n_] := Catch[For[k = Min[ Complement[ Range[Max[A089088] + 1], A089088]], True, k++, If[ !MemberQ[A089088, k] && Or @@ (GCD[k, #] > 1&) /@ A089088, AppendTo[A089088, k]; Throw[k]]]]; Table[a[n], {n, 0, 88}] (* Jean-François Alcover, Jul 18 2012 *)
Nest[Append[#1, Block[{k = 1}, While[Nand[FreeQ[#1, k], AnyTrue[#1, ! CoprimeQ[#, k] &]], k++]; k]] &, {1, 2}, 87] (* Michael De Vlieger, Nov 18 2017 *)

Prog

(Haskell)
import Data.List (delete)
a089088 n = a089088_list !! n
a089088_list = 1 : 2 : f [3..] [1, 2] where
  f xs ys = y : f (delete y xs) (y : ys) where
    y = head $ filter (\z -> any (> 1) $ map (gcd z) ys) xs
-- Reinhard Zumkeller, Feb 27 2013

Crossrefs

Cf. A064413.

Cf. A112975.

Sequence in context: A210771 A359535 A115316 * A251622 A073899 A232846

Adjacent sequences: A089085 A089086 A089087 * A089089 A089090 A089091

Keyword

nonn,nice,easy

Author

Leroy Quet, Dec 04 2003

Extensions

More terms from Victoria A Sapko (vsapko(AT)canes.gsw.edu), Jun 16 2004

Status

approved