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/(2*4)+1*3/(2*4*6)+1*3*5/(2*4*6*8)+...+(1*3*5*...*(2n-1))/(2*4*6*...*(2n+2)) = 1/2 - (1*3*5*...*(2n+1))/

(2*4*6*...*(2n+2))

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

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

(a(1)*a(2)*...*a(2^n))^(1/2^n) <= (a(1) + a(2) + ... + a(2^n)) / 2^n, n = 1, 2, ... a(i)是正数 注:()用来标记下标

cos(x) + cos(2x) + ... + cos(nx) = cos((x/2)*(n+1))*sin(nx/2) / sin(x/2), 其中sin(x/2) != 0

1*sin(x) + 2*sin(2x) + ... + n*sin(nx) = sin((n+1)*x) / (4*sin(x/2)^2) - (n+1)cos((2n + 1)/2 * x) / (2 * sin(x/2))

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个区域

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

k=p1^a1*p2^a2*……*pi^ai;(即分解质因数形式)

=k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);
=k*(1-1/p1)*(1-1/p2)....(1-1/pk)

E(N) = p1^(a1 - 1) * (p1 - 1) * ... * pn^(an - 1) * (pn - 1)

没有一个平方数是以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)

Euler 定理

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

n次代数方程 x^n + a1 * x^(n-1) + ... + an-1*x + an = 0 的系数都是a1, a2, ... , an都是整数。

0.d1d2d3...dh。

a=p^m, 当b=0的时候，a的开n次方是一个整数，当1<= b <= n - 1时，a的开n次方不能表示为分数。

a=p^m, 当b=0的时候，a的开n次方是一个整数，当1<= b <= n - 1时，a的开n次方=b+c, 其中b是一个正整数而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

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

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

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

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

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)

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个但不能再少的链

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

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

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

[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
注:以上说的解均为最小正解