A089088 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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

Felix Huber, Table of n, a(n) for n = 0..10000 (terms up to a(1000) from Reinhard Zumkeller)

Index entries for sequences that are permutations of the natural numbers

MAPLE

with(NumberTheory):

A089088list:=proc(N) # To get the terms a(0) .. a(N)

local a, i, k, m, p;

if N=0 then 1 elif N=1 then 1, 2 else

m:=N+pi(N)+2;

a:=remove(x->isprime(x) and x>2, [seq(i, i=1..m)]);

for i from 2 to pi(floor(m/2)) do

p:=ithprime(i);

k:=ListTools:-BinaryPlace(a, 2*p+1);

a:=[op(1..k, a), p, op(k+1..-1, a)];

od;

return op(1..N+1, a);

end proc;

A089088list(67); # Felix Huber, Nov 03 2025

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: A359535 A115316 A375327 * A251622 A073899 A394858