A263717 Number of partitions of n into perfect odd powers (1 being excluded).

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 1, 1, 0, 2, 0, 3, 0, 0, 0, 1, 1, 0, 2, 0, 3, 0, 0, 0, 1, 1, 0, 2, 0, 3, 0, 1, 1, 2, 2, 0, 3, 0, 5, 0, 1, 1, 2, 2, 0, 3, 0, 5, 0, 1, 1, 2, 2, 0, 3, 1, 6

Offset: 1

Author

Martin Y. Champel, Oct 24 2015

Keywords

• nonn

Examples

			a(97) = #{8*9+25, 5*9+25+27, 2*9+25+2*27} = 3.
		

Links

• Martin Y. Champel, Table of n, a(n) for n = 1...999

Crossrefs

Cf. A075109, A112344.

Programs

Mathematica

Needs["Combinatorica`"]; Length@ Select[Combinatorica`Partitions@ #, AllTrue[#, And[PrimePowerQ@ #, ! PrimeQ@ #, OddQ@ #] &, 1] &] & /@ Range[2, 52] (* Michael De Vlieger, Nov 05 2015, Version 10 *)

Python

# Python version 2.7
def a(n):
    base = sorted(list(set([a**b for b in range(2,int(log(n)/log(2))) for a in range(3,1+int(n**(1./b)),2)])))
    lb = len(base)
    if lb == 0:
        return 0
    sol = 0
    s = [n // base[0]]
    if lb == 1:
        if n % base[0]  == 0: return 1
        return 0
    while True:
        k = s.pop()
        while k < 0:
            if s ==(lb-1)*[0]:
                return sol
            k = s.pop() - 1
        s.append(k)
        x = n - sum([s[i]*base[i] for i in range(len(s))])
        ls = len(s)
        if ls == lb:
            continue
        a = x // base[ls]
        b = x % base[ls]
        if b == 0:
            s.append(a)
            sol +=1
            if len(s) == lb:
                s.pop()
                s.append(-1)
            r = s.pop() - 2
            s.append(r)
        else:
            s.append(a-1)
            if a!=0:
                if len(s) == lb: s[lb-1]=-1