cp's OEIS Frontend

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.

%I A294269 #41 Apr 16 2024 10:37:51
%S A294269 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,
%T A294269 27,29,30,28,31,33,34,32,35,37,38,36,39,41,42,40,43,45,46,44,47,49,50,
%U A294269 48,51,53,54,52,55,57,58,56,59,61,62,60,63,65,66,64,67
%N 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.
%H A294269 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,1,-1).
%F A294269 From _Robert Israel_, Apr 15 2024: (Start)
%F A294269 G.f.: -1 + 2 * x + (2 - 2 * x + 3 * x^2 + 2 * x^3 - x^4)/(1 - x - x^4 + x^5).
%F A294269 a(n) = a(n - 1) + a(n - 4) - a(n - 5) for n >= 8.
%F A294269 (End)
%e A294269 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.
%p A294269 R:= [1]:
%p A294269 Cands:= [$2..200]:
%p A294269 for n from 2 to 100 do
%p A294269   found:= false;
%p A294269   for i from 1 to nops(Cands) do
%p A294269     x:= Cands[i];
%p A294269     if nops(select(t -> igcd(t,x) > 1, R))::even then
%p A294269        R:= [op(R),x];
%p A294269        Cands:= subsop(i=NULL,Cands);
%p A294269        found:= true;
%p A294269        break
%p A294269     fi
%p A294269   od;
%p A294269   if not found then break fi;
%p A294269 od:
%p A294269 R; # _Robert Israel_, Apr 15 2024
%t A294269 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 *)
%o A294269 (Python)
%o A294269 from math import gcd
%o A294269 def getSeq(n):
%o A294269     if n == 1:
%o A294269         return [1]
%o A294269     prev = getSeq(n-1)
%o A294269     cand = 1
%o A294269     while True:
%o A294269         cand += 1
%o A294269         if cand in prev:
%o A294269             continue
%o A294269         if len([n for n in prev if gcd(cand, n) > 1]) % 2 == 0:
%o A294269             prev.append(cand)
%o A294269             return prev
%o A294269 print(getSeq(100))
%o A294269 (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);}
%o A294269 lista(nn) = {va = [1]; for (n=2, nn, new = findnext(va, n); va = concat(va, new);); va;} \\ _Michel Marcus_, Mar 29 2018
%Y A294269 Cf. A005117 (when coprimality condition is changed to divisibility and "even number of terms" is replaced by odd).
%K A294269 easy,nonn
%O A294269 1,2
%A A294269 _Masahiko Shin_, Feb 11 2018