A257218 Lexicographically earliest sequence of distinct positive integers such that gcd(a(n), a(n-1)) takes no value more than twice.

1, 2, 3, 6, 4, 8, 10, 5, 15, 9, 18, 12, 16, 24, 30, 20, 40, 32, 48, 36, 27, 54, 72, 60, 45, 75, 25, 50, 70, 7, 14, 28, 42, 21, 63, 126, 84, 56, 112, 64, 96, 120, 80, 100, 150, 90, 108, 81, 162, 216, 144, 168, 140, 35, 105, 210, 180, 135, 225, 300

Offset: 1

Author

Ivan Neretin, Apr 18 2015

Keywords

• nonn
• look

Comments

Presumably a(n) is a permutation of the positive integers.

Primes seem to occur in their natural order. 31 appears as a(7060). Primes p >= 37 are not found among the first 10000 terms.

Numbers n such that a(n)=n are 1, 2, 3, 12, 306, ...

A256918(n) = gcd(a(n), a(n+1)); gcd(a(A257120(n)), a(A257120(n)+1)) = gcd(a(A257475(n)), a(A257475(n)-1)) = n. - Reinhard Zumkeller, Apr 25 2015

For p prime: A257122(p)-1 = index of the smallest multiple of p: a(A257122(p)-1) mod p = 0 and a(m) mod p > 0 for m < A257122(p)-1. - Reinhard Zumkeller, Apr 26 2015

Examples

			After a(9)=15, the values 1, 2, 3, 4, 6, and 8 are already used, while 7 is forbidden because gcd(15,7)=1 and that value of GCD has already occurred twice, at (1,2) and (2,3). The minimal value which is neither used not forbidden is 9, so a(10)=9.
		

Links

• Ivan Neretin and Reinhard Zumkeller, Table of n, a(n) for n = 1..25000, first 10000 terms from Ivan Neretin

Crossrefs

Other minimal sequences of distinct positive integers that match some condition imposed on a(n) and a(n-1):

A175498 (differences are unique),

A081145 (absolute differences are unique),

A235262 (bitwise XORs are unique),

A163252 (differ by one bit in binary),

A000027 (GCD=1),

A064413 (GCD>1),

A128280 (sum is a prime),

A034175 (sum is a square),

A175428 (sum is a cube),

A077220 (sum is a triangular number),

A073666 (product plus 1 is a prime),

A081943 (product minus 1 is a prime),

A091569 (product plus 1 is a square),

A100208 (sum of squares is a prime).

Cf. A004526.

Cf. A256918, A257120, A257475, A257478, A257122 (putative inverse).

Cf. also A281978.

Programs

Haskell

import Data.List (delete); import Data.List.Ordered (member)
a257218 n = a257218_list !! (n-1)
a257218_list = 1 : f 1 [2..] a004526_list where
   f x zs cds = g zs where
     g (y:ys) | cd `member` cds = y : f y (delete y zs) (delete cd cds)
              | otherwise       = g ys
              where cd = gcd x y
-- Reinhard Zumkeller, Apr 24 2015

Mathematica

a={1}; used=Array[0&,10000]; Do[i=1; While[MemberQ[a,i] || used[[l=GCD[a[[-1]],i]]]>=2, i++]; used[[l]]++; AppendTo[a,i], {n,2,100}]; a (* Ivan Neretin, Apr 18 2015 *)