login
A339454
Number of subsets of {1..n} whose root mean square is an integer.
7
1, 2, 3, 4, 5, 6, 9, 10, 15, 20, 29, 52, 87, 166, 311, 538, 943, 1682, 2915, 5054, 8905, 15904, 28533, 51826, 95191, 175402, 325777, 607542, 1134191, 2128922, 3986433, 7485522, 14065135, 26446388, 49796025, 93920770, 177470237, 335780796, 636883269, 1209603646
OFFSET
1,2
LINKS
Eric W. Weisstein's World of Mathematics, Root-Mean-Square
EXAMPLE
a(9) = 15 subsets: {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {1, 7}, {1, 5, 7}, {1, 3, 5, 8, 9}, {3, 4, 5, 7, 9}, {1, 3, 5, 6, 8, 9} and {3, 4, 5, 6, 7, 9}.
PROG
(Python)
from functools import lru_cache
from sympy.ntheory.primetest import is_square
def cond(sos, c): return c > 0 and sos%c == 0 and is_square(sos//c)
@lru_cache(maxsize=None)
def b(n, sos, c):
if n == 0: return int(cond(sos, c))
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(1, 41)]) # Michael S. Branicky, Oct 06 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, Dec 05 2020
EXTENSIONS
a(23)-a(40) from Alois P. Heinz, Dec 05 2020
STATUS
approved