login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #44 Sep 27 2024 22:59:23

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

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

%U 8,49,9,8,20,9,10,50,9,10,17,9,10,19,9,10,28,9

%N 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.

%C 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.

%H Charles L. Hohn, <a href="/A373666/b373666.txt">Table of n, a(n) for n = 1..10000</a>

%F 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)).

%e a(1) = 1 because 1^2 = 1^2.

%e a(2) = 5 because 5^2 = 3^2 + 4^2.

%e a(3) = 3 because 3^2 = 1^2 + 2*(2^2).

%e a(4) = 2 because 2^2 = 4*(1^2).

%e a(5) = 5 because 5^2 = 4*(2^2) + 3^2.

%e a(6) = 3 because 3^2 = 5*(1^2) + 2^2.

%e a(7) = 4 because 4^2 = 4*(1^2) + 3*(2^2).

%o (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

%o (PARI)

%o a366973(n) = {for(i=2, oo, my(p=prime(i)); for(j=0, (p-1)/2, if(n%p==j^2%p, return(p))))}

%o bstep(np, p) = {my(t=np+if(np%2, p)); while(!issquare(t), t+=p*2); sqrtint(t)/2}

%o 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

%Y Cf. A351061, A366973.

%K nonn

%O 1,2

%A _Charles L. Hohn_, Jun 12 2024