A117221 Number of partitions of 3-smooth numbers.

1, 2, 3, 5, 11, 22, 30, 77, 231, 385, 1575, 3010, 8349, 17977, 147273, 386155, 1741630, 5392783, 18004327, 118114304, 483502844, 4351078600, 22540654445, 129913904637, 1987276856363, 15285151248481, 133978259344888, 365749566870782, 3925922161489422, 49005643635237875

Offset: 1

Author

Reinhard Zumkeller, Mar 04 2006

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..100

Crossrefs

Cf. A000041, A003586, A090184, A117220, A117222.

Programs

Mathematica

PartitionsP /@ Select[Range[1000], AllTrue[FactorInteger[#][[All, 1]], # <= 3 &] &] (* Jean-François Alcover, Oct 13 2021 *)

PARI

\\ here is(n) is test for A003586 inclusion.
is(n)={forprime(p=2, 3, n/=p^valuation(n,p)); n==1}
seq(n)={my(A=List(), i=0); while(#AAndrew Howroyd, Jan 02 2020

Python

from sympy import integer_log, npartitions
def A117221(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum((x//3**i).bit_length() for i in range(integer_log(x,3)[0]+1))
    return npartitions(bisection(f,n,n)) # Chai Wah Wu, Sep 16 2024

Formula

a(n) = A000041(A003586(n)).

Extensions

More terms from Michel Marcus, Apr 20 2019