login
A294269
a(n) is the smallest number not already in the sequence which shares a factor with an even number of preceding terms; a(1) = 1.
0
1, 2, 3, 5, 6, 4, 7, 9, 10, 8, 11, 13, 14, 12, 15, 17, 18, 16, 19, 21, 22, 20, 23, 25, 26, 24, 27, 29, 30, 28, 31, 33, 34, 32, 35, 37, 38, 36, 39, 41, 42, 40, 43, 45, 46, 44, 47, 49, 50, 48, 51, 53, 54, 52, 55, 57, 58, 56, 59, 61, 62, 60, 63, 65, 66, 64, 67
OFFSET
1,2
FORMULA
From Robert Israel, Apr 15 2024: (Start)
G.f.: -1 + 2 * x + (2 - 2 * x + 3 * x^2 + 2 * x^3 - x^4)/(1 - x - x^4 + x^5).
a(n) = a(n - 1) + a(n - 4) - a(n - 5) for n >= 8.
(End)
EXAMPLE
6 is in the sequence because there are even number of terms (i.e., a(2) = 2, a(3) = 3) which are not coprime to 6 and it is the smallest such number not already in the sequence.
MAPLE
R:= [1]:
Cands:= [$2..200]:
for n from 2 to 100 do
found:= false;
for i from 1 to nops(Cands) do
x:= Cands[i];
if nops(select(t -> igcd(t, x) > 1, R))::even then
R:= [op(R), x];
Cands:= subsop(i=NULL, Cands);
found:= true;
break
fi
od;
if not found then break fi;
od:
R; # Robert Israel, Apr 15 2024
MATHEMATICA
With[{nn = 66}, Nest[Function[a, Append[a, SelectFirst[Range[Min@ a + 1, Min@ a + 2 nn], Function[k, And[FreeQ[a, k], Mod[Count[a, _?(CoprimeQ[#, k] &)], 2] == Mod[Length@ a, 2]]]]]], {1}, nn]] (* Michael De Vlieger, Feb 20 2018 *)
PROG
(Python)
from math import gcd
def getSeq(n):
if n == 1:
return [1]
prev = getSeq(n-1)
cand = 1
while True:
cand += 1
if cand in prev:
continue
if len([n for n in prev if gcd(cand, n) > 1]) % 2 == 0:
prev.append(cand)
return prev
print(getSeq(100))
(PARI) findnext(va, nb) = {ok = 0; x = 1; vao = vecsort(va); while (!ok, if (! vecsearch(vao, x) && !(sum(k=1, nb-1, gcd(x, va[k])!=1) % 2), ok = 1, x++); ); return (x); }
lista(nn) = {va = [1]; for (n=2, nn, new = findnext(va, n); va = concat(va, new); ); va; } \\ Michel Marcus, Mar 29 2018
CROSSREFS
Cf. A005117 (when coprimality condition is changed to divisibility and "even number of terms" is replaced by odd).
Sequence in context: A122348 A130951 A130386 * A330647 A209260 A297409
KEYWORD
easy,nonn
AUTHOR
Masahiko Shin, Feb 11 2018
STATUS
approved