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.

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

Author

Masahiko Shin, Feb 11 2018

Keywords

• easy
• nonn

Examples

			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.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Crossrefs

Cf. A005117 (when coprimality condition is changed to divisibility and "even number of terms" is replaced by odd).

Programs

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

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

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))

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)