Una búsqueda de enteros que se puede escribir como una suma de dos cuadrados de múltiples maneras

Question

Como parte de una teoría de los números proyecto hobby, estoy buscando un computacional para enumerar todos los enteros $n$ que puede ser escrito como suma de dos enteros cuadrados en tres o más formas. El rango de $n$ es probable que llegar a ser bastante grande ( a a$\approx 2^{64}$), así que estoy buscando métodos que me permite especificar un intervalo de búsqueda para $n$, decir $11\cdot10^{13}$$12\cdot10^{14}$, y devuelve todos los valores tales como

$$1193162282546 = 1043815^2+321889^2 = 1066211^2+237395^2 = 1076911^2+182825^2$$

Mi primer pensamiento de la solución de este problema es bastante fuerza bruta:

Enumerar $every$ suma de dos cuadrados dentro de un rango de $n_0..n_1$ por iterando sobre $n=a^2+b^2$ en un doble bucle de más de $1\le a \le\sqrt{n_1-1} $$\sqrt{n_0^2-a^2}\le b \le \sqrt{n_1^2-a^2}$, la ordenación de la lista y la detección de valores duplicados de 3 o más valores. Creo que esto va a funcionar, pero puede ser muy ineficiente, con la gran mayoría de la computación tirado.

El acertijo: ¿existe un mejor método de cálculo?

Answer 1

Ya que no requieren relativamente primos $x,y$ $x^2 + y^2 = n,$ este tiene una muy simple caracterización, mediante la descomposición en factores primos de a $n:$

(A) el exponente de 2 es irrelevante

(B) si $q \equiv 3 \pmod 4,$ el exponente debe ser, incluso, de lo contrario este primer es también irrelevante en cuanto al conteo de $x^2 + y^2$ expresiones

(C) no debe ser $p^{4 + k}$ $k \geq 0, \; \; p \equiv 1 \pmod 4,$ o $p_1^{1 + k_1} p_2^{2 + k_2}$ $k_1, k_2 \geq 0, \; \; p_1, p_2 \equiv 1 \pmod 4,$ donde no nos importa si $p_1$ o $p_2$ es mayor, o $p_1^{1 + k_1} p_2^{1 + k_2} p_3^{1 + k_3}$ $k_1, k_2, k_3 \geq 0, \; \; p_1, p_2, p_3 \equiv 1 \pmod 4.$ Aquí $p_1, p_2, p_3$ son distintos.

Derecho, por lo que tres distintas buena primos hace, o uno y otro cuadrado o mejor, o uno a la cuarta potencia o más.

EEEDDDIITTT: dada su anti-factoring postura, la mejor manera de hacer esto es pulverizar las cosas. Haga una lista de números primos $1 \pmod 4$ hasta un apropiado obligado. El uso que hacen de una lista de hasta el $1.2 \cdot 10^{15}$ de los exitosos números de tipo (C). Guardar y multiplicar por arbitraria $q^2$ $q \equiv 3 \pmod 4$ y arbitraria $2^k,$ y mantener el resultado, si no es demasiado grande.

Me decidí a realizar un pequeño programa, los números impares hasta el $1 + 13^4$ que se pueden expresar en menos de tres maneras como $x^2 + y^2$ $0 \leq x \leq y,$ y no divisible por cualquier prime $q \equiv 3 \pmod 4.$ tenga en cuenta que multiplicar por 2 o por $q^2$ no cambia el número de representaciones. Sin embargo, encontré que los números con al menos tres representaciones en primer lugar, luego me dijo que solo imprima el fib impar y no divisible por cualquier $q \equiv 3 \pmod 4,$ y, finalmente, encontrar la factorización prima de cada uno y de impresión. Así que esta pequeña tabla experimentalmente confirma los patrones en la parte (C) anteriores; yo no construir esas.

---

325 = 5^2 * 13
425 = 5^2 * 17
625 = 5^4
725 = 5^2 * 29
845 = 5 * 13^2
925 = 5^2 * 37
1025 = 5^2 * 41
1105 = 5 * 13 * 17
1325 = 5^2 * 53
1445 = 5 * 17^2
1525 = 5^2 * 61
1625 = 5^3 * 13
1825 = 5^2 * 73
1885 = 5 * 13 * 29
2125 = 5^3 * 17
2225 = 5^2 * 89
2405 = 5 * 13 * 37
2425 = 5^2 * 97
2465 = 5 * 17 * 29
2525 = 5^2 * 101
2665 = 5 * 13 * 41
2725 = 5^2 * 109
2825 = 5^2 * 113
2873 = 13^2 * 17
3125 = 5^5
3145 = 5 * 17 * 37
3425 = 5^2 * 137
3445 = 5 * 13 * 53
3485 = 5 * 17 * 41
3625 = 5^3 * 29
3725 = 5^2 * 149
3757 = 13 * 17^2
3925 = 5^2 * 157
3965 = 5 * 13 * 61
4205 = 5 * 29^2
4225 = 5^2 * 13^2
4325 = 5^2 * 173
4505 = 5 * 17 * 53
4525 = 5^2 * 181
4625 = 5^3 * 37
4745 = 5 * 13 * 73
4825 = 5^2 * 193
4901 = 13^2 * 29
4925 = 5^2 * 197
5125 = 5^3 * 41
5185 = 5 * 17 * 61
5365 = 5 * 29 * 37
5525 = 5^2 * 13 * 17
5725 = 5^2 * 229
5785 = 5 * 13 * 89
5825 = 5^2 * 233
5945 = 5 * 29 * 41
6025 = 5^2 * 241
6205 = 5 * 17 * 73
6253 = 13^2 * 37
6305 = 5 * 13 * 97
6409 = 13 * 17 * 29
6425 = 5^2 * 257
6565 = 5 * 13 * 101
6625 = 5^3 * 53
6725 = 5^2 * 269
6845 = 5 * 37^2
6925 = 5^2 * 277
6929 = 13^2 * 41
7025 = 5^2 * 281
7085 = 5 * 13 * 109
7225 = 5^2 * 17^2
7325 = 5^2 * 293
7345 = 5 * 13 * 113
7565 = 5 * 17 * 89
7585 = 5 * 37 * 41
7625 = 5^3 * 61
7685 = 5 * 29 * 53
7825 = 5^2 * 313
7925 = 5^2 * 317
8125 = 5^4 * 13
8177 = 13 * 17 * 37
8245 = 5 * 17 * 97
8381 = 17^2 * 29
8405 = 5 * 41^2
8425 = 5^2 * 337
8585 = 5 * 17 * 101
8725 = 5^2 * 349
8825 = 5^2 * 353
8845 = 5 * 29 * 61
8905 = 5 * 13 * 137
8957 = 13^2 * 53
9061 = 13 * 17 * 41
9125 = 5^3 * 73
9265 = 5 * 17 * 109
9325 = 5^2 * 373
9425 = 5^2 * 13 * 29
9605 = 5 * 17 * 113
9685 = 5 * 13 * 149
9725 = 5^2 * 389
9805 = 5 * 37 * 53
9925 = 5^2 * 397
10025 = 5^2 * 401
10205 = 5 * 13 * 157
10225 = 5^2 * 409
10309 = 13^2 * 61
10525 = 5^2 * 421
10585 = 5 * 29 * 73
10625 = 5^4 * 17
10693 = 17^2 * 37
10825 = 5^2 * 433
10865 = 5 * 41 * 53
10933 = 13 * 29^2
10985 = 5 * 13^3
11125 = 5^3 * 89
11225 = 5^2 * 449
11245 = 5 * 13 * 173
11285 = 5 * 37 * 61
11425 = 5^2 * 457
11525 = 5^2 * 461
11645 = 5 * 17 * 137
11713 = 13 * 17 * 53
11765 = 5 * 13 * 181
11849 = 17^2 * 41
12025 = 5^2 * 13 * 37
12125 = 5^3 * 97
12325 = 5^2 * 17 * 29
12337 = 13^2 * 73
12505 = 5 * 41 * 61
12545 = 5 * 13 * 193
12625 = 5^3 * 101
12665 = 5 * 17 * 149
12725 = 5^2 * 509
12805 = 5 * 13 * 197
12905 = 5 * 29 * 89
13025 = 5^2 * 521
13325 = 5^2 * 13 * 41
13345 = 5 * 17 * 157
13481 = 13 * 17 * 61
13505 = 5 * 37 * 73
13525 = 5^2 * 541
13625 = 5^3 * 109
13925 = 5^2 * 557
13949 = 13 * 29 * 37
14045 = 5 * 53^2
14065 = 5 * 29 * 97
14125 = 5^3 * 113
14225 = 5^2 * 569
14297 = 17 * 29^2
14365 = 5 * 13^2 * 17
14425 = 5^2 * 577
14645 = 5 * 29 * 101
14705 = 5 * 17 * 173
14825 = 5^2 * 593
14885 = 5 * 13 * 229
14965 = 5 * 41 * 73
15025 = 5^2 * 601
15041 = 13^2 * 89
15145 = 5 * 13 * 233
15317 = 17^2 * 53
15325 = 5^2 * 613
15385 = 5 * 17 * 181
15425 = 5^2 * 617
15457 = 13 * 29 * 41
15625 = 5^6
15665 = 5 * 13 * 241
15725 = 5^2 * 17 * 37
15805 = 5 * 29 * 109
16025 = 5^2 * 641
16133 = 13 * 17 * 73
16165 = 5 * 53 * 61
16325 = 5^2 * 653
16385 = 5 * 29 * 113
16393 = 13^2 * 97
16405 = 5 * 17 * 193
16465 = 5 * 37 * 89
16525 = 5^2 * 661
16705 = 5 * 13 * 257
16745 = 5 * 17 * 197
16825 = 5^2 * 673
16925 = 5^2 * 677
17069 = 13^2 * 101
17125 = 5^3 * 137
17225 = 5^2 * 13 * 53
17425 = 5^2 * 17 * 41
17485 = 5 * 13 * 269
17525 = 5^2 * 701
17629 = 17^2 * 61
17725 = 5^2 * 709
17797 = 13 * 37^2
17945 = 5 * 37 * 97
18005 = 5 * 13 * 277
18125 = 5^4 * 29
18241 = 17 * 29 * 37
18245 = 5 * 41 * 89
18265 = 5 * 13 * 281
18325 = 5^2 * 733
18421 = 13^2 * 109
18605 = 5 * 61^2
18625 = 5^3 * 149
18685 = 5 * 37 * 101
18785 = 5 * 13 * 17^2
18925 = 5^2 * 757
19025 = 5^2 * 761
19045 = 5 * 13 * 293
19097 = 13^2 * 113
19225 = 5^2 * 769
19325 = 5^2 * 773
19345 = 5 * 53 * 73
19465 = 5 * 17 * 229
19625 = 5^3 * 157
19669 = 13 * 17 * 89
19721 = 13 * 37 * 41
19805 = 5 * 17 * 233
19825 = 5^2 * 13 * 61
19865 = 5 * 29 * 137
19885 = 5 * 41 * 97
19925 = 5^2 * 797
19981 = 13 * 29 * 53
20165 = 5 * 37 * 109
20213 = 17 * 29 * 41
20225 = 5^2 * 809
20345 = 5 * 13 * 313
20485 = 5 * 17 * 241
20525 = 5^2 * 821
20605 = 5 * 13 * 317
20705 = 5 * 41 * 101
20725 = 5^2 * 829
20905 = 5 * 37 * 113
21025 = 5^2 * 29^2
21097 = 17^2 * 73
21125 = 5^3 * 13^2
21325 = 5^2 * 853
21425 = 5^2 * 857
21437 = 13 * 17 * 97
21605 = 5 * 29 * 149
21625 = 5^3 * 173
21845 = 5 * 17 * 257
21853 = 13 * 41^2
21905 = 5 * 13 * 337
21925 = 5^2 * 877
22025 = 5^2 * 881
22265 = 5 * 61 * 73
22321 = 13 * 17 * 101
22345 = 5 * 41 * 109
22525 = 5^2 * 17 * 53
22625 = 5^3 * 181
22685 = 5 * 13 * 349
22765 = 5 * 29 * 157
22865 = 5 * 17 * 269
22945 = 5 * 13 * 353
22997 = 13 * 29 * 61
23125 = 5^4 * 37
23153 = 13^2 * 137
23165 = 5 * 41 * 113
23225 = 5^2 * 929
23273 = 17 * 37^2
23425 = 5^2 * 937
23525 = 5^2 * 941
23545 = 5 * 17 * 277
23585 = 5 * 53 * 89
23725 = 5^2 * 13 * 73
23825 = 5^2 * 953
23885 = 5 * 17 * 281
24089 = 13 * 17 * 109
24125 = 5^3 * 193
24245 = 5 * 13 * 373
24425 = 5^2 * 977
24505 = 5 * 13^2 * 29
24565 = 5 * 17^3
24625 = 5^3 * 197
24905 = 5 * 17 * 293
24925 = 5^2 * 997
24973 = 13 * 17 * 113
25085 = 5 * 29 * 173
25181 = 13^2 * 149
25225 = 5^2 * 1009
25285 = 5 * 13 * 389
25325 = 5^2 * 1013
25345 = 5 * 37 * 137
25493 = 13 * 37 * 53
25525 = 5^2 * 1021
25625 = 5^4 * 41
25705 = 5 * 53 * 97
25721 = 17^2 * 89
25789 = 17 * 37 * 41
25805 = 5 * 13 * 397
25825 = 5^2 * 1033
25925 = 5^2 * 17 * 61
26065 = 5 * 13 * 401
26129 = 17 * 29 * 53
26225 = 5^2 * 1049
26245 = 5 * 29 * 181
26525 = 5^2 * 1061
26533 = 13^2 * 157
26585 = 5 * 13 * 409
26605 = 5 * 17 * 313
26645 = 5 * 73^2
26725 = 5^2 * 1069
26765 = 5 * 53 * 101
26825 = 5^2 * 29 * 37
26945 = 5 * 17 * 317
27145 = 5 * 61 * 89
27325 = 5^2 * 1093
27365 = 5 * 13 * 421
27425 = 5^2 * 1097
27521 = 13 * 29 * 73
27565 = 5 * 37 * 149
27625 = 5^3 * 13 * 17
27725 = 5^2 * 1109
27925 = 5^2 * 1117
27985 = 5 * 29 * 193
28033 = 17^2 * 97
28085 = 5 * 41 * 137
28145 = 5 * 13 * 433
28225 = 5^2 * 1129
28249 = 13 * 41 * 53
28561 = 13^4

\begin{align*} a\mid b &\Rightarrow b = ak,\\a\mid c &\Rightarrow c = aj,\\a\mid a &\Rightarrow a = ah,\end----------------------