A379337 Number of subsets of the first n nonzero n-gonal numbers whose sum is a nonzero n-gonal number.

3, 4, 5, 7, 7, 10, 11, 18, 20, 23, 31, 63, 77, 127, 212, 332, 569, 1034, 1749, 2961, 5236, 9319, 16524, 28583, 53618, 96310, 174573, 309344, 584500, 1077230, 1984982, 3532258, 6791403, 12564409, 23445306, 42349391, 81321728, 152375491, 284898585, 524549566, 1006478176, 1894215667

Offset: 2

Author

Ilya Gutkovskiy, Dec 21 2024

Keywords

• nonn

Examples

			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}.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 2..83
• Eric Weisstein's World of Mathematics, Polygonal Number

Crossrefs

Cf. A057145, A377123.

Programs

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

Extensions

a(2) inserted and a(23) and beyond from Michael S. Branicky, Dec 21 2024