A072347 - OEIS

%I #45 Oct 13 2017 21:13:30

%S 1,1,1,2,1,2,1,3,1,2,1,3,2,3,2,5,1,2,1,3,2,3,2,5,1,3,1,4,3,5,3,8,1,2,

%T 1,3,2,3,2,5,1,3,1,4,3,5,3,8,2,3,2,5,3,4,3,7,2,5,2,7,5,8,5,13,1,2,1,3,

%U 2,3,2,5,1,3,1,4,3,5,3,8,2,3,2,5,3,4,3,7,2,5,2,7,5,8,5,13,1,3,1,4,3,5,3

%N If n = pqr...st in binary, a(n) = value of continuant [p,q,r,...,s,t].

%C []=1, [p]=p, [p,q]=pq+1, [p,q,r]=pqr+p+r; in general [x_1,...,x_n] = [x_1,...,x_{n-1}]*x_n + [x_1,...,x_{n-2}].

%C The successive record values in this sequence occur at n=0 and n=2^k-1 for k>1 and are equal to the Fibonacci numbers A000045 (cf. Chrystal, p. 503, Exercise 11).

%C Every positive integer eventually appears, as the value of the sequence at (4^n-1)/3 is n. - _Jeffrey Shallit_, May 02 2016

%C First occurrence of n in this sequence is given by A272530(n). - _Jeffrey Shallit_, Oct 13 2017

%D G. Chrystal, Algebra, Vol. II, pp. 494 ff. (for definition of continuant).

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, Sect. 6.7 (for definition of continuant).

%D T. Muir, The Theory of Determinants in the Historical Order of Development. 4 vols., Macmillan, NY, 1906-1923, Vol. 2, p. 413 (for definition of continuant).

%H T. D. Noe, <a href="/A072347/b072347.txt">Table of n, a(n) for n=0..4095</a>

%H J.-P. Allouche and J. Shallit, <a href="https://doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoret. Comput. Sci. 98 (1992), 163-197.

%H T. Muir, <a href="http://www.hti.umich.edu/cgi/t/text/text-idx?sid=b88432273f115fb346725f1a42422e19;c=umhistmath;idno=ACM9350.0002.001">The Theory of Determinants in the Historical Order of Development</a>, 4 vols., Macmillan, NY, 1906-1923, Vol. 2.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Continuant_(mathematics)">Continuant</a>

%F From _Robert Israel_, May 04 2016: (Start)

%F a(2n) = a(floor(n/2)).

%F a(4n+1) = a(2n+1).

%F a(4n+3) = a(2n+1) + a(n).

%F G.f. G(x) satisfies G(x) = (1+x^2+x^3)*G(x^4) + (1+x^2)*(G(x^2)-G(-x^2))/(2*x). (End)

%F Hence this sequence is 2-regular in the sense of Allouche and Shallit (1992). - _Jeffrey Shallit_, Oct 13 2017

%e From _Alois P. Heinz_, Aug 14 2013: (Start)

%e a(0) =      []                          = 1.

%e a(1) =     [1]                          = 1.

%e a(2) =   [1,0] = [0,1]    =   1*0 + 1   = 1.

%e a(3) =   [1,1]            =   1*1 + 1   = 2.

%e a(4) = [1,0,0] = [0,0,1]  = 1*0*0 + 1+0 = 1.

%e a(5) = [1,0,1]            = 1*0*1 + 1+1 = 2.

%e a(6) = [1,1,0] = [0,1,1]  = 1*1*0 + 1+0 = 1.

%e a(7) = [1,1,1]            = 1*1*1 + 1+1 = 3.

%e (End)

%p c:= proc() option remember;

%p       if nargs=0 then 1

%p     elif nargs=1 then args[1]

%p     else args[-1]*c(seq(args[i], i=1..nargs-1))

%p                  +c(seq(args[i], i=1..nargs-2))

%p       fi

%p     end:

%p a:= n-> `if`(n=0, 1, c(convert(n, base, 2)[])):

%p seq(a(n), n=0..120);  # _Alois P. Heinz_, Aug 06 2013

%p # second Maple program:

%p a:= proc(n) option remember;

%p   if n::even then procname(floor(n/4))

%p elif n mod 4 = 1 then procname((n+1)/2)

%p else procname((n-1)/2) + procname((n-3)/4)

%p fi

%p end proc:

%p a(0):= 1: a(1):= 1:

%p map(a, [$0..1000]); # _Robert Israel_, May 04 2016

%t c[args_List] := With[{nargs = Length[args]}, Which[nargs == 0, 1, nargs == 1, First[args], True, Last[args]*c[Most[args]] + c[args // Most // Most]]]; a[n_] := c[IntegerDigits[n, 2]]; a[0] = 1; Table[a[n], {n, 0, 102}] (* _Jean-François Alcover_, Feb 11 2014, after _Alois P. Heinz_ *)

%o (ARIBAS) function continuant(n: integer): integer; var len,v,v1,v2,j: integer; begin len := bit_length(n); if len < 2 then v := 1; else v1 := bit_test(n,len-1); v := 1 + bit_test(n,len-1)*bit_test(n,len-2); for j := len-3 to 0 by -1 do v2 := v1; v1 := v; v := v1*bit_test(n,j) + v2; end; end; return v; end; for n := 0 to 102 do write(continuant(n),","); end;

%Y Cf. A272530.

%K nonn,nice,easy

%O 0,4

%A _N. J. A. Sloane_, Jul 18 2002

%E More terms from _Klaus Brockhaus_, Jul 19 2002

%E Maple program corrected by _Robert Israel_, May 04 2016