A117546 Number of representations of n as a sum of distinct tribonacci numbers (A000073).

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 3, 2, 2, 2, 2, 2, 2, 3, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 3, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 3, 3, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2

Offset: 0

Author

T. D. Noe and Jonathan Vos Post, Mar 28 2006

Keywords

• easy
• nonn

Comments

It can be shown that, like the Fibonacci numbers, the tribonacci numbers are complete; that is, a(n)>0 for all n. There is always a representation, free of three consecutive tribonacci numbers, which is analogous to the Zeckendorf representation of Fibonacci numbers. See A003726.

Examples

			a(14)=2 because 14 is both 13+1 and 7+4+2+1.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• Eric Weisstein's World of Mathematics, Tribonacci Number.
• Eric Weisstein's World of Mathematics, Zeckendorf Representation.

Crossrefs

Cf. A000119 (number of representations of n as a sum of distinct Fibonacci numbers).

Cf. A240844.

Programs

Haskell

a117546 = p $ drop 3 a000073_list where
   p _  0     = 1
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Apr 13 2014

Mathematica

tr={1,2,4,7,13,24,44,81,149}; len=tr[[ -1]]; cnt=Table[0,{len}]; Do[v=IntegerDigits[k,2,Length[tr]]; s=Dot[tr,v]; If[s<=len, cnt[[s]]++ ], {k,2^(Length[tr])-1}]; cnt

Extensions

a(0)=1 added and offset changed by Reinhard Zumkeller, Apr 13 2014