cp's OEIS Frontend

A117535 Number of ways of writing n as a sum of powers of 3, each power being used at most 4 times.

%I A117535 #42 May 13 2021 10:39:07
%S A117535 1,1,1,2,2,1,2,2,1,3,3,2,4,4,2,3,3,1,3,3,2,4,4,2,3,3,1,4,4,3,6,6,3,5,
%T A117535 5,2,6,6,4,8,8,4,6,6,2,5,5,3,6,6,3,4,4,1,4,4,3,6,6,3,5,5,2,6,6,4,8,8,
%U A117535 4,6,6,2,5,5,3,6,6,3,4,4,1,5,5,4,8,8,4,7,7,3,9,9,6,12,12,6,9,9,3,8,8,5,10,10
%N A117535 Number of ways of writing n as a sum of powers of 3, each power being used at most 4 times.
%C A117535 It seems that this sequence can be calculated by constructing an insertion tree in which the insertion rules depend on the "age" of a term at a particular stage of the calculation. See the link for a discussion of this concept.
%H A117535 Alois P. Heinz, <a href="/A117535/b117535.txt">Table of n, a(n) for n = 0..10000</a>
%H A117535 P. de Castro et al., <a href="https://community.plu.edu/~edgartj/binomialcoeffs.pdf">Counting binomial coefficients divisible by a prime power</a>, Amer. Math. Monthly, 125 (2018), 531-540. See page 535.
%H A117535 John W. Layman, <a href="http://www.math.vt.edu/people/layman/sequences/ins_seq.htm">Ratio-Determined Insertion Sequences and the Tree of their Recurrence Types</a>, June 2003 [Broken link]
%H A117535 John W. Layman, <a href="/A085376/a085376.txt">Ratio-Determined Insertion Sequences and the Tree of their Recurrence Types</a>, June 2003 [local copy, corrected]
%H A117535 John W. Layman, <a href="https://intranet.math.vt.edu/people/layman/sequences/agedetit.htm">Sequences Generated by Age-Determined Insertion Trees</a>, Jan 2006
%H A117535 John W. Layman, <a href="/A117535/a117535.txt">Sequences Generated by Age-Determined Insertion Trees</a>, Jan 2006 [Local copy]
%F A117535 G.f.: product((1+x^(3^j)+x^(2*(3^j))+x^(3*(3^j))+x^(4*(3^j))), j=0..infinity). - _Emeric Deutsch_, Apr 02 2006
%F A117535 For n>=1, a(3*n+2) = a(n); a(3*n+1) = a(n) + a(n-1); a(3*n) = a(n) + a(n-1). - _Tom Edgar_, Jun 21 2017
%F A117535 G.f. A(x) satisfies: A(x) = (1 + x + x^2 + x^3 + x^4) * A(x^3). - _Ilya Gutkovskiy_, Jul 09 2019
%e A117535 a(12) = 4 because 12=9+3=9+1+1+1=3+3+3+3=3+3+3+1+1+1.
%p A117535 g:= product((1+x^(3^j)+x^(2*(3^j))+x^(3*(3^j))+x^(4*(3^j))), j=0..10): gser:= series(g,x=0,106): seq(coeff(gser,x,n), n=0..103); # _Emeric Deutsch_, Apr 02 2006
%p A117535 # second Maple program:
%p A117535 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<0, 0,
%p A117535       add(`if`(n-j*3^i<0, 0, b(n-j*3^i, i-1)), j=0..4)))
%p A117535     end:
%p A117535 a:= n-> b(n, ilog[3](n)):
%p A117535 seq(a(n), n=0..100);  # _Alois P. Heinz_, Jun 21 2012
%t A117535 b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 0, 0, Sum[If[n - j*3^i < 0, 0, b[n - j*3^i, i - 1]], {j, 0, 4}]]]; a[n_] := b[n, Floor[Log[3, n]]]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Dec 22 2016, after _Alois P. Heinz_ *)
%Y A117535 Cf. A054390.
%K A117535 nonn,look
%O A117535 0,4
%A A117535 _John W. Layman_, Mar 27 2006