OFFSET
1,2
COMMENTS
a(n) is the smallest number k such that n*k can be expressed as the sum of k squares.
LINKS
Peter Munn, Table of n, a(n) for n = 1..10000
FORMULA
a(n) <= 4. (Lagrange)
EXAMPLE
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.
PROG
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Yifan Xie, Apr 07 2023
STATUS
approved