文章目录
  1. 1. 原题
  2. 2. 分析
    1. 2.1. 共轭实数
    2. 2.2. 证明它们的n次方和是整数
    3. 2.3. 扩展-Fibonacci数
    4. 2.4. |√p-√q|< 1
  3. 3. 解题
    1. 3.1. 代码
  4. 4. 小结:

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.

分析

题中的(√2+√3)2就是一个Pisot数,它具有这个特点:
当n趋向无穷大的时候,它的n次方趋向一个整数,而它的共轭实数(√2-√3)2的n次方趋向0。而且这两个n次方数相加是一个整数。

共轭实数

形如a+b√m和a-b√m的两个实数,叫做共轭实数。

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

对于p和q:
(√p+√q)2n = (p+q+2√pq)2n,
(√p-√q)2n = (p+q-2√pq)2n,
设a = p+q,b = 2√pq,
(这里a+b与a-b是共轭实数,它们的小数部分相加等于1,现在证明它们的任意n次方和是整数)

(√p+√q)2n + (p+q-2√pq)2n = (a+b)n+(a-b)n,其中a是整数,b是实数,
根据二项式展开式可知,所有展开项中,b为偶数次方的都同号,b为奇数次方的都不同号(从而相减消除了),而b的偶数次方是整数,所以展开项相加也是整数。

扩展-Fibonacci数

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

|√p-√q|< 1

还有一个关键条件,就是必须满足|√p-√q|< 1,即(a-b)<1 才是上面几个结论成立的关键,也是解答本题的关键(证明还没有找到)。

解题

为了使(√p+√q)2n的小数有2011或更多的9,那么(√p-√q)2n的小数就必须具有2011或更多的0(就是非常接近0),从而:
$$(\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)})$$

于是,只需要循环p和q,寻找满足条件的 (a-b)<1 的p、q对,然后计算n,并相加即可。

代码

public static void main(String[] args) {
long t = System.nanoTime();
long s = 0;
int L = 2011;
for (int p = 1; p < L; p++) {
for (int q = p + 1; q < L - p + 1; q++) {
double c = p + q - 2 * Math.sqrt(p * q);
if (c < 1) {// 等价于 (√q-√p) < 1
s += Math.ceil(-L / Math.log10(c));
}
}
}
System.out.println(s);
System.out.println("Time consumed "
+ TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - t) + " ms");
}

输出:

709313889
Time consumed 22 ms

小结:

参考1
参考2-NickMcG
Pisot–Vijayaraghavan_number

文章目录
  1. 1. 原题
  2. 2. 分析
    1. 2.1. 共轭实数
    2. 2.2. 证明它们的n次方和是整数
    3. 2.3. 扩展-Fibonacci数
    4. 2.4. |√p-√q|< 1
  3. 3. 解题
    1. 3.1. 代码
  4. 4. 小结: