login
a(0) = 1, a(2n+1) = a(n), a(2n) = a(n) + a(n-1) + ... + a(n-m) + ... where a(n<0) = 0.
4

%I #17 Aug 31 2021 02:37:13

%S 1,1,2,1,4,2,5,1,9,4,11,2,16,5,17,1,26,9,30,4,41,11,43,2,59,16,64,5,

%T 81,17,82,1,108,26,117,9,147,30,151,4,192,41,203,11,246,43,248,2,307,

%U 59,323,16,387,64,392,5,473,81,490,17,572,82,573,1,681,108,707

%N a(0) = 1, a(2n+1) = a(n), a(2n) = a(n) + a(n-1) + ... + a(n-m) + ... where a(n<0) = 0.

%C Sequence has itself and its partial sums as bisections.

%C Setting m=1 gives Stern-Brocot sequence (A002487).

%C Conjecture: a(n) mod 2 repeats the 7-pattern 1,1,0,1,0,0,1 (A011657).

%C The conjecture is easily proved by induction: a(0) to a(14) = 1, 1, 2, 1, 4, 2, 5, 1, 9, 4, 11, 2, 16, 5 read mod 2 gives 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1. Assume the conjecture is true up to n = 14k. Then the next 7 odd entries a(14k+1), a(14k+3), ..., a(14k+13) are read from a(7k) to a(7k+6), which follow the correct mod 2 pattern by assumption. For the even entries a(14k), a(14k+10)... a(14k+12), the sum over the first 7k-1 addends is even, simply because of each consecutive 7 addends exactly 4 are odd. So again a(7k) to a(7k+6) determines the outcome and again gives the desired pattern. a(14k) is odd, since a(7k) is odd, a(14k+2) is even, since a(7k) and a(7k+1) are odd and so on ... - Lambert Herrgesell (zero815(AT)googlemail.com), May 08 2007

%H Alois P. Heinz, <a href="/A086450/b086450.txt">Table of n, a(n) for n = 0..10000</a>

%p a:= proc(n) local m; a(n):= `if`(n=0, 1,

%p `if`(irem(n, 2, 'm')=1, a(m), s(m)))

%p end:

%p s:= proc(n) s(n):= a(n) +`if`(n=0, 0, s(n-1)) end:

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Sep 26 2013

%t a[0] = 1; a[n_] := a[n] = If[EvenQ[n], Sum[a[n/2-k], {k, 0, n/2}], a[(n-1)/2]]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Jun 16 2015 *)

%o (PARI) a(n)=if(n<2,n>=0,if(n%2==0,sum(k=0,n/2,a(n/2-k)),a((n-1)/2)))

%Y Cf. A086449.

%Y Partial sums are in A085765.

%K nonn,easy

%O 0,3

%A _Ralf Stephan_, Jul 20 2003