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

Links

Table of n, a(n) for n=1..98.

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

Example

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

Mathematica

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

Prog

(Python 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

Crossrefs

Cf. A075109, A112344.

Sequence in context: A216512 A078359 A107329 * A230279 A085859 A218218

Adjacent sequences: A263714 A263715 A263716 * A263718 A263719 A263720

Keyword

nonn

Author

Martin Y. Champel, Oct 24 2015

Status

approved