All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
1000 ways (Posted on 2011-09-23) Difficulty: 3 of 5

Following on from 12 Ways: find the smallest number that can be represented as the sum of two distinct squares of positive integers in exactly 1000 different ways.

  Submitted by broll    
No Rating
Solution: (Hide)
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)

Comments: ( You must be logged in to post comments.)
  Subject Author Date
re(3): Making inside etc - will comment later.broll2011-10-19 12:18:55
re(3): Making inside etc - will comment later.broll2011-09-30 03:58:27
Some Thoughtsre(2): Making inside etc - will comment later.Ady TZIDON2011-09-24 08:24:04
re: Making inside info public: Hint (credit to Jer)Jer2011-09-23 23:35:17
Hints/TipsMaking inside info public: Hint (credit to Jer)Charlie2011-09-23 22:16:00
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information