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
Charles L. Hohn, Table of n, a(n) for n = 1..10000
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
KEYWORD
nonn
AUTHOR
Charles L. Hohn, Jun 12 2024
STATUS
approved