# Which numbers less than 5 billion have the most representations as the sums of two squares?

1842675848 has four representations as the sum of two squares: 1842675848 = 3518^2 + 42782^2 = 5458^2 + 42578^2 = 11338^2 + 41402^2 = 19702^2 + 38138^2.

It got me to wonder which numbers in this range (say, less than 5 billion) have four or more representations as the sum of two squares? And which of these has the most?

Is there any systematic way to answer this question?

• @OscarLanzi we cannot be certain without checking, but Ramanujan's construction for this type of thing suggests exponent of prime $p$ proportional to $1/\log p,$ quite similar to the Superior Highly Composite Numbers. With an explicit upper bound, we need to allow considerable variation from that in the exponents. – Will Jagy Jul 7 '17 at 2:09
• @will if we continue the list of primes up to $73$, then yes we can get more solutions with a smaller number by exchanging the factor of $73$ for squaring the $5$ and $13$ factors. But if the limit is five billion we are stopped short of this break-even point. We are constrained from hitting the Ramanujan optimium exactly because the exponents have to be whole numbers. – Oscar Lanzi Jul 7 '17 at 2:21
• @OscarLanzi I put one in my answer, 72 expressions and the number about 3 billion 3159797225 = 5^2 13^2 17 29 37 41 – Will Jagy Jul 7 '17 at 2:23
• Larger number, but less than 5 billion so it's a fair cop. But, in your answer please explain how your original trial improves with your factor interchange ($53 \rightarrow 5×13$) while staying under 5 billion. – Oscar Lanzi Jul 7 '17 at 2:30
• @OscarLanzi, as long as at least one of the exponents is odd, the count requested should half the count of divisors, so $d(n).$ It goes off if $n$ is a perfect square. en.wikipedia.org/wiki/Divisor_function and then en.wikipedia.org/wiki/Superior_highly_composite_number – Will Jagy Jul 7 '17 at 2:43

Friday: I extended the table Gerry pointed out, up to $10^{15}$; athough I dropped the initial $2, 50$ as multiplying by $2$ does not change the number of representations ( I use $5$ and $65$). I give the number of representations (as sum of two squares, numbers that are to be squared taken as positive and then ordered), the factorization of the number, and its log base ten.

as text file: http://oeis.org/A007511/b007511.txt

               my  bound 1021090952484265  =   5 13 17 29 37 41 53 61 73 89  log base ten  15.0091

1 log ten  0.00000   5  =   5  log base ten  0.69897
2 log ten  0.30103   65  =   5 13  log base ten  1.81291
3 log ten  0.47712   325  =   5^2 13  log base ten  2.51188
4 log ten  0.60206   1105  =   5 13 17  log base ten  3.04336
6 log ten  0.77815   5525  =   5^2 13 17  log base ten  3.74233
8 log ten  0.90309   27625  =   5^3 13 17  log base ten  4.4413
9 log ten  0.95424   71825  =   5^2 13^2 17  log base ten  4.85628
10 log ten  1.00000   138125  =   5^4 13 17  log base ten  5.14027
12 log ten  1.07918   160225  =   5^2 13 17 29  log base ten  5.20473
16 log ten  1.20412   801125  =   5^3 13 17 29  log base ten  5.9037
18 log ten  1.25527   2082925  =   5^2 13^2 17 29  log base ten  6.31867
20 log ten  1.30103   4005625  =   5^4 13 17 29  log base ten  6.60267
24 log ten  1.38021   5928325  =   5^2 13 17 29 37  log base ten  6.77293
32 log ten  1.50515   29641625  =   5^3 13 17 29 37  log base ten  7.4719
36 log ten  1.5563    77068225  =   5^2 13^2 17 29 37  log base ten  7.88688
40 log ten  1.60206   148208125  =   5^4 13 17 29 37  log base ten  8.17087
48 log ten  1.68124   243061325  =   5^2 13 17 29 37 41  log base ten  8.38572
64 log ten  1.80618   1215306625  =   5^3 13 17 29 37 41  log base ten  9.08469
72 log ten  1.85733   3159797225  =   5^2 13^2 17 29 37 41  log base ten  9.49966
80 log ten  1.90309   6076533125  =   5^4 13 17 29 37 41  log base ten  9.78366
96 log ten  1.98227   12882250225  =   5^2 13 17 29 37 41 53  log base ten  10.11
108 log ten  2.03342   53716552825  =   5^2 13^2 17^2 29 37 41  log base ten  10.7301
128 log ten  2.10721   64411251125  =   5^3 13 17 29 37 41 53  log base ten  10.809
144 log ten  2.15836   167469252925  =   5^2 13^2 17 29 37 41 53  log base ten  11.2239
160 log ten  2.20412   322056255625  =   5^4 13 17 29 37 41 53  log base ten  11.5079
192 log ten  2.2833    785817263725  =   5^2 13 17 29 37 41 53 61  log base ten  11.8953
216 log ten  2.33445   2846977299725  =   5^2 13^2 17^2 29 37 41 53  log base ten  12.4544
256 log ten  2.40824   3929086318625  =   5^3 13 17 29 37 41 53 61  log base ten  12.5943
288 log ten  2.45939   10215624428425  =   5^2 13^2 17 29 37 41 53 61  log base ten  13.0093
320 log ten  2.50515   19645431593125  =   5^4 13 17 29 37 41 53 61  log base ten  13.2933
384 log ten  2.58433   51078122142125  =   5^3 13^2 17 29 37 41 53 61  log base ten  13.7082
432 log ten  2.63548   173665615283225  =   5^2 13^2 17^2 29 37 41 53 61  log base ten  14.2397
480 log ten  2.68124   255390610710625  =   5^4 13^2 17 29 37 41 53 61  log base ten  14.4072
512 log ten  2.70927   286823301259625  =   5^3 13 17 29 37 41 53 61 73  log base ten  14.4576
576 log ten  2.76042   745740583275025  =   5^2 13^2 17 29 37 41 53 61 73  log base ten  14.8726

my  bound 1021090952484265  =   5 13 17 29 37 41 53 61 73 89  log base ten  15.0091


The best you can do is $$N = 5^{a_5} 13^{a_{13}} 17^{a_{17}}... p_r^{a_{p_r}}$$ with $$a_5 \geq a_{13} \geq \cdots \geq a_{p_r} \geq 0$$ and each prime $$p_j \equiv 1 \pmod 4.$$

From the example below, it is clear we can take $p_r \leq 53.$

So, for example, you can do fairly well with all exponents $1$ and the product as large as possible below your bound, but you can do a little better.

To start, try $$5 \cdot 13 \cdot 17 \cdot 29 \cdot 37 \cdot 41 \cdot 53 = 2576450045$$ Better, $$5^2 \cdot 13^2 \cdot 17 \cdot 29 \cdot 37 \cdot 41 = 3159797225$$

3159797225 =  5^2 13^2 17 29 37 41
91  56212  count  1
1165  56200  count  2
1928  56179  count  3
2300  56165  count  4
2704  56147  count  5
3419  56108  count  6
3532  56101  count  7
5432  55949  count  8
5915  55900  count  9
6317  55856  count  10
6500  55835  count  11
7028  55771  count  12
7444  55717  count  13
8027  55636  count  14
8869  55508  count  15
9613  55384  count  16
10085  55300  count  17
10451  55232  count  18
11200  55085  count  19
11596  55003  count  20
11960  54925  count  21
12428  54821  count  22
13925  54460  count  23
14963  54184  count  24
15475  54040  count  25
15652  53989  count  26
16040  53875  count  27
17125  53540  count  28
17581  53392  count  29
18317  53144  count  30
18424  53107  count  31
19099  52868  count  32
19493  52724  count  33
20044  52517  count  34
20540  52325  count  35
21536  51923  count  36
21704  51853  count  37
22747  51404  count  38
23284  51163  count  39
23387  51116  count  40
23725  50960  count  41
24091  50788  count  42
24736  50477  count  43
25112  50291  count  44
25540  50075  count  45
26533  49556  count  46
26960  49325  count  47
27475  49040  count  48
28301  48568  count  49
28460  48475  count  50
28808  48269  count  51
29536  47827  count  52
30835  47000  count  53
31525  46540  count  54
31859  46312  count  55
32165  46100  count  56
32557  45824  count  57
32788  45659  count  58
33476  45157  count  59
33800  44915  count  60
33947  44804  count  61
34652  44261  count  62
35213  43816  count  63
35539  43552  count  64
36400  42835  count  65
36764  42523  count  66
37348  42011  count  67
37915  41500  count  68
38189  41248  count  69
38272  41171  count  70
38701  40768  count  71
39085  40400  count  72
3159797225 =  5^2 13^2 17 29 37 41

• oeis.org/A007511 tabulates the numbers with record number of expressions as sums of two squares. 3159797225 is the record holder for numbers under five billion. – Gerry Myerson Jul 7 '17 at 3:07
• @GerryMyerson Thanks. Given how tightly this is tied to number of divisors, Ramanujan's method for superior highly composite numbers will adapt nicely to this; however, that way does not fit well with a fixed upper bound. – Will Jagy Jul 7 '17 at 3:15
• Nice! The upper bound was arbitrary but I didn't want to ask if anyone could prove there is a max to the number of ways any number can be represented as the sum of two squares, since there is probably no way I'd understand the proof. – CommaToast Jul 7 '17 at 3:33
• The proof that there is no maximum is not hard to understand. – Gerry Myerson Jul 7 '17 at 6:47
• @Gerry thanks, extended that table a little, placed in answer – Will Jagy Jul 7 '17 at 19:23

There is a procedure initiated by Ramanujan that can be applied to this problem. With the same definitions as those for Superior Highly Composite Numbers, here are the first few numbers that are "superior" in the count as the sum of two squares, where the numbers being squared are positive and in order.

The nature of the construction is that these numbers are quick to create, while each is guaranteed to have more representations (as the sum of two squares) than any smaller number.

Well, why not. We fix a real number $\delta > 0.$ For each prime $p \equiv 1 \pmod 4,$ we take the exponent $k$ of $p$ as $$k = \left\lfloor \frac{1}{p^\delta - 1} \right\rfloor$$ If $p > 2^{1/\delta},$ then the denominator above exceeds $1$ and the relevant exponent is actually zero. That is, the product is actually a finite product.

Meanwhile, we are able to invert this in closed form. The first (largest) $\delta$ for which prime $p$ is given exponent $k$ is $$\delta = \frac{\log \left( 1 + \frac{1}{k} \right)}{ \log p}$$

As in the srvey article by Nicolas, in a log-log graph of $\log n$ and $\log r_2(n),$ these "superior" values, in output below, show up as the vertices of the convex hull of the (infinite) graph. Note that I told it to multiply the vertical component by 4, to create a little vertical separation between nearby points. I will need to experiment to draw in the line segments, I may need to do that by hand. You can see, though, how some points in the plot below are higher compared with those nearby... Alright, added line segments and labels by hand

=====================

Alright, I made it much faster, here are the first 54 such numbers. I wanted the list to reach both $5^5$ and $13^3,$ both of which have happened by the time we have reached $\delta = \frac{1}{9}.$

jagy@phobeusjunior:~$./Superior_Highly_Composite_read 1 5 = 5 log base ten 0.69897 2 65 = 5 13 log base ten 1.81291 3 325 = 5^2 13 log base ten 2.51188 6 5525 = 5^2 13 17 log base ten 3.74233 12 160225 = 5^2 13 17 29 log base ten 5.20473 24 5928325 = 5^2 13 17 29 37 log base ten 6.77293 48 243061325 = 5^2 13 17 29 37 41 log base ten 8.38572 64 1215306625 = 5^3 13 17 29 37 41 log base ten 9.08469 128 64411251125 = 5^3 13 17 29 37 41 53 log base ten 10.809 256 3929086318625 = 5^3 13 17 29 37 41 53 61 log base ten 12.5943 512 286823301259625 = 5^3 13 17 29 37 41 53 61 73 log base ten 14.4576 768 3728702916375125 = 5^3 13^2 17 29 37 41 53 61 73 log base ten 15.5716 1536 331854559557386125 = 5^3 13^2 17 29 37 41 53 61 73 89 log base ten 17.5209 3072 32189892277066454125 = 5^3 13^2 17 29 37 41 53 61 73 89 97 log base ten 19.5077 6144 3251179119983711866625 = 5^3 13^2 17 29 37 41 53 61 73 89 97 101 log base ten 21.512 12288 354378524078224593462125 = 5^3 13^2 17 29 37 41 53 61 73 89 97 101 109 log base ten 23.5495 24576 40044773220839379061220125 = 5^3 13^2 17 29 37 41 53 61 73 89 97 101 109 113 log base ten 25.6025 36864 680761144754269444040742125 = 5^3 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 log base ten 26.833 73728 93264276831334913833581671125 = 5^3 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 log base ten 28.9697 92160 466321384156674569167908355625 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 log base ten 29.6687 184320 69481886239344510806018344988125 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 log base ten 31.8419 368640 10908656139577088196544880163135625 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 log base ten 34.0378 737280 1887197512146836258002264268222463125 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 log base ten 36.2758 1474560 341582749698577362698409832548265825625 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 log base ten 38.5335 2949120 65925470691825431000793097681815304345625 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 log base ten 40.8191 5898240 12987317726289609907156240243317614956088125 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 log base ten 43.1135 11796480 2974095759320320668738779015719733824944180625 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 log base ten 45.4734 23592960 692964311921634715816135510662697981211994085625 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 log base ten 47.8407 47185920 167004399173113966511688658069710213472090574635625 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 log base ten 50.2227 94371840 42920130587490289393503985123915524862327277681355625 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 log base ten 52.6327 188743680 11545515128034887846852571998333276187966037696284663125 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 log base ten 55.0624 377487360 3198107690465663933578162443538317504066592441870851685625 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 log base ten 57.5049 754974720 898668261020851565335463646634267218642712476165709323660625 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 log base ten 59.9536 1509949440 263309800479109508643290848463840295062314755516552831832563125 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 log base ten 62.4205 3019898880 82415967549961276205350035569182012354504518476681036363592258125 = 5^4 13^2 17^2 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 log base ten 64.916 4529848320 2390063058948877009955151031506278358280631035823750054544175485625 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 log base ten 66.3784 9059696640 757649989686794012155782876987490239574960038356128767290503628943125 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 log base ten 68.8795 18119393280 255328046524449582096498829544784210736761532926015394576899722953833125 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 log base ten 71.4071 36238786560 89109488237032904151678091511129689547129774991179372707338003310887760625 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 log base ten 73.9499 72477573120 31455649347672615165542366303428780410136810571886318565690315168743379500625 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 log base ten 76.4977 144955146240 11732957206681885456747302631178935092981030343313596825002487557941280553733125 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 log base ten 79.0694 289910292480 4564120353399253442674700723528605751169620803548989164925967660039158135402185625 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 log base ten 81.6594 579820584960 1811955780299503616741856187240856483214339459008948698475609161035545779754667693125 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 log base ten 84.2581 1159641169920 726594267900100950313484331083583449768950123062588428088719273575253857681621744943125 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 log base ten 86.8613 2319282339840 297177055571141288678215091413185630955500600332598667088286182892278827791783293681738125 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 409 log base ten 89.473 4638564679680 125111540395450482533528553484951150632265752740024038844168482997649386500340766640011750625 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 409 421 log base ten 92.0973 9277129359360 54173296991230058937017863658983848223771070936430408819524953137982184354647551955125088020625 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 409 421 433 log base ten 94.7338 18554258718720 24323810349062296462721020782883747852473210850457253559966703958954000775236750827851164521260625 = 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 409 421 433 449 log base ten 97.386 22265110462464 121619051745311482313605103914418739262366054252286267799833519794770003876183754139255822606303125 = 5^5 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 409 421 433 449 log base ten 98.085 44530220924928 55579906647607347417317532488889363842901286793294824384523918546209891771415975641639910931080528125 = 5^5 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 409 421 433 449 457 log base ten 100.745 89060441849856 25622336964546987159383382477377996731577493211708914041265526449802760106622764770795998939228123465625 = 5^5 13^2 17^2 29^2 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 409 421 433 449 457 461 log base ten 103.409 133590662774784 948026467688238524897185151662985879068367248833229819526824478642702123945042296519451960751440568228125 = 5^5 13^2 17^2 29^2 37^2 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 409 421 433 449 457 461 log base ten 104.977 178120883699712 12324344079947100823663406971618816427888774234831987653848718222355127611285549854752875489768727386965625 = 5^5 13^3 17^2 29^2 37^2 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 409 421 433 449 457 461 log base ten 106.091 356241767399424 6273091136693074319244674148553977561795386085529481715808997575178759954144344876069213624292282239965503125 = 5^5 13^3 17^2 29^2 37^2 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 197 229 233 241 257 269 277 281 293 313 317 337 349 353 373 389 397 401 409 421 433 449 457 461 509 log base ten 108.797 jagy@phobeusjunior:~$


======================

• OK, but this doesn't get all the record setting numbers, e.g., it doesn't get that number 3159797225 with its 72 representations. – Gerry Myerson Jul 8 '17 at 8:49
• @Gerry, no, it doesn't, only certain extremal points. I learned of this first in math.univ-lyon1.fr/~nicolas/hcnrevisited.pdf I think I have a better scan, if so I will email you that. I like the log-log graph on page 228, it shows how the s.h.c. numbers are the vertices of a certain convex hull. – Will Jagy Jul 8 '17 at 18:32
• But you don't show which two squares each number is the sum of. Where can I see that? Still pretty cool though. – CommaToast Jul 9 '17 at 0:56
• @CommaToast some sort of misunderstanding. The number 341582749698577362698409832548265825625 can be written as the sum of two squares in 1474560 different ways, that is one million, four hundred seventy four thousand, five hundred sixty different integer pairs $(x,y)$ such that $0 < x < y$ and the number is $x^2 + y^2.$ – Will Jagy Jul 9 '17 at 1:09