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

Author

Leroy Quet, Dec 04 2003

Keywords

• nonn
• nice
• easy

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

Crossrefs

Cf. A064413.

Cf. A112975.

Programs

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

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 *)

Extensions

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