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,2

Links

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

Formula

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

Mathematica

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

Prog

(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(#A<n, i++; if(is(i), listput(A, numbpart(i)))); Vec(A)} \\ Andrew 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

Crossrefs

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

Sequence in context: A087581 A360320 A049888 * A073879 A073880 A376856

Adjacent sequences: A117218 A117219 A117220 * A117222 A117223 A117224

Keyword

nonn

Author

Reinhard Zumkeller, Mar 04 2006

Extensions

More terms from Michel Marcus, Apr 20 2019

Status

approved