OFFSET
1,2
COMMENTS
A000330(n-1) <= a(n).
LINKS
Project Euler, Subsets with a Unique Sum
EXAMPLE
a(3) = 14 because: k = 1 and
14 = 4+9 and
4 = 4+0
9 = 9+0
and 9 <= n^2.
a(4) = 90 because: k = 2 and
90 = 5+10+13+17+20+25 and
5 = 1+4
10 = 1+9
13 = 4+9
17 = 1+16
20 = 4+16
25 = 9+16 and 16 <= n^2.
PROG
(Python)
from collections import defaultdict
def a(n):
k = n >> 1
dp = [defaultdict(int) for _ in range(k + 1)]
dp[0][0] = 1
for s in [i**2 for i in range(1, n + 1)]:
for j in range(k, 0, -1):
for m in list(dp[j - 1].keys()):
dp[j][m + s] += dp[j - 1][m]
return sum(t for t, v in dp[k].items() if v == 1)
print([a(n) for n in range(1, 37)])
(Python)
from itertools import combinations
from collections import Counter
def A374510(n): return sum(d for d, e in Counter(sum(s) for s in combinations((m**2 for m in range(1, n+1)), n>>1)).items() if e == 1) # Chai Wah Wu, Jul 17 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Darío Clavijo, Jul 09 2024
STATUS
approved