《四平方和定理》与《齐肯多夫定理》

刺骨的言语ヽ痛彻心扉 2022-08-28 13:55 199阅读 0赞

定理：

> 是经过受逻辑限制的证明为真的陈述

## //1.四平方和定理 (Lagrange’s four-square theorem) ##

#### 简介 ####

*  每个正整数均可表示为4个整数的平方和
 *  对于某些自然数，还可以被表示为1-3个整数的平方和，如 5=1*1+2*2
 *  有些整数最少为4个数的平方和，例如7
 *  如果一个数最少为4个数的平方和，那么它还满足：n = (4^k) \* (8m + 7)

#### 公式的使用 ####

假设判断 368

368 只要能整除 4，则除以 4  
得到 368 / 4 = 92 / 4 = 23 / 4 = 5.75  
最后为 23

再判断除以 8 是否余 7  
23 / 8 = 16…7  
得到 16 余 7

**那铁定满足：n = (4^k) \* (8m + 7)**  
说明最少为四个数的平方和

**转成代码的使用**

public boolean checkAnswer4(int x) {
        
        // 判断这个数是否被4整除，如果被整除，则除以4之后再判断
        while (x % 4 == 0) {
        
            x /= 4;
        }
        // 判断这个数除以 8，是否余 7，余 7代表最大只能被表示为4个正整数的平方和
        return x % 8 == 7;
    }

**该定理在算法题的使用**：https://leetcode-cn.com/problems/perfect-squares/comments/

## //2.齐肯多夫定理 (Zeckendorf) ##

#### 简介 ####

*  表示任何正整数都可以表示成若干个不连续的斐波那契数（不包括第一个斐波那契数）之和。这种和式称为齐肯多夫表述法。

**斐波那契数列：**

> 又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……  
> 在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1，F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈  
> N\*）  
> 这个数列从第3项开始，每一项都等于前两项之和。  
> 通俗点讲：a(n) = a(n-1) + a(n-2)

#### 验证推导 ####

*  如果 m 是斐波那契数，则直接成立。
 *  如果不是，那么肯定在两个斐波那契数的中间(n1 m n2)，m 减掉左边的斐波那契数(n1)后，得到 m\`，此时 m\` 不是斐波那契数，则肯定也在两个的中间，再让 m\` 减掉左边的斐波那契数，以此循环，直到成为斐波那契数。
 *  由于它减了多个斐波那契数后，自己变成了斐波那契数，因此说明，它本身(m\`)再加上所有被减掉的斐波那契数得到 m。也就是任何数都可以表示成若干个不连续的斐波那契数。
 *  不连续的原因：因为 m\` < m 左边的数(n1)，说明了 m\` 左边的数也 < m 左边的数，因此这两个斐波那契数一定不连续。