cp's OEIS Frontend

A336815 Number of subsets of {1..n} whose sum of squares of elements is a square.

%I A336815 #71 Dec 10 2020 08:52:29
%S A336815 1,2,3,4,6,7,10,12,17,26,37,69,120,233,417,781,1386,2561,4638,8387,
%T A336815 15495,27709,51580,94054,176266,330004,618846,1174439,2216002,4232301,
%U A336815 8041866,15344759,29258898,55850376,106792759,204203789,391147474,749434144,1439261966
%N A336815 Number of subsets of {1..n} whose sum of squares of elements is a square.
%F A336815 a(n) = 1 + Sum_{k=1..n} A339612(k).
%e A336815 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}.
%o A336815 (Python)
%o A336815 from sympy.ntheory.primetest import is_square
%o A336815 from functools import lru_cache
%o A336815 @lru_cache(maxsize=None)
%o A336815 def b(n, sos, c):
%o A336815   if n == 0:
%o A336815     if is_square(sos): return 1
%o A336815     return 0
%o A336815   return b(n-1, sos, c) + b(n-1, sos+n*n, c+1)
%o A336815 a = lambda n: b(n, 0, 0)
%o A336815 print([a(n) for n in range(40)]) # _Michael S. Branicky_, Dec 10 2020
%Y A336815 Cf. A000290, A126024, A339612.
%K A336815 nonn
%O A336815 0,2
%A A336815 _Ilya Gutkovskiy_, Dec 09 2020
%E A336815 a(24)-a(38) from _Michael S. Branicky_, Dec 09 2020