We start by factoring 1000:2^3*5^3, which is 125*8. We note that each factor occurs to an odd power which avoids a difficulty that might otherwise arise. We know we can get 8 ways by using any 4 separate Pythagorean primes; see 12 ways at the link above. Now we need to get 125 ways. We can get 5 ways by using 5^4*13=8125 see A016032 in Sloane, which also tells us that to get 25 ways we need 5^4×13^4×17= 303460625. It seems logical to expect that 125 ways will require 5^4×13^4×17^4×29= 43236159468125 and this is easily confirmed e.g. in Mathematica. Now we just need the next 3 Pythagorean primes to obtain the multiple of 8: 5^4*13^4*17^4*29*37*41*53= 3,476,230,457,396,718,125; and a^2+b^2=3476230457396718125, 0 less than a less than b in Mathematica confirms that this has exactly 1000 solutions. There can’t be any smaller solution since we constructed this number in the ‘cheapest’ way possible.
NOTE: This is a 'lazy man's way' as the number 1000 has nice properties. For other numbers, try this algorithm:
*Write each of 2n and 2n-1 as products of their divisors, in decreasing order and in all possible ways. Equate each divisor in the product to (a1+1)(a2+1)...(ar+1), so that a1>=a2>=a3>=...>=ar, and solve for the ai. Evaluate A002144(1)^a1 x A002144(2)^a2 x ... x A002144(r)^ar (i.e the Pythagorean primes)for each set of values determined above, then the smaller of these products is the least integer to have precisely n partitions into a sum of two squares.(Ant King) * |