cp's OEIS Frontend

A247665 a(1)=2; thereafter a(n) is the smallest number >= 2 not yet used which is compatible with the condition that a(n) is relatively prime to the next n terms.

%I A247665 #99 May 19 2022 11:44:15
%S A247665 2,3,4,5,7,9,8,11,13,17,19,23,15,29,14,31,37,41,43,47,53,59,61,67,71,
%T A247665 73,25,27,79,83,16,49,89,97,101,103,107,109,113,121,127,131,137,139,
%U A247665 149,151,157,163,167,169,173,179,181,191,85,193,57,197,199,211,223
%N A247665 a(1)=2; thereafter a(n) is the smallest number >= 2 not yet used which is compatible with the condition that a(n) is relatively prime to the next n terms.
%C A247665 It appears that a(k) is even iff k = 2^i-1 (cf. A248379). It also appears that all powers of 2 occur in the sequence. (_Amarnath Murthy_)
%C A247665 The indices of even terms and their values are [1, 2], [3, 4], [7, 8], [15, 14], [31, 16], [63, 32], [127, 64], [255, 128], [511, 122], ...
%C A247665 Will the numbers 6, 10, 21, 22, ... ever occur? 12, 18, 20, ... are also missing, but if 6 never appears then neither will 12, etc.
%C A247665 A related question: are all terms deficient? - _Peter Munn_, Jul 20 2017
%C A247665 It appears that the missing numbers are 6, 10, 12, 18, 20, 21, 22, 24, 26, 28, 30, 33, 34, 35, 36, 38, 39, 40, 42, ..., but since there is no proof that any one of these is really missing, this sequence cannot yet be added to the OEIS. - _N. J. A. Sloane_, May 18 2022
%D A247665 _Amarnath Murthy_, Email to _N. J. A. Sloane_, Oct 05 2014.
%H A247665 Russ Cox, <a href="/A247665/b247665.txt">Table of n, a(n) for n = 1..100000</a>
%H A247665 Russ Cox, <a href="/A247665/a247665.go.txt">Go program</a> (can compute 5 million terms in about 5 minutes)
%H A247665 Russ Cox, <a href="/A247665/a247665.txt">Table of n, a(n) for n = 1..203299677, composite a(n) only</a>; a(203299678) > 2^32.
%e A247665 a(1) = 2 must be rel. prime to a(2), so a(2)=3.
%e A247665 a(2) = 3 must be rel. prime to a(3) and a(4), so we can take them to be 4 and 5.
%e A247665 a(3) = 4 must be rel. prime to a(5), a(6), so we must take them to be 7,9.
%e A247665 a(4) = 5 must be rel. prime to a(7), a(8), so we must take them to be 8,11.
%e A247665 At each step after the first, we must choose two new numbers, and we must make sure that not only are they rel. prime to a(n), they are also rel. prime to all a(i), i>n, that have been already chosen.
%o A247665 (PARI) m=100; v=vector(m); u=vectorsmall(100*m); for(n=1, m, for(i=2, 10^9, if(!u[i], for(j=(n+1)\2, n-1, if(gcd(v[j], i)>1, next(2))); v[n]=i; u[i]=1; break))); v \\ _Jens Kruse Andersen_, Oct 08 2014
%o A247665 (Haskell)
%o A247665 a247665 n = a247665_list !! (n-1)
%o A247665 a247665_list = 2 : 3 : f [3] [4..] where
%o A247665    f (x:xs) zs = ys ++ f (xs ++ ys) (zs \\ ys) where
%o A247665      ys = [v, head [w | w <- vs, gcd v w == 1]]
%o A247665      (v:vs) = filter (\u -> gcd u x == 1 && all ((== 1) . (gcd u)) xs) zs
%o A247665 -- _Reinhard Zumkeller_, Oct 09 2014
%o A247665 (Sage)
%o A247665 # s is the starting point (2 in A247665).
%o A247665 def gen(s):
%o A247665     sequence = [s]
%o A247665     available = list(range(2,2*s))
%o A247665     available.pop(available.index(s))
%o A247665     yield s
%o A247665     while True:
%o A247665         available.extend(range(available[-1]+1,next_prime(available[-1])+1))
%o A247665         for i,e in enumerate(available):
%o A247665             if all(gcd(e, sequence[j])==1 for j in range(-len(sequence)//2,0)):
%o A247665                 available.pop(i)
%o A247665                 sequence.append(e)
%o A247665                 yield(e)
%o A247665                 break
%o A247665 g = gen(2)
%o A247665 [next(g) for i in range(40)]  # (gets first 40 terms of A247665)
%o A247665 # _Nadia Heninger_, Oct 28 2014
%o A247665 (Python)
%o A247665 from itertools import count, islice
%o A247665 from math import gcd
%o A247665 from collections import deque
%o A247665 def A247665_gen(): # generator of terms
%o A247665     aset, aqueue, c, f = {2}, deque([2]), 3, True
%o A247665     yield 2
%o A247665     while True:
%o A247665         for m in count(c):
%o A247665             if m not in aset and all(gcd(m,a) == 1 for a in aqueue):
%o A247665                 yield m
%o A247665                 aset.add(m)
%o A247665                 aqueue.append(m)
%o A247665                 if f: aqueue.popleft()
%o A247665                 f = not f
%o A247665                 while c in aset:
%o A247665                     c += 1
%o A247665                 break
%o A247665 A247665_list = list(islice(A247665_gen(),50)) # _Chai Wah Wu_, May 19 2022
%Y A247665 Cf. A248379, A248381, A248388, A248389, A248390, A248391, A249049, A249050, A249058, A249556, A353730.
%Y A247665 Indices of primes and prime powers: A248387, A248918.
%Y A247665 Lengths of runs of primes: A249033.
%Y A247665 A090252 = similar to A247665 but start with a(1)=1. A249559 starts with a(1)=3.
%Y A247665 A249064 is a different generalization.
%Y A247665 A064413 is another similar sequence.
%K A247665 nonn,look
%O A247665 1,1
%A A247665 _N. J. A. Sloane_, Oct 06 2014 and Oct 08 2014
%E A247665 More terms from _Jens Kruse Andersen_, Oct 06 2014
%E A247665 Further terms from _Russ Cox_, Oct 08 2014
%E A247665 Added condition a(n) >= 2 to definition. - _N. J. A. Sloane_, May 16 2022