login
a(n) is the smallest positive integer k such that n can be expressed as the arithmetic mean of k squares.
2

%I #59 Aug 10 2023 09:02:38

%S 1,2,3,1,2,3,3,2,1,2,3,3,2,3,3,1,2,2,3,2,4,3,3,3,1,2,3,3,2,3,3,2,3,2,

%T 3,1,2,3,3,2,2,3,3,3,2,3,3,3,1,2,3,2,2,3,3,3,3,2,3,3,2,3,3,1,2,3,3,2,

%U 4,3,3,2,2,2,3,3,4,3,3,2,1,2,3,4,2,3,3,3,2,2,3,3,4,3,3,3,2,2,3,1

%N a(n) is the smallest positive integer k such that n can be expressed as the arithmetic mean of k squares.

%C a(n) is the smallest number k such that n*k can be expressed as the sum of k squares.

%H Peter Munn, <a href="/A362068/b362068.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) <= 4. (Lagrange)

%e For n = 2, if k = 1, 2*1 = 2 is not a square; if k = 2, 2*2 = 4 = 2^2 + 0^2, so a(2) = 2.

%o (PARI)

%o findsquare(k, m) = if(k == 1, issquare(m), for(j=0, m, if(j*j > m, return(0), if(findsquare(k-1, m-j*j), return(1)))));

%o a(n) = {for(t = 1, 3, if(findsquare(t, n*t), return(t))); return(4)};

%o (Python)

%o from sympy.ntheory.primetest import is_square

%o from sympy import factorint

%o def A362068(n):

%o if is_square(n):

%o return 1

%o if all(map(lambda x:x[0]&3<3 or x[1]&1^1, factorint(k:=n>>(m:=(~n&n-1).bit_length())).items())):

%o return 2

%o if m&1 or 3*k&7<7:

%o return 3

%o return 4 # _Chai Wah Wu_, Apr 27 2023

%Y Cf. A360530 (nonzero), A004215.

%K nonn,easy

%O 1,2

%A _Yifan Xie_, Apr 07 2023