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.
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, 73, 25, 27, 79, 83, 16, 49, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 85, 193, 57, 197, 199, 211, 223
Offset: 1
Examples
a(1) = 2 must be rel. prime to a(2), so a(2)=3. a(2) = 3 must be rel. prime to a(3) and a(4), so we can take them to be 4 and 5. a(3) = 4 must be rel. prime to a(5), a(6), so we must take them to be 7,9. a(4) = 5 must be rel. prime to a(7), a(8), so we must take them to be 8,11. 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.
References
- Amarnath Murthy, Email to N. J. A. Sloane, Oct 05 2014.
Links
- Russ Cox, Table of n, a(n) for n = 1..100000
- Russ Cox, Go program (can compute 5 million terms in about 5 minutes)
- Russ Cox, Table of n, a(n) for n = 1..203299677, composite a(n) only; a(203299678) > 2^32.
Crossrefs
Programs
-
Haskell
a247665 n = a247665_list !! (n-1) a247665_list = 2 : 3 : f [3] [4..] where f (x:xs) zs = ys ++ f (xs ++ ys) (zs \\ ys) where ys = [v, head [w | w <- vs, gcd v w == 1]] (v:vs) = filter (\u -> gcd u x == 1 && all ((== 1) . (gcd u)) xs) zs -- Reinhard Zumkeller, Oct 09 2014 -
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
-
Python
from itertools import count, islice from math import gcd from collections import deque def A247665_gen(): # generator of terms aset, aqueue, c, f = {2}, deque([2]), 3, True yield 2 while True: for m in count(c): if m not in aset and all(gcd(m,a) == 1 for a in aqueue): yield m aset.add(m) aqueue.append(m) if f: aqueue.popleft() f = not f while c in aset: c += 1 break A247665_list = list(islice(A247665_gen(),50)) # Chai Wah Wu, May 19 2022
-
Sage
# s is the starting point (2 in A247665). def gen(s): sequence = [s] available = list(range(2,2*s)) available.pop(available.index(s)) yield s while True: available.extend(range(available[-1]+1,next_prime(available[-1])+1)) for i,e in enumerate(available): if all(gcd(e, sequence[j])==1 for j in range(-len(sequence)//2,0)): available.pop(i) sequence.append(e) yield(e) break g = gen(2) [next(g) for i in range(40)] # (gets first 40 terms of A247665) # Nadia Heninger, Oct 28 2014
Extensions
More terms from Jens Kruse Andersen, Oct 06 2014
Further terms from Russ Cox, Oct 08 2014
Added condition a(n) >= 2 to definition. - N. J. A. Sloane, May 16 2022
Comments