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

%I #37 Apr 27 2018 17:10:09

%S 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,

%T 75,25,50,70,7,14,28,42,21,63,126,84,56,112,64,96,120,80,100,150,90,

%U 108,81,162,216,144,168,140,35,105,210,180,135,225,300

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

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

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

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

%C 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

%C 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

%H Ivan Neretin and Reinhard Zumkeller, <a href="/A257218/b257218.txt">Table of n, a(n) for n = 1..25000</a>, first 10000 terms from Ivan Neretin

%e 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.

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

%o (Haskell)

%o import Data.List (delete); import Data.List.Ordered (member)

%o a257218 n = a257218_list !! (n-1)

%o a257218_list = 1 : f 1 [2..] a004526_list where

%o f x zs cds = g zs where

%o g (y:ys) | cd `member` cds = y : f y (delete y zs) (delete cd cds)

%o | otherwise = g ys

%o where cd = gcd x y

%o -- _Reinhard Zumkeller_, Apr 24 2015

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

%Y A175498 (differences are unique),

%Y A081145 (absolute differences are unique),

%Y A235262 (bitwise XORs are unique),

%Y A163252 (differ by one bit in binary),

%Y A000027 (GCD=1),

%Y A064413 (GCD>1),

%Y A128280 (sum is a prime),

%Y A034175 (sum is a square),

%Y A175428 (sum is a cube),

%Y A077220 (sum is a triangular number),

%Y A073666 (product plus 1 is a prime),

%Y A081943 (product minus 1 is a prime),

%Y A091569 (product plus 1 is a square),

%Y A100208 (sum of squares is a prime).

%Y Cf. A004526.

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

%Y Cf. also A281978.

%K nonn,look

%O 1,2

%A _Ivan Neretin_, Apr 18 2015