1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Will Jagy Jul 7 '17 at 2:09
  • $\begingroup$ @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. $\endgroup$ – Oscar Lanzi Jul 7 '17 at 2:21
  • $\begingroup$ @OscarLanzi I put one in my answer, 72 expressions and the number about 3 billion 3159797225 = 5^2 13^2 17 29 37 41 $\endgroup$ – Will Jagy Jul 7 '17 at 2:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Oscar Lanzi Jul 7 '17 at 2:30
  • $\begingroup$ @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 $\endgroup$ – Will Jagy Jul 7 '17 at 2:43
5
$\begingroup$

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.

http://oeis.org/A007511

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jul 7 '17 at 3:07
  • $\begingroup$ @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. $\endgroup$ – Will Jagy Jul 7 '17 at 3:15
  • $\begingroup$ 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. $\endgroup$ – CommaToast Jul 7 '17 at 3:33
  • $\begingroup$ The proof that there is no maximum is not hard to understand. $\endgroup$ – Gerry Myerson Jul 7 '17 at 6:47
  • 1
    $\begingroup$ @Gerry thanks, extended that table a little, placed in answer $\endgroup$ – Will Jagy Jul 7 '17 at 19:23
1
$\begingroup$

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

enter image description here enter image description here enter image description here

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

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:~$ 

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

$\endgroup$
  • $\begingroup$ OK, but this doesn't get all the record setting numbers, e.g., it doesn't get that number 3159797225 with its 72 representations. $\endgroup$ – Gerry Myerson Jul 8 '17 at 8:49
  • 1
    $\begingroup$ @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. $\endgroup$ – Will Jagy Jul 8 '17 at 18:32
  • $\begingroup$ But you don't show which two squares each number is the sum of. Where can I see that? Still pretty cool though. $\endgroup$ – CommaToast Jul 9 '17 at 0:56
  • $\begingroup$ @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.$ $\endgroup$ – Will Jagy Jul 9 '17 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.