login
A373666
Smallest positive integer whose square can be written as the sum of n positive perfect squares whose square roots differ by no more than 1.
2
1, 5, 3, 2, 5, 3, 4, 10, 3, 4, 7, 6, 4, 9, 6, 4, 25, 6, 5, 10, 6, 5, 16, 6, 5, 12, 6, 7, 11, 6, 7, 20, 6, 7, 15, 6, 7, 31, 9, 7, 13, 9, 7, 14, 9, 7, 36, 9, 7, 15, 9, 8, 22, 9, 8, 17, 9, 8, 16, 9, 8, 49, 9, 8, 20, 9, 10, 50, 9, 10, 17, 9, 10, 19, 9, 10, 28, 9
OFFSET
1,2
COMMENTS
Shortest possible integer length of the diagonal of an n-dimensional hyperrectangle where each edge has a positive integer length, and edge lengths differ by no more than 1.
LINKS
FORMULA
a(n) = min(d) such that d^2 - n*b^2 == 0 (mod 2*b + 1) and d >= ceiling(sqrt(n)) where b = floor(sqrt(d^2/n)).
EXAMPLE
a(1) = 1 because 1^2 = 1^2.
a(2) = 5 because 5^2 = 3^2 + 4^2.
a(3) = 3 because 3^2 = 1^2 + 2*(2^2).
a(4) = 2 because 2^2 = 4*(1^2).
a(5) = 5 because 5^2 = 4*(2^2) + 3^2.
a(6) = 3 because 3^2 = 5*(1^2) + 2^2.
a(7) = 4 because 4^2 = 4*(1^2) + 3*(2^2).
PROG
(PARI) a(n) = my(d=ceil(sqrt(n))); while(true, my(b=sqrtint(floor(d^2/n))); if ((d^2-b^2*n)%(b*2+1)==0, return(d), d++)) \\ Charles L. Hohn, Jul 02 2024
(PARI)
a366973(n) = {for(i=2, oo, my(p=prime(i)); for(j=0, (p-1)/2, if(n%p==j^2%p, return(p))))}
bstep(np, p) = {my(t=np+if(np%2, p)); while(!issquare(t), t+=p*2); sqrtint(t)/2}
a(n) = my(p=a366973(n), b=sqrtint(n*((p-1)/2)^2-1)+1, bp=b%p, s=bstep(n%p, p)); b-bp+if(bp<=s, s, bp<=p-s, p-s, p+s) \\ Charles L. Hohn, Sep 27 2024
CROSSREFS
Sequence in context: A165102 A294568 A290349 * A009661 A023576 A271523
KEYWORD
nonn
AUTHOR
Charles L. Hohn, Jun 12 2024
STATUS
approved