a^2+b^2+c^2=d^2（0<a<b<c<d） 恰好有44组正整数解

northwolves

mathe 发表于 2025-10-9 10:32
这个题目如果对于每个d,我们穷举c,b,a,那么复杂度显然是O(d^3), 时间复杂度稍微有点高。
另外一种方法，我 ...

有一个疑问，字典保存一定范围内的a^2+b^2=sum2 的组合，穷举(d^2-c^2)时，如何保证c>b?

lsr314

我们通过解的分类得到解数的公式：

1. rr[p_, m_] := If[p == 2, 1, If[Mod[p, 4] == 1, p^m, ((p + 1)/2 p^m - 1)/((p - 1)/2)]]
   
2. ss[p_, m_] :=If[p == 2, 1, If[(Mod[p, 8] == 5 || Mod[p, 8] == 7), 1, 2 m + 1]]
   
3. tt[p_, m_] := If[Mod[p, 4] == 1, 2 m + 1, 1]
   
4. 
   
5. r[q_] := Times @@ Cases[FactorInteger[q], {a_, b_} -> rr[a, b]]
   
6. s[q_] := If[q == 1, 1, Times @@ Cases[FactorInteger[q], {a_, b_} -> ss[a, b]]]
   
7. t[q_] := If[q == 1, 1, Times @@ Cases[FactorInteger[q], {a_, b_} -> tt[a, b]]]
   
8. 
   
9. f[q_] := (6 r[q] - 12 s[q] - 12 t[q] + 18)/48

复制代码

其中6rr,2ss,4tt分别表示$x^2+y^2+z^2=(p^m)^2,x^2+2y^2=(p^m)^2,x^2+y^2=(p^m)^2$的整数解个数，且rr,ss,tt都是积性函数，r,s,t将它们推广到全部整数（因式分解后直接相乘）。

通过这个公式，可以得出数列的第45项到第77项依次为：213, 319, 379, 383, 255, 237, 225, 207, 267, 431, 329, 457, 343, 189, 371, 261, 487, 303, 285, 451, 309, 321, 327, 339, 279, 563, 231, 273, 587, 601, 551, 375, 333.

当q<2*10^7时，没有找到f(q)=44或78的解. 能否通过对f(q)的讨论，证明解不存在？

lsr314

通过f的公式，可以得到$f(2q)=f(q)$,所以a(n)一定是奇数，假设q是奇数，那么：
（1）$r(q)>=q.$
（2）$s(q)=\prod_{p^m||q, p\equiv 1,3 \mod 8}(2m+1)$
（3）$t(q)=\prod_{p^m||q, p\equiv 1 \mod 4}(2m+1)$
（4）$f(q)=1/8r(q)-1/2s(q)-1/2t(q)+3/8>q/8-1/2s(q)-1/2t(q)$

对任意k>0,$d(n)<=n^k*\prod_{p^k<2}2/(k\log2),$我们可以得出s(q)和t(q)的上界，从而得到一个f(q)的下界。

mathe

northwolves 发表于 2025-10-9 18:19
有一个疑问，字典保存一定范围内的a^2+b^2=sum2 的组合，穷举(d^2-c^2)时，如何保证c>b? ...

有两种不同方案可用，第一种
1）事先计算所有的a^2+b^2=sum2，保存所有和sum2的出现计数
2) 按c从大到小顺序穷举所有d^2-c^2, 每次穷举每个c时，从前面和的计数中删除a^2+c^2(对于所有a<c)
第二种:
  我们不需要区分a,b,c的大小，转而计算
i) a^2+b^2+c^2=d^2 (a>0,b>0,c>0)的数目
ii)计算2a^2+c^2=d^2的数目
iii)3a^2=d^2的数目（当然这个数目为0）
然后推导出0<a<b<c<d的解的数目。

而lsr314的方法应该是
i) a^2+b^2+c^2=d^2的整数解数目(包含0和负数都可以出现)
ii) 2a^2+c^2=d^2的整数解数目
iii)b^2+c^2=d^2的整数解数目 （相当于a=0)
然后利用上面结果求出解的数目

mathe

lsr314 发表于 2025-10-9 22:33
通过f的公式，可以得到$f(2q)=f(q)$,所以a(n)一定是奇数，假设q是奇数，那么：
（1）$r(q)>=q.$
（2）$s(q) ...

可以这么弄，由于在\(x\ge 1\)时有\(2\times 3^{0.75x}-2x-1>0\)
而对于\(p\ge 5,x\ge 1\)我们都有\(p^{0.75x}-2x-1\ge 5^{0.75x}-2x-1\gt 0\)
由此我们得到
\(s(q)\le \prod_{p^m ||q} (2m+1) \le 2 q^{0.75}\)
同样\(t(q)\le 2 q^{0.75}\)
由此根据(4)可以得到
\(f(q) \gt \frac q 8 - 2 q^{0.75}\)
由此得到对于奇数\(q \gt 66932.9...\), \(f(q) \gt 44\)

lsr314

这个链接有一个解数的公式：不定方程ax~2+by~2+cz~2=n解的个数

另一个公式 Some formulae for partitions into squares

mathe

第一篇文章里面好多符号看不懂。
不过第二个文章里面相当于给出了lsr314定义的
\(r(n)=4e_{1,3,4}(n) + 8\sum_{1\le k^2 \lt n} e_{1,3,4}(n-k^2) + 2 \delta(n)\)
其中\(\delta(n)\)在n为完全平方数时是1，n不是完全平方数时为0.
而\(e_{r,s,m}(n) = d_{r,m}(n)-d_{s,m}(n)\),而\(d_{r,m}(n)\)代表n的模m余数为r的因子的数目。
也就是解的数目和n模4余数为1和3的因子数目有关系，而同偶数因子没有关系。

mathe

如果设整数\(m=2^a p_1^{b_1}p_2^{b_2}\cdots p_t^{b_t}Q\)其中\(p_i\)都是模4为1的素因子，而Q的所有素因子都模4为3，
那么经过计算可以知道\(e_{1,3,4}(m)=\begin{cases}\prod_{h=1}^t (b_h+1)&if \space\space \delta(Q)==1\\0&otherwise\end{cases}\)
这个是因为最终一个因子模4余数为1还是3仅取决于模4为3的素因子总数目的奇偶性。

northwolves

mathe 发表于 2025-10-10 08:23
可以这么弄，由于在\(x\ge 1\)时有\(2\times 3^{0.75x}-2x-1>0\)
而对于\(p\ge 5,x\ge 1\)我们都有\(p^{0 ...

mathe版主可以研究一下得到一个完美证明（10000内有482个数字）：

{482,{44,78,174,183,205,210,282,295,330,372,384,404,434,460,468,479,480,509,582,624,652,670,674,678,709,744,745,750,759,782,804,810,839,866,867,897,953,999,1004,1023,1026,1031,1051,1095,1096,1122,1173,1200,1227,1244,1245,1259,1268,1413,1446,1517,1545,1562,1583,1605,1616,1635,1642,1668,1689,1694,1721,1731,1767,1773,1812,1880,1906,1914,1937,1965,1979,1993,2010,2019,2022,2024,2034,2070,2085,2094,2108,2193,2291,2304,2351,2400,2409,2420,2460,2520,2522,2535,2546,2547,2571,2572,2603,2604,2607,2621,2675,2692,2748,2757,2759,2791,2832,2834,2850,2860,2874,2909,2913,2923,2949,2955,2984,3012,3032,3044,3050,3060,3070,3094,3108,3124,3130,3151,3179,3195,3201,3226,3248,3285,3291,3297,3302,3330,3374,3377,3390,3408,3417,3432,3480,3500,3501,3505,3507,3521,3529,3546,3584,3585,3621,3669,3689,3746,3747,3762,3768,3801,3809,3824,3825,3842,3911,3927,3931,3954,3957,3977,3984,3989,3993,4030,4080,4083,4084,4155,4180,4212,4238,4289,4332,4398,4433,4434,4444,4447,4476,4478,4484,4509,4541,4568,4587,4610,4614,4620,4623,4628,4637,4677,4704,4710,4713,4766,4769,4781,4795,4810,4844,4845,4851,4872,4875,4887,4896,4961,4992,5022,5033,5049,5093,5097,5100,5114,5122,5133,5170,5184,5187,5205,5254,5294,5317,5327,5345,5360,5406,5419,5469,5475,5478,5489,5508,5529,5532,5543,5564,5583,5584,5604,5609,5633,5643,5645,5654,5655,5677,5685,5717,5749,5759,5780,5790,5799,5803,5816,5847,5930,5946,5960,5978,5987,6002,6068,6079,6099,6136,6154,6185,6222,6225,6235,6257,6267,6293,6310,6329,6333,6341,6344,6387,6421,6477,6505,6511,6559,6606,6609,6618,6629,6661,6669,6675,6689,6697,6704,6717,6738,6743,6795,6869,6887,6900,6960,6963,6994,7001,7008,7035,7047,7067,7069,7077,7110,7116,7122,7185,7218,7238,7244,7245,7260,7292,7294,7307,7323,7333,7334,7347,7404,7412,7432,7473,7480,7499,7554,7584,7593,7603,7604,7620,7623,7634,7680,7681,7712,7720,7758,7760,7764,7792,7797,7823,7833,7834,7850,7851,7855,7908,7922,7926,7932,7935,7967,7985,8006,8025,8030,8044,8081,8084,8092,8104,8108,8136,8154,8170,8218,8246,8252,8265,8275,8283,8290,8309,8334,8340,8364,8367,8374,8450,8453,8472,8479,8489,8490,8500,8520,8536,8569,8607,8615,8697,8705,8718,8735,8744,8792,8819,8837,8851,8867,8922,8954,9016,9025,9040,9074,9106,9145,9160,9229,9245,9255,9278,9284,9322,9348,9350,9360,9373,9380,9404,9419,9420,9434,9447,9469,9476,9479,9489,9495,9501,9503,9533,9539,9544,9587,9601,9647,9680,9687,9697,9739,9845,9901,9909,9917,9929,9957,9959,9990}}

northwolves

lsr314 发表于 2025-10-9 19:34
我们通过解的分类得到解数的公式：

lsr314的代码非常好使，我略加变动了一下：

1. r[p_,m_]:=If[p==2,1,If[Mod[p,4]==1,p^m,((p+1) p^m-2)/(p-1)]]
   
2. s[p_,m_]:=If[p==2,1,If[MemberQ[{5,7},Mod[p,8]],1,2 m+1]]
   
3. t[p_,m_]:=If[Mod[p,4]==1,2 m+1,1]
   
4. f[q_]:=If[q==1,0,fi=FactorInteger@q;(Times@@(r@@@fi)-2 Times@@(s@@@fi)-2Times@@(t@@@fi)+3)/8]

复制代码