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

%I #11 Feb 23 2023 04:20:32

%S 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,

%T 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,

%U 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

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

%C 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.

%H Reinhard Zumkeller, <a href="/A117546/b117546.txt">Table of n, a(n) for n = 0..10000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TribonacciNumber.html">Tribonacci Number</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ZeckendorfRepresentation.html">Zeckendorf Representation</a>.

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

%t 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

%o (Haskell)

%o a117546 = p $ drop 3 a000073_list where

%o p _ 0 = 1

%o p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m

%o -- _Reinhard Zumkeller_, Apr 13 2014

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

%Y Cf. A240844.

%K easy,nonn

%O 0,8

%A _T. D. Noe_ and _Jonathan Vos Post_, Mar 28 2006

%E a(0)=1 added and offset changed by _Reinhard Zumkeller_, Apr 13 2014