A336815
Number of subsets of {1..n} whose sum of squares of elements is a square.
Original entry on oeis.org
1, 2, 3, 4, 6, 7, 10, 12, 17, 26, 37, 69, 120, 233, 417, 781, 1386, 2561, 4638, 8387, 15495, 27709, 51580, 94054, 176266, 330004, 618846, 1174439, 2216002, 4232301, 8041866, 15344759, 29258898, 55850376, 106792759, 204203789, 391147474, 749434144, 1439261966
Offset: 0
a(8) = 17 subsets: {}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {3, 4}, {6, 8}, {1, 4, 8}, {2, 3, 6}, {2, 4, 5, 6}, {1, 2, 4, 6, 8}, {1, 3, 4, 5, 7} and {2, 4, 6, 7, 8}.
-
from sympy.ntheory.primetest import is_square
from functools import lru_cache
@lru_cache(maxsize=None)
def b(n, sos, c):
if n == 0:
if is_square(sos): return 1
return 0
return b(n-1, sos, c) + b(n-1, sos+n*n, c+1)
a = lambda n: b(n, 0, 0)
print([a(n) for n in range(40)]) # Michael S. Branicky, Dec 10 2020
A378961
Number of sets of nonzero triangular numbers whose largest element is the n-th triangular number and whose sum is a triangular number.
Original entry on oeis.org
1, 1, 2, 1, 3, 5, 5, 11, 19, 33, 55, 92, 192, 327, 579, 1142, 2052, 3776, 6936, 12964, 24308, 44432, 84763, 159299, 299093, 567295, 1075570, 2045580, 3883453, 7411014, 14164089, 27044407, 51759660, 99259961, 190371661, 365537357, 702901278, 1352868238, 2606296357
Offset: 1
a(5) = 3 subsets of triangular numbers whose largest element is A000217(5)=15 and whose sum is in A000217: {15}, {6, 15} and {3, 10, 15}.
-
istri:= proc(n) issqr(1+8*n) end proc:
tri:= n -> n*(n+1)/2:
F:= proc(n,s) option remember; local v;
if s = 0 then return 1 fi;
if s > n*(n+1)*(n+2)/6 then return 0 fi;
v:= tri(n);
if s >= v then procname(n-1,s-v) + procname(n-1,s)
else procname(n-1,s)
fi;
end proc:
f:= proc(n) local i,t,m;
t:= 0;
m:= n*(n+1)*(n+2)/6;
for i from 1 while tri(i) <= m do
t:= t + F(n,tri(i)) - F(n-1,tri(i))
od;
t
end proc:
map(f, [$1..50]); # Robert Israel, Jan 13 2025
A339615
Number of nonempty sets of distinct positive integers whose sum of cubes is a cube, the largest integer of a set is n.
Original entry on oeis.org
1, 1, 1, 1, 2, 1, 1, 3, 1, 6, 5, 9, 10, 25, 32, 51, 97, 144, 244, 463, 767, 1062, 2005, 4177, 5716, 12101, 21526, 35306, 64629, 114871, 205337, 372317, 718410, 1226320, 2361112, 4308192, 7301384, 14615750, 26382095, 47631200, 91388286, 171931627, 302867194, 578843590, 1112232587
Offset: 1
a(13) = 10 sets: {13}, {2, 3, 8, 13}, {4, 8, 11, 12, 13}, {1, 2, 6, 7, 11, 13}, {2, 5, 7, 8, 12, 13}, {3, 4, 8, 10, 11, 12, 13}, {1, 2, 3, 4, 5, 7, 11, 13}, {2, 3, 4, 6, 7, 8, 9, 13}, {1, 2, 5, 6, 7, 8, 9, 10, 12, 13} and {2, 3, 5, 7, 8, 9, 10, 11, 12, 13}.
-
from functools import lru_cache
def perf_cube(n): return round(n**(1/3))**3 ==n
@lru_cache(maxsize=None)
def b(n, soc, c):
if n == 0:
if perf_cube(soc): return 1
return 0
return b(n-1, soc, c) + b(n-1, soc+n*n*n, c+1)
a = lambda n: b(n-1, n*n*n, 1)
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Dec 10 2020
Showing 1-3 of 3 results.