A336815 - OEIS

%I #71 Dec 10 2020 08:52:29

%S 1,2,3,4,6,7,10,12,17,26,37,69,120,233,417,781,1386,2561,4638,8387,

%T 15495,27709,51580,94054,176266,330004,618846,1174439,2216002,4232301,

%U 8041866,15344759,29258898,55850376,106792759,204203789,391147474,749434144,1439261966

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

%F a(n) = 1 + Sum_{k=1..n} A339612(k).

%e 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 (Python)

%o from sympy.ntheory.primetest import is_square

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def b(n, sos, c):

%o   if n == 0:

%o     if is_square(sos): return 1

%o     return 0

%o   return b(n-1, sos, c) + b(n-1, sos+n*n, c+1)

%o a = lambda n: b(n, 0, 0)

%o print([a(n) for n in range(40)]) # _Michael S. Branicky_, Dec 10 2020

%Y Cf. A000290, A126024, A339612.

%K nonn

%O 0,2

%A _Ilya Gutkovskiy_, Dec 09 2020

%E a(24)-a(38) from _Michael S. Branicky_, Dec 09 2020