cp's OEIS Frontend

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.

%I A373666 #44 Sep 27 2024 22:59:23
%S A373666 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 A373666 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 A373666 8,49,9,8,20,9,10,50,9,10,17,9,10,19,9,10,28,9
%N 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.
%C A373666 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 A373666 Charles L. Hohn, <a href="/A373666/b373666.txt">Table of n, a(n) for n = 1..10000</a>
%F A373666 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 A373666 a(1) = 1 because 1^2 = 1^2.
%e A373666 a(2) = 5 because 5^2 = 3^2 + 4^2.
%e A373666 a(3) = 3 because 3^2 = 1^2 + 2*(2^2).
%e A373666 a(4) = 2 because 2^2 = 4*(1^2).
%e A373666 a(5) = 5 because 5^2 = 4*(2^2) + 3^2.
%e A373666 a(6) = 3 because 3^2 = 5*(1^2) + 2^2.
%e A373666 a(7) = 4 because 4^2 = 4*(1^2) + 3*(2^2).
%o A373666 (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 A373666 (PARI)
%o A373666 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 A373666 bstep(np, p) = {my(t=np+if(np%2, p)); while(!issquare(t), t+=p*2); sqrtint(t)/2}
%o A373666 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 A373666 Cf. A351061, A366973.
%K A373666 nonn
%O A373666 1,2
%A A373666 _Charles L. Hohn_, Jun 12 2024