OFFSET
2,1
LINKS
Michael S. Branicky, Table of n, a(n) for n = 2..83
Eric Weisstein's World of Mathematics, Polygonal Number
EXAMPLE
a(3) = 4 subsets: {1}, {3}, {6}, {1, 3, 6}.
a(4) = 5 subsets: {1}, {4}, {9}, {16}, {9, 16}.
a(5) = 7 subsets: {1}, {5}, {12}, {22}, {35}, {1, 12, 22}, {1, 12, 22, 35}.
PROG
(Python)
from functools import cache
from itertools import count, takewhile
def ngonal(n, k): return k*((n-2)*k - (n-4))//2
def a(n):
@cache
def b(i, s):
if i == 0: return 1 if s > 0 and s in ISNGONAL else 0
return b(i-1, s) + b(i-1, s+NGONAL[i-1])
NGONAL = [ngonal(n, i) for i in range(1, n+1)]
BOUND = sum(NGONAL)
ISNGONAL = set(takewhile(lambda x: x<=BOUND, (ngonal(n, i) for i in count(1))))
b.cache_clear()
return b(n, 0)
print([a(n) for n in range(2, 23)]) # Michael S. Branicky, Dec 21 2024
CROSSREFS
KEYWORD
nonn,new
AUTHOR
Ilya Gutkovskiy, Dec 21 2024
EXTENSIONS
a(2) inserted and a(23) and beyond from Michael S. Branicky, Dec 21 2024
STATUS
approved