login
A generalized Stern sequence.
7

%I #37 Sep 07 2024 08:55:21

%S 1,1,1,1,2,1,2,1,3,2,2,1,4,2,2,1,5,3,3,2,5,2,3,1,6,4,3,2,6,2,3,1,7,5,

%T 4,3,8,3,5,2,8,5,4,2,8,3,3,1,9,6,5,4,9,3,6,2,9,6,4,2,9,3,3,1,10,7,6,5,

%U 11,4,8,3,12,8,6,3,13,5,5,2,13,8,7,5,12,4,7,2,12,8,5,3,11,3,4,1,12,9,7,6

%N A generalized Stern sequence.

%C Conjectures: a(2^n)=a(2^(n+1)+1)=A033638(n); a(2^n-1)=a(3*2^n-1)=1.

%C The Gi1 and Gi2 triangle sums, see A180662 for their definitions, of Sierpinski's triangle A047999 equal this sequence. The Gi1 and Gi2 sums can also be interpreted as (i + 4*j = n) and (4*i + j = n) sums, see the Northshield reference. Some A112970(2^n-p) sequences, 0<=p<=32, lead to known sequences, see the crossrefs. - _Johannes W. Meijer_, Jun 05 2011

%H Sam Northshield, <a href="https://citeseerx.ist.psu.edu/pdf/a765e1f8064266bf3e36c34bf5c60bb8bb32d392">Sums across Pascal’s triangle modulo 2</a>, Congressus Numerantium, 200, pp. 35-52, 2010. [_Johannes W. Meijer_, Jun 05 2011]

%F a(n) = Sum_{k=0..n} mod(sum{j=0..n, (-1)^(n-k)*C(j, n-j)*C(k, j-k)}, 2).

%F From _Johannes W. Meijer_, Jun 05 2011: (Start)

%F a(2*n+1) = a(n) and a(2*n) = a(n) + a(n-2) with a(0) = 1, a(1) = 1 and a(n)=0 for n<=-1.

%F G.f.: Product_{n>=0} (1 + x^(2^n) + x^(4*2^n)). (End)

%F G.f. A(x) satisfies: A(x) = (1 + x + x^4) * A(x^2). - _Ilya Gutkovskiy_, Jul 09 2019

%p A112970:=proc(n) option remember; if n <0 then A112970(n):=0 fi: if (n=0 or n=1) then 1 elif n mod 2 = 0 then A112970(n/2) + A112970((n/2)-2) else A112970((n-1)/2); fi; end: seq(A112970(n),n=0..99); # _Johannes W. Meijer_, Jun 05 2011

%t a[n_] := a[n] = Which[n<0, 0, n==0 || n==1, 1, Mod[n, 2]==0, a[n/2] + a[n/2-2], True, a[(n-1)/2]];

%t Table[a[n], {n, 0, 99}] (* _Jean-François Alcover_, Aug 02 2022 *)

%Y Cf. A002487, A112971.

%Y Cf. A120562 (Northshield).

%Y Cf. A033638 (p=0), A000012 (p=1), A004526 (p=2, p=3, p=5, p=9, p=17), A002620 (p=4, p=7, p=13, p=25), A000027 (p=6, p=11, p=21), A004116 (p=8, p=15, p=29), A035106 (p=10, p=19), A024206 (p=14, p=27), A007494 (p=18), A014616 (p=22), A179207 (p=26). - _Johannes W. Meijer_, Jun 05 2011

%K easy,nonn

%O 0,5

%A _Paul Barry_, Oct 07 2005