Project Euler Problem 318 - 涉及二项式分解、接近整数、Pisot数等数学知识 ,Completed on 2015-10-10 15:00

## 原题

Consider the real number √2+√3.
When we calculate the even powers of √2+√3 we get:
(√2+√3)2 = 9.898979485566356…
(√2+√3)4 = 97.98979485566356…
(√2+√3)6 = 969.998969071069263…
(√2+√3)8 = 9601.99989585502907…
(√2+√3)10 = 95049.999989479221…
(√2+√3)11 = 940897.9999989371855…
(√2+√3)14 = 9313929.99999989263…
(√2+√3)16 = 92198401.99999998915…

It looks like that the number of consecutive nines at the beginning of the fractional part of these powers is non-decreasing.
In fact it can be proven that the fractional part of (√2+√3)2n approaches 1 for large n.

Consider all real numbers of the form √p+√q with p and q positive integers and p<q, such that the fractional part of (√p+√q)2n approaches 1 for large n.

Let C(p,q,n) be the number of consecutive nines at the beginning of the f于actional part of
(√p+√q)2n = (p+q+2.√pq)2n,
(√p+√q)2n = (p+q+2.√pq)2n,

Let N(p,q) be the minimal value of n such that C(p,q,n) ≥ 2011.

Find ∑N(p,q) for p+q ≤ 2011.

## 分析

### 证明它们的n次方和是整数

(√p+√q)2n = (p+q+2√pq)2n,
(√p-√q)2n = (p+q-2√pq)2n,

（这里a+b与a-b是共轭实数，它们的小数部分相加等于1，现在证明它们的任意n次方和是整数）

(√p+√q)2n + (p+q-2√pq)2n = (a+b)n+(a-b)n,其中a是整数，b是实数，

### 扩展-Fibonacci数

Fibonacci数就是两个共轭实数的n次方和：
$$a_n = A \left( { \frac {1 + \sqrt 5} 2 } \right) ^ n + B \left( { \frac {1 - \sqrt 5} 2 } \right) ^ n.$$

## 解题

$$(\sqrt p - \sqrt q)^{2n} \le 10 ^{-2011}$$

$$n \ge \frac{-2011}{2\lg(\sqrt q -\sqrt p)}$$

n取最小值：
$$n = ceil(\frac{-2011}{2\lg(\sqrt q -\sqrt p)})$$