A379337 - OEIS

%I #14 Dec 23 2024 02:16:10

%S 3,4,5,7,7,10,11,18,20,23,31,63,77,127,212,332,569,1034,1749,2961,

%T 5236,9319,16524,28583,53618,96310,174573,309344,584500,1077230,

%U 1984982,3532258,6791403,12564409,23445306,42349391,81321728,152375491,284898585,524549566,1006478176,1894215667

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

%H Michael S. Branicky, <a href="/A379337/b379337.txt">Table of n, a(n) for n = 2..83</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PolygonalNumber.html">Polygonal Number</a>

%e a(3) = 4 subsets: {1}, {3}, {6}, {1, 3, 6}.

%e a(4) = 5 subsets: {1}, {4}, {9}, {16}, {9, 16}.

%e a(5) = 7 subsets: {1}, {5}, {12}, {22}, {35}, {1, 12, 22}, {1, 12, 22, 35}.

%o (Python)

%o from functools import cache

%o from itertools import count, takewhile

%o def ngonal(n, k): return k*((n-2)*k - (n-4))//2

%o def a(n):

%o     @cache

%o     def b(i, s):

%o         if i == 0: return 1 if s > 0 and s in ISNGONAL else 0

%o         return b(i-1, s) + b(i-1, s+NGONAL[i-1])

%o     NGONAL = [ngonal(n, i) for i in range(1, n+1)]

%o     BOUND = sum(NGONAL)

%o     ISNGONAL = set(takewhile(lambda x: x<=BOUND, (ngonal(n, i) for i in count(1))))

%o     b.cache_clear()

%o     return b(n, 0)

%o print([a(n) for n in range(2, 23)]) # _Michael S. Branicky_, Dec 21 2024

%Y Cf. A057145, A377123.

%K nonn,new

%O 2,1

%A _Ilya Gutkovskiy_, Dec 21 2024

%E a(2) inserted and a(23) and beyond from _Michael S. Branicky_, Dec 21 2024