login
Number of integers <= 10^n that are the sum of 2 distinct nonzero squares.
0

%I #14 Jun 20 2022 04:41:40

%S 2,29,293,2649,23760,215594,1983334,18451711,173211045,1637570777,

%T 15570353488

%N Number of integers <= 10^n that are the sum of 2 distinct nonzero squares.

%C Integers of the form m^2 + n^2 with m > n > 0 are given by A004431.

%e a(2) = 29 because there are 29 terms in A004431 which are less than or equal to 100: {5, 10, 13, 17, 20, 25, 26, 29, 34, 37, 40, 41, 45, 50, 52, 53, 58, 61, 65, 68, 73, 74, 80, 82, 85, 89, 90, 97, 100}

%t hyp = Union[ Flatten[ Table[ m^2 + n^2, {n, 2, 100000}, {m, n - 1}]]]; Table[ Length[ Select[ hyp, #<=10^n &]], {n, 8}]

%o (Python)

%o from math import isqrt

%o from itertools import combinations

%o def a(n):

%o ub = 10**n

%o sqs = [i**2 for i in range(1, isqrt(ub)+1)]

%o return len(set(sum(c) for c in combinations(sqs, 2) if sum(c) <= ub))

%o print([a(n) for n in range(1, 8)]) # _Michael S. Branicky_, Jun 19 2022

%Y Cf. A004431.

%K nonn,more

%O 1,1

%A _Robert G. Wilson v_, Nov 09 2004

%E Definition edited and a(7)-a(9) from _Andrew Howroyd_, Apr 14 2021

%E a(10)-a(11) from _Michael S. Branicky_, Jun 19 2022