OFFSET
0,4
COMMENTS
[]=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}].
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).
Every positive integer eventually appears, as the value of the sequence at (4^n-1)/3 is n. - Jeffrey Shallit, May 02 2016
First occurrence of n in this sequence is given by A272530(n). - Jeffrey Shallit, Oct 13 2017
REFERENCES
G. Chrystal, Algebra, Vol. II, pp. 494 ff. (for definition of continuant).
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, Sect. 6.7 (for definition of continuant).
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).
LINKS
T. D. Noe, Table of n, a(n) for n=0..4095
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoret. Comput. Sci. 98 (1992), 163-197.
T. Muir, The Theory of Determinants in the Historical Order of Development, 4 vols., Macmillan, NY, 1906-1923, Vol. 2.
Wikipedia, Continuant
FORMULA
From Robert Israel, May 04 2016: (Start)
a(2n) = a(floor(n/2)).
a(4n+1) = a(2n+1).
a(4n+3) = a(2n+1) + a(n).
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)
Hence this sequence is 2-regular in the sense of Allouche and Shallit (1992). - Jeffrey Shallit, Oct 13 2017
EXAMPLE
From Alois P. Heinz, Aug 14 2013: (Start)
a(0) = [] = 1.
a(1) = [1] = 1.
a(2) = [1,0] = [0,1] = 1*0 + 1 = 1.
a(3) = [1,1] = 1*1 + 1 = 2.
a(4) = [1,0,0] = [0,0,1] = 1*0*0 + 1+0 = 1.
a(5) = [1,0,1] = 1*0*1 + 1+1 = 2.
a(6) = [1,1,0] = [0,1,1] = 1*1*0 + 1+0 = 1.
a(7) = [1,1,1] = 1*1*1 + 1+1 = 3.
(End)
MAPLE
c:= proc() option remember;
if nargs=0 then 1
elif nargs=1 then args[1]
else args[-1]*c(seq(args[i], i=1..nargs-1))
+c(seq(args[i], i=1..nargs-2))
fi
end:
a:= n-> `if`(n=0, 1, c(convert(n, base, 2)[])):
seq(a(n), n=0..120); # Alois P. Heinz, Aug 06 2013
# second Maple program:
a:= proc(n) option remember;
if n::even then procname(floor(n/4))
elif n mod 4 = 1 then procname((n+1)/2)
else procname((n-1)/2) + procname((n-3)/4)
fi
end proc:
a(0):= 1: a(1):= 1:
map(a, [$0..1000]); # Robert Israel, May 04 2016
MATHEMATICA
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 *)
PROG
(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;
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
N. J. A. Sloane, Jul 18 2002
EXTENSIONS
More terms from Klaus Brockhaus, Jul 19 2002
Maple program corrected by Robert Israel, May 04 2016
STATUS
approved