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

Cf. A057145, A377123.

Sequence in context: A247140 A269304 A071054 * A231346 A033545 A253570

Adjacent sequences: A379334 A379335 A379336 * A379338 A379339 A379340

Keyword

nonn

Author

Ilya Gutkovskiy, Dec 21 2024

Extensions

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

Status

approved