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.

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

Author

Charles L. Hohn, Jun 12 2024

Keywords

• nonn

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.

Examples

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

Links

• Charles L. Hohn, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A351061, A366973.

Programs

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

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