投稿

Eulerian trail

イメージ
You need to go back the start point in Eulerian trail. You can go through the path once. This is closed . Each edge has even links.

Perfect number

イメージ
A perfect number is a number that is half the sum of all of its positive divisors, and it is including itself. σ(N)=2N 28 is the perfect number. 28=1 + 2 + 4 + 7 + 14 σ(28)=1 + 2 + 4 + 7 + 14 + 28 = 2*28 = 56 Euler proved that all even perfect numbers were in the Euclid–Euler theorem. The sum of divisors of a number must include the number itself, not just the proper divisors. σ(2^2(2^3-1))=σ(4)σ(7)=(1+2+4)(1+7)=7*8=56=σ(28) This is known as Mersenne primes. 2(2^2-1)=6 2^2(2^3-1)=28 2^4(2^5-1)=496 These are perfect numbers. 3,7,31 are primes, so you can find perfect numbers infinitely because of fractal . However, odd perfect numbers are unknown.

Amicable numbers

The smallest pair of amicable numbers is (220, 284). You expand it infinitely. M and N are amicable. σ(M) is the sum of proper divisors. σ(220)=1+2+4+5+10+11+20+22+44+55+110+220=504. Moreover, σ(N)=σ(284)=1+2+4+71+142+284=504. σ(M)-M=N and σ(N)-N=M In this case, M=220 and N=284. σ(220)-220=504-220=284 σ(284)-284=504-284=220 ∴ σ(M)=M+N=σ(N) This is crossing over. M=apq, N=ar pqr are different prime numbers, and a is the prime relatively. Leonhard Euler found it. σ(p)=p+1, p is the prime. σ(pq)=σ(p)σ(q)=1+p+q+pq=(1+p)+q(1+p)=(1+p)(1+q), p and q are prime numbers. Therefore, σ(M)=σ(N), σ(apq)=σ(ar) σ(a)σ(p)σ(q)=σ(a)σ(r) σ(p)σ(q)=σ(r) ∴ (p+1)(q+1)=r+1 This is based on prime numbers. Then, you put x=p+1, y=q+1 . xy=r+1, r=xy-1 σ(M)=M+N=apq+ar=a(pq+r) σ(M)=σ(a)σ(p)σ(q)=σ(a)(p+1)(q+1)=a(pq+r) σ(a)xy=a[(x-1)(y-1)+(xy-1)] ax=[2ax-σ(a)x-a]y y=ax/[2ax-σ(a)x-a] Then, you put a/[2a-σ(a)]=b/c . 2a-σ(a)=ac/b, σ(a)=2a-(ac/b) ∴ y=ax/[(ac/b)x-a]=bx/(cx-...

Euler's formula

イメージ
Euler's formula is based on Maclaurin's expansion . The sine function (blue) is closely approximated by its Taylor polynomial of degree 7 (pink) for a full period centered at the origin. x is 0, so f(x)=(sin x,cos x,-sin x,-cos x,・・・)=(0,1,0,-1,・・・)=sin x and f(x)=(cos x,-sin x,-cos x,sin x,・・・)=(1,0,-1,0,・・・)=cos x Euler's identity is well known as the beauty of mathematics.

Streaming algorithm

イメージ
This is the process of data streaming with less memory. x∈R^n This is high dimensional vector. You update it. xi←xi+v You have O(n) space, and the whole stream is O(m). You compress the data by streaming . A=(1±ε)B (1-ε)B≦A≦(1+ε)B ∴ σi,j = ±1, E[σi,j] = 0

Zeta transform

イメージ
This is Inclusion-Exclusion . Then, this is the Zeta transform. Moreover, this is the inversion. You prove this. At first, you use the Zeta transform. You put the inversion. You remove the gray area. You divide S and R. This is Inclusion-Exclusion. You got f(R). Therefore, the Zeta transform is feasible.

Exponential Divide and Conquer

イメージ
OPT(U,s,t) is the length of s and t , and you choose the cheapest. You split the path into two halves in all possible ways. This is called Exponential Divide and Conquer. m is an intermediate point. |S|=||U|/2|+1 T∪S=U T∩S=m n is nodes . ∴ ε>0 The exponential space is huge.