不能写成3个平方数之和的正整数

KeyTo9_Fans

设数列${A_n}$是不能表示成$(a^2+b^2+c^2)$的正整数组成的数列：

http://oeis.org/A004215

$A_1=7$
$A_2=15$
$A_3=23$
$A_4=28$
$A_5=31$
……

求证：

(1)$A_n>6n$

(2)$lim_{n->\infty}{A_n}/n=6$

mathe

链接上说这个数列实际上就是$4^a(8k+7)$,主要这个结论比较困难，我没有找到证明。
有了这个结论，这里的问题就很简单了

zgg___

呵呵，如果已知某个数列A就是4^a(8k+7)，那么如何证明A/n趋于6呢？请mathe指点一下呢。
我画了个图，的确应是趋于6呢。
s1 = Table[4^a (8 k + 7), {a, 0, 8}, {k, 0, 65000}];
s2 = Union[Flatten[s1]];
n = Length[s2]
s3 = s2/Range[n];
ListPlot[Take[s3, 90000]]

mathe

不超过n的数中
8k+7型的有$[{n+1}/8]$个
4(8k+7)型的有$[{n+4}/32]$个
..
$4^h(8k+7)$型的有$[{n+4^h}/{2^{2h+3}}]$个
累加即可。
结果严格小于${n+1}/8+{n+4}/32+...={n+1}/6$
所以我们得到$n<{A_n+1}/6$,或者说$6n<=A_n$
另外由于$A_n$不是3的倍数，不可能等于$6n$,所以得到$A_n>6n$
而又因为上面计数可以反向防缩得到$n>{A_n+1}/6-log_2(A_n)$
于是我们得到$lim_{n->+infty}{A_n}/n<=6$,结合$A_n>6n$得到$lim_{n->+infty}{A_n}/n=6$

KeyTo9_Fans

形如$(8k+7)$的正整数不能表示成$3$个平方数之和是很容易证明的。

首先看$a^2 mod 8$的结果：

$0^2 mod 8=0$
$1^2 mod 8=1$
$2^2 mod 8=4$
$3^2 mod 8=1$
$4^2 mod 8=0$
$5^2 mod 8=1$
$6^2 mod 8=4$
$7^2 mod 8=1$

只有$0$、$1$、$4$三种结果。

其中：

$0=0+0+0$
$1=1+0+0$
$2=1+1+0$
$3=1+1+1$
$4=4+0+0$
$5=4+1+0$
$6=4+1+1$

而$7$不能用$3$个$0$、$1$、$4$来表示。

所以形如$(8k+7)$的正整数不能表示成$3$个平方数之和。

剩下的问题还有：

1. $4(8k+7)$、$16(8k+7)$、……的正整数也不能表示成$3$个平方数之和。

2. 其余的正整数可以表示成$3$个平方数之和。

mathe

$4^a(8b+7)$不能表示成三平方数和也简单。由于是偶数，那么三个平方数必然全部偶数或两奇一偶。
对于全部偶数的情况，可以退化成$4^{a-1}(8b+7)$问题，所以只需要考虑两奇一偶情况，但是这时和不是4的倍数，矛盾

gxqcn

所以，最终归结于$(8b+7)$型问题，若可能，考虑到奇偶性只有下面两种情形：
1、全奇，则其平方和模8余3（奇数^2 mod 8 ≡ 1），矛盾；
2、一奇两偶，则其平方和模8余1或5（偶数^2 mod 8 ≡ 0 or 4），矛盾。

zgg___

所以相当于求证形如8k+3的数可以表示成3个平方数的和。
相当于求证任意正整数都可以表示为3个形如n(n-1)/2的数的和。

zgg___

网页http://oeis.org/A061262中说：
Fermat claimed, Euler tried, Gauss proved (Jul 10, 1796) that every number can be represented as a sum of three triangular numbers.
网页http://en.wikipedia.org/wiki/Carl_Friedrich_Gauss中说：
Gauss also discovered that every positive integer is representable as a sum of at most three triangular numbers on 10 July and then jotted down in his diary the famous words, "Heureka! num = Δ + Δ + Δ."
由此说来，这个不是那么容易证明的，佩服mathe对题目难易程度的直觉。

mathe

找到一篇文章简介了一种证明这个三平方数和的充要条件，但是很难看懂:
http://www.math.sunysb.edu/~dela ... les/sum3squares.pdf