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

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, 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, 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

Offset: 1

Author

Yifan Xie, Apr 07 2023

Keywords

• nonn
• easy

Comments

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

Examples

			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.
		

Links

• Peter Munn, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A360530 (nonzero), A004215.

Programs

PARI

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)))));
a(n) = {for(t = 1, 3, if(findsquare(t, n*t), return(t))); return(4)};

Python

from sympy.ntheory.primetest import is_square
from sympy import factorint
def A362068(n):
    if is_square(n):
        return 1
    if all(map(lambda x:x[0]&3<3 or x[1]&1^1, factorint(k:=n>>(m:=(~n&n-1).bit_length())).items())):
        return 2
    if m&1 or 3*k&7<7:
        return 3
    return 4 # Chai Wah Wu, Apr 27 2023

Formula

a(n) <= 4. (Lagrange)