cp's OEIS Frontend

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

%I A379337 #14 Dec 23 2024 02:16:10
%S A379337 3,4,5,7,7,10,11,18,20,23,31,63,77,127,212,332,569,1034,1749,2961,
%T A379337 5236,9319,16524,28583,53618,96310,174573,309344,584500,1077230,
%U A379337 1984982,3532258,6791403,12564409,23445306,42349391,81321728,152375491,284898585,524549566,1006478176,1894215667
%N A379337 Number of subsets of the first n nonzero n-gonal numbers whose sum is a nonzero n-gonal number.
%H A379337 Michael S. Branicky, <a href="/A379337/b379337.txt">Table of n, a(n) for n = 2..83</a>
%H A379337 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PolygonalNumber.html">Polygonal Number</a>
%e A379337 a(3) = 4 subsets: {1}, {3}, {6}, {1, 3, 6}.
%e A379337 a(4) = 5 subsets: {1}, {4}, {9}, {16}, {9, 16}.
%e A379337 a(5) = 7 subsets: {1}, {5}, {12}, {22}, {35}, {1, 12, 22}, {1, 12, 22, 35}.
%o A379337 (Python)
%o A379337 from functools import cache
%o A379337 from itertools import count, takewhile
%o A379337 def ngonal(n, k): return k*((n-2)*k - (n-4))//2
%o A379337 def a(n):
%o A379337     @cache
%o A379337     def b(i, s):
%o A379337         if i == 0: return 1 if s > 0 and s in ISNGONAL else 0
%o A379337         return b(i-1, s) + b(i-1, s+NGONAL[i-1])
%o A379337     NGONAL = [ngonal(n, i) for i in range(1, n+1)]
%o A379337     BOUND = sum(NGONAL)
%o A379337     ISNGONAL = set(takewhile(lambda x: x<=BOUND, (ngonal(n, i) for i in count(1))))
%o A379337     b.cache_clear()
%o A379337     return b(n, 0)
%o A379337 print([a(n) for n in range(2, 23)]) # _Michael S. Branicky_, Dec 21 2024
%Y A379337 Cf. A057145, A377123.
%K A379337 nonn
%O A379337 2,1
%A A379337 _Ilya Gutkovskiy_, Dec 21 2024
%E A379337 a(2) inserted and a(23) and beyond from _Michael S. Branicky_, Dec 21 2024