一些数论的公式

2024-08-28 10:58
文章标签 公式 数论

本文主要是介绍一些数论的公式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

以下等式或者不等式均可以用数学归纳法予以证明！

1 + 3 + 5 + ... + (2n - 1) = n^2

1*2 + 2*3 + 3*4 + ... + n*(n + 1) = n*(n + 1)*(n + 2) / 3

1*1! + 2*2! + 3*3! + ... + n*n! = (n + 1)! - 1

1^2 + 2^2 + 3^2 + ... + n^2 = n*(n + 1)*(2n + 1) / 6

1^2 - 2^2 + 3^2 -... + (-1)^n * n^2 = (-1)^(n + 1) * n * (n + 1) / 2

2^2 + 4^2 + ... + (2n)^2 = 2n*(n+1)*(2n+1) / 3

1/2! + 2/3! + ... + n/(n+1)! = 1 - 1/(n+1)!

2^(n + 1) < 1 + (n + 1)2^n

1^3 + 2^3 + 3^3 + ... + n^3 = (n*(n + 1) / 2)^2

1^4 + 2^4 + 3^4 + ... + n^4 = n(n+1)(2n+1)(3n^2+3n-1)/30

1/2n <= 1*3*5*...*(2n-1) / (2*4*6*...*2n) <= 1 / sqrt(n+1)  n=1,2...

2^n >= n^2 , n=4, 5,...

2^n >= 2n + 1, n=3,4,...

r^0 + r^1 + ... + r^n < 1 / (1 - r), n>=0, 0<r<1

1*r^1 + 2*r^2 + ... + n*r^n < r / (1-r)^2, n>=1, 0<r<1

1/2^1 + 2/2^2 + 3/2^3 + ... + n /2^n < 2, n>=1

 

5^n - 1能被4整除

7^n - 1能被6整除

11^n - 6能被5整除

6*7^n - 2*3^n能被4整除

3^n + 7^n - 2能被8整除

 

n条直线能将平面最多划分为(n^2 + n + 2) / 2个区域

定义H(k) = 1 + 1/2 + 1/3 + ... + 1/k 则 1 + n/2 <=H(2^n) <= 1 + n

H(1) + H(2) + ... + H(n) = (n + 1) * H(n) - n

1*H(1) + 2*H(2) + ... + n*H(n) = n*(n + 1) / 2 * H(n + 1) - n * (n + 1) / 4

欧拉函数的定义:E(k)=([1,n-1]中与n互质的整数个数).因为任意正整数都可以唯一表示成如下形式:
k=p1^a1*p2^a2*……*pi^ai;(即分解质因数形式)
可以推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))
               =k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);
               =k*(1-1/p1)*(1-1/p2)....(1-1/pk)

在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值(a为N的质因素)
若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);


若N>2, 欧拉函数E(N)必定是偶数
若gcd(a,b) = 1,则有E(a * b) = E(a) * E(b)

若一个数N分解成p1^a1 * p2^a2 * ... * pn^an，那么
E(N) = p1^(a1 - 1) * (p1 - 1) * ... * pn^(an - 1) * (pn - 1)

若N>1,不大于N且与N互素的所有正整数的和是1/2 * N * E(N)

因子和: 若 k=p1^a1*p2^a2...*pi^ai   F(k) = (p1^0+...+p1^a1)*(p2^0+...+p2^a2)*...*(pi^0 + ... + pi^ai)
 

没有一个平方数是以2,3,7,8结尾的

max{a, b, c} - min{a, b, c} = (|a - b| + |b - c| + |a - c|) / 2

ac % m = bc % m 可以得到 a % m' = b % m'  m' = m / gcd(m, c)

如果a % mi = b % mi (i=1,2,...,n) 并且 l = lcm(m1, m2, ..., mn)  则可以得到 a % l = b % l

Euler 定理
若gcd(a,m)==1, 则a^(phi(m)) % m = 1 % m
Fermat小定理
p为素数，对任意的a有 a^p % p = a % p
p为素数 ，对任意的a(a<p), a^(p-1) % p = 1 % p
p为素数 ， 对任意的a，若gcd(p,a)==1, a^(p-1) % p = 1 % p

一个奇数a的平方减1都是8的倍数

任意4个连续整数的乘积再加上1 一定是完全平方数

当a是整数时，a(a-1)(2a-1)是6的倍数

当a是奇数时,   a(a^2 - 1)是24的倍数

n次代数方程 x^n + a1 * x^(n-1) + ... + an-1*x + an = 0 的系数都是a1, a2, ... , an都是整数。
如果它有有理数的根，证明这个根一定是整数，而且这个数一定是an的因子。如果不是整数，就一定是无理数。


设a,b都是正整数，a<b而gcd(a,b) = 1 ,如果存在一个素数p，它能够整除b，但是不能够整除10，则a/b一定不能够化成有限小数。如果b=2^a * 5^b，其中a,b都是非负整数，则a/b能化成有限小数。

设0<a<b, 且gcd(a,b) = 1, 如果a/b能表示成纯循环小数，则我们有gcd(b, 10) = 1。

设0<a<b, 且gcd(a,b) = 1, 令h是一个最小的正整数，使得10^h 与1 关于b同余，那么a/b可以表示成纯循环小数
0.d1d2d3...dh。

设b是一个正整数且gcd(10, b) = 1，令h是一个最小的正整数，能使得10^h 与1 关于b同余，则h能够整除Euler(b)

设a, b, b1都是正整数，a < b, gcd(a, b) = 1, b1 > 1, gcd(b1, 10) = 1。b = 2^c * 5^d * b1, 其中c， d都是非负整数，且不同时为0， 令h是一个最小的正整数，使得 10^h 与1 关于b1同余, 则当c>=d时，我们有a/b = 0.a1a2...aca'(c+1)...a'(c + h)  ，而当c < d时，我们有a/b = 0.a1a2...ada'(d+1)...a'(d + h)

设0.a1a2...an...不能换成有限小数，也不能化成循环小数，则它不能化成分数。

设p是一个素数，m是一个正整数且m=na+b其中a是一个非负整数而b是一个不大于n-1的非负整数。令
a=p^m, 当b=0的时候，a的开n次方是一个整数，当1<= b <= n - 1时，a的开n次方不能表示为分数。


设p是一个素数，m是一个正整数且m=na+b其中a是一个非负整数而b是一个不大于n-1的非负整数。令
a=p^m, 当b=0的时候，a的开n次方是一个整数，当1<= b <= n - 1时，a的开n次方=b+c, 其中b是一个正整数而c是一个无限小数但不是循环小数。

设a是一个正整数, 当a的开n次方=b+c中b是一个正整数而0<c<1时，则a的开n次方不能表示成为分数，并且这时c是一个无限小数但不是循环小数。


(4b^3 + 3b) / (4b^2 + 1) <= b + 1 / (2b + 1/2b) <=  根号b平方+1 <= b + 1 / (2b + 1/(2b + 1 / 2b)) = (8b^4 + 8b^2 + 1) / (8b^3 + 4b)

b + 1/(2b + 1/(2b + 1/(2b + 1/2b))) <= 根号b平方+1

(16b^5 + 20b^3 + 5b) / (16b^4 + 12b^2 + 1) <= 根号b平方+1 <= (8b^4 + 8b^2 + 1) / (8b^3 + 4b)

 

8*8棋盘2牌的完美覆盖数目为12988816=2^4 * 901^2

 

一张m行n列棋盘有一个b-牌的完美覆盖，当且仅当b是m的一个因子或者b是n的一个因子

 

n阶幻方的幻和为 n*(n^2+1) / 2   n阶幻方体的幻和为(n^4+n) / 2

 

鸽巢原理： 如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或者更多的物体

鸽巢原理加强形式： 令q1，q2，..，qn为正整数。如果将 q1+q2+...+qn-n+1 个物体放入n个盒子内，那么，至少第一个盒子至少含有q1个物体，或者第二个

盒子至少含有q2个物体，... ，或者第n个盒子至少含有qn个物体

 

给定m个整数a1,a2,...,am，存在整数p和q，0<=p<q<=m,使得a(p+1)+a(p+2)+...+a(m)能够被m整除。通俗的说，就是在序列a1,a2,...,am中存在连续

个a，使得这些a的和能被m整除

 

由n^2+1个实数构成的序列a1，a2,...,a(n^2+1)或者含有长度为n+1的递增子序列，或者含有长度为n+1的递减子序列

 

Ramsey定理：在6个（或更多的）人中，或者有3个人，他们中的每两个人都互相认识；或者有3个人，他们中的每两个人都彼此不认识

 

n个元素的集合的循环r-排列的个数由

A(n,r)/r=n!/(r * (n-r)!)给出。特别地，n个元素的循环排列的个数是(n-1)!

 

多重集排列：

令S是一个多重集，有k个不同类型的元素，各元素的重数分别为n1,n2,...,nk。设S的大小为n=n1+n2+...+nk。则S的排列数等于n!/(n1!*n2!*...*nk!)

 

多重集的组合：

令S为具有k中类型元素的一个多重集，每种元素均具有无限的重复数。则S的r-组合的个数等于 C(r+k-1,r)

 

如果排列P1P2...Pn有逆序列b1,b2,...,bn，且k=b1+b2+...+bn为逆序数，那么P1P2...Pn可以通过k次连续交换得到12...n

 

利用反射Gray码生成相邻元组1的个数相差1的所有组合

 

生成{1,2,...,n}的字典序r-组合的算法：

从r-组合a1a2...ar=12..r开始

当a1a2...ar不等于（n-r+1)(n-r+2)...n时,做：

i)确定最大的整数k，是的ak + 1<=n且ak + 1不等于a1,a2,...ar

ii)用r-组合   a1...a(k-1)(ak + 1)(ak+2)...(ak + r - k + 1)替换 a1a2...ar

 

C(n,k)=C(n-1,k)+C(n-1,k-1)  1<=k<=n-1

 

k * C(n,k) = n * C(n-1, k-1)

 

C(n,0)+C(n,1)+...+C(n,n) = 2^n    C(n,0)+C(n,2)+... = 2^(n-1)  C(n,1)+C(n,3)+...=2^(n-1)

 

1*C(n,1)+2*C(n,2)+...+n*C(n,n)=n*2^(n-1) (n>=1)

 

通过对等式 (1+x)^n=sigma(C(n,k)*x^k)  k: 0->n 两边就微分，可以得到 sigma(k^p * C(n,k)) k: 1->n的和

 

sigma(C(n,k)^2) = C(2n,n)  k:  1->n

 

C(r,0)+C(r+1,1)+...+C(r+k,k) = C(r+k+1,k)

 

C(0,k)+C(1,k)+...+C(n-1,k)+C(n,k)=C(n+1,k+1)

 

Dilworth定理：  令(X,<=)是一个有限偏序集，并令m是反链的最大大小。则X可以被划分成m个但不能再少的链

同理， 若r是链的最大大小，那么X可以被划分成r个但不能再少的反链。

 

卷积定理： 对任意两个长度为n的向量a和b，其中n是2的幂，

a,b的卷积等于 (DFT2n)-1(DFT2n(a) . DFT2n(b))

其中向量a和b是用0扩充使其长度达到2n，"."表示2个2n个元素组成的向量的点乘

 

18014398509481931 素数
18014398509482111 最小质因子为11
1637672591771101 最小质因子为6780253

 

中线定理（pappus定理）是指三角形ABC内BM=MC,则AB^2+AC^2=2*(AM^2+BM^2)

证明：
AC^2=AH^2+HC^2?
AB^2=AH^2+BH^2=AH^2+(HC+2MH)^2=AH^2+HC^2+4MH*HC+4MH^2
左边=AB^2+AC^2=2*AH^2+2CH^2+4MH*CH+4MH^2
右边=2*(AM^2+BM^2)=2*(AH^2+MH^2+(CH+MH)^2)=2*(AH^2+MH^2+CH^2+2CH*MH+MH^2)
得证

 

[modified from &豪's blog]
(1)定理:设x0,x1,x2,...是无穷实数列,xj>0,j>=1,那么,
      (i)对任意的整数 n>= 1, r>=1有
            <X0,...,Xn-1,Xn,...,Xn+r> = <X0,...,Xn-1,<Xn,...,Xn+r>>
            =   <X0,...,Xn-1,Xn+1/<Xn+1,...,Xn+r>>.
      特别地有
            <X0,...,Xn-1,Xn,Xn+1> = <X0,...,Xn-1,Xn+1/Xn+1>
      注:用该定理可以求连分数的值

(2)对于连分数数数列 <X0,...Xn> 有递推关系:
      Pn = XnPn-1+Pn-2;
      Qn = XnQn-1+Qn-2;
      定义:  P-2 = 0; P-1 = 1; Q-2 = 1; Q-1 = 0;
      所以:  P0 = X0; Q0 = 1; P1 = X1X0+1; Q1 = X1;
      特别地:当 Xi=1 时, {Pn}, {Qn}为Fbi数列

(3)对于连分数数数列 <X0,...Xn>
     当n>= 1时，我们有PkQk-1 = Pk-1Qk = (-1)^k
     当n>=2时， 我们有PkQk-2 = Pk-2Qk = (-1)^(k - 1) * xk

(4) 所有有理数都可以表示成有限连分数


(5)pell方程: x^2+ny^2=+-1的解法:
      若n是平方数,则无解, 否则:
      先求出sqrt(n)的连分数序列<x0,x1..xn> 其中xn = 2*x0;
      对于 x^2+ny^2=-1
      若n为奇数,则 x=Pn-1, y=Qn-1; n为偶数时无解
      对于 x^2+ny^2=1
      若n为偶数,则 x=Pn-1, y=Qn-1; n为奇数时x=P2n-1, y=Q2n-1
      注:以上说的解均为最小正解

这篇关于一些数论的公式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1114571。

相关文章

数论入门整理（updating）

数论入门整理（updating）

一、gcd lcm 基础中的基础，一般用来处理计算第一步什么的，分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题：
阅读更多...
hdu 4565 推倒公式+矩阵快速幂

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值： Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中： 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令： An=(a+b√)n A_n = (a +
阅读更多...
数论ZOJ 2562

数论ZOJ 2562

题意：给定一个数N，求小于等于N的所有数当中，约数最多的一个数，如果存在多个这样的数，输出其中最大的一个。 分析：反素数定义：对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7
阅读更多...
POJ2247数论

POJ2247数论

p = 2^a*3^b*5^c*7^d 求形如上式的第n小的数。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.u
阅读更多...
CSP-J基础之数学基础 初等数论 一篇搞懂(一)

CSP-J基础之数学基础 初等数论 一篇搞懂(一)

文章目录 前言声明初等数论是什么初等数论历史1. **古代时期**2. **中世纪时期**3. **文艺复兴与近代**4. **现代时期** 整数的整除性约数什么样的整数除什么样的整数才能得到整数？条件：举例说明：一般化： 判断两个数能否被整除 因数与倍数质数与复合数使用开根号法判定质数哥德巴赫猜想最大公因数与辗转相除法计算最大公因数的常用方法：举几个例子：例子 1: 计算 12 和 18
阅读更多...
CSP-J基础之数学基础 初等数论 一篇搞懂(二)

CSP-J基础之数学基础 初等数论 一篇搞懂(二)

文章目录 前言算术基本定理简介什么是质数？举个简单例子：重要的结论：算术基本定理公式解释：举例： 算术基本定理的求法如何找出质因数：举个简单的例子： 重要的步骤：C++实现 同余举个例子：同余的性质简介1. 同余的自反性2. 同余的对称性3. 同余的传递性4. 同余的加法性质5. 同余的乘法性质 推论 总结 前言 在计算机科学和数学中，初等数论是一个重要的基础领域，涉及到整数
阅读更多...
二维旋转公式

二维旋转公式

二维旋转公式 ros的tf工具包可以很方便的实现任意坐标系之间的坐标转换。但是，如果只是想简单的测试想法，而又不想编写过于庞杂的代码，考虑自己写二维旋转的函数。而与二维旋转问题对偶的另一个问题便是二维坐标系旋转变换。这两个问题的形式基本一样，只是旋转的角度相差一个负号。就是这个容易搞混，所以做个笔记，以备查用。 1. 二维旋转公式（算法） 而（此文只针对二维）旋转则是表示某一坐标点 ( x
阅读更多...
word转PDF后mathtype公式乱码以及图片分辨率降低等一系列问题|完美解决

word转PDF后mathtype公式乱码以及图片分辨率降低等一系列问题|完美解决

word转PDF后mathtype公式乱码以及图片分辨率降低等一系列问题|完美解决 问题描述 最近在投一篇期刊论文，直接提交word文档，当时没有查看提交预览，一审审稿意见全是：公式乱码、公式乱码、乱码啊！！！是我大意了，第二次提交，我就决定将word文档转成PDF后再提交，避免再次出现公式乱码的问题。接着问题又来了，我利用‘文件/导出’或‘文件/另存为’的方式将word转成PDF后，发现公式
阅读更多...
不同饭局，如何说开场白才能打开氛围？教你一个万能公式

不同饭局，如何说开场白才能打开氛围？教你一个万能公式

在人情社会中，饭局不仅是吃饱饭的场合，更是人际交往、情感交流的重要平台。无论是家庭聚会、商务宴请、朋友相聚还是同事联谊，一个恰当的开场白都能迅速打破沉默，营造温馨和谐的氛围。 针对现实生活中最常见的四种饭局，酱酒亮哥教你一个万能开场白公式，这个公式分为四步，当然，不是一步不落的照搬，需要灵活应用，挑其中的两步、三步就行了，只要打开氛围，我们的目的也就达到了。接下来我们一起学习一下，希望你在不同的
阅读更多...
【无线通信发展史⑧】测量地球质量？重力加速度g的测量？如何推导单摆周期公式？地球半径R是怎么测量出来的？

【无线通信发展史⑧】测量地球质量？重力加速度g的测量？如何推导单摆周期公式？地球半径R是怎么测量出来的？

前言：用这几个问答形式来解读下我这个系列的来龙去脉。如果大家觉得本篇文章不水的话希望帮忙点赞收藏加关注，你们的鼓舞是我继续更新的动力。 我为什么会写这个系列呢？ 首先肯定是因为我本身就是一名从业通信者，想着更加了解自己专业的知识，所以更想着从头开始了解通信的来源以及在每一个时代的发展进程。 为什么会从头开始写通信？ 我最早是学习了中华上下五千年，应该说朝代史，这个算个人兴趣，从夏
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2