EulerProject

# P131: 素数立方数组合

Prime cube partnership

对于某些素数 , 存在正整数 , 使得表达式 是立方数.

例如, 对于 , .

非常奇特的是, 对于满足这个性质的素数, 的值都是唯一的. 在小于一百的素数中, 只有四个素数满足这个性质.

在小于一百万的素数中, 有多少个素数满足这个神奇的性质?

考虑 , 当 和 都为立方数, 这两个立方数相减的差就是一个素数

又因为 , 所以只有当 时, 才可能是一个素数.

所以只需要检查相邻的 个立方数之差是否是素数就可以了.

也就是说只需要检查 是否是素数就可以了, 然后范围可以再限定到 以下:

Length@Select[3 #^2 + 3 # + 1& /@ Range[576], PrimeQ]
  • 计时: 4:17.33

# P132: 大循环单位数的因数

Large repunit factors

只包含数字 的数被称为循环单位数, 我们定义 是长为 的循环单位数.

例如, , 这些质因数的和是 .

找出 的前 个质因数的和.

找前几个因数, 那就是试除法, 但也不可能去除这么大的数啊.

所以, 取模呗, 这题考的还是快速幂模.

注意从 开始, 扔了 

ct = 40;st = 10;n = 1*^9;
try = (PowerMod[10, n, #] - 1) / 9&;
do = Reap@While[ct > 0, If[try[st] == 0, Sow[st];ct--];st = NextPrime[st]];
Total@Rest[Flatten@do]

唔, 要是你说这样不够函数式的话, 也不是不能用递归解法, 这样还快一个数量级.

$IterationLimit = 2^15;
sf[n_, 0, p_] := 0;
sf[n_, m_, p_] := If[PowerMod[10, n, 9 * Prime[p]] == 1, Prime[p] + sf[n, m - 1, p + 1], sf[n, m, p + 1]];
sf[10^9, 40, 1]
  • 计时: 10:47.95

# P133: 循环单位数的非质因数

Repunit nonfactors

只包含数字 的数被称为循环单位数, 我们定义 是长为 的循环单位数;

例如, .

考虑形如 的循环单位数.

尽管 都不能被 整除, 却能够被 整除.

然而, 不存在 使得 能被 整除.

事实上, 在小于 的质数中, 只有 和 能够成为 的质因数.

找出所有小于十万且永远不会成为 的质因数的质数之和.

上一题是水题, 这题就触及核心问题了

实在搞不懂的话搞个 的上界然后还是试除也能过

Reap@For[i = 1, (p = Prime[i]) <= 10^5, i++, If[p == 2 || p == 5 || Mod[(PowerMod[10, 10^20, 9p] - 1) / 9, p] != 0, Sow@p]] // Flatten // Rest // Total

不要这么暴力的解法就麻烦了.

首先定义 乘法阶数:

若 互素 , 定义集合

那么将集合 中的最小正数称为 的阶, 且 仅由阶的整数倍组成.

比如说:

Table[MultiplicativeOrder[10, 9 Prime[n]], {n, PrimePi[100]}] MultiplicativeOrder[10, 9 #] & /@ {11, 17, 41, 73}

所以呢:

Q[2 | 5] := True
Q[n_] := ! MatchQ[FactorInteger[MultiplicativeOrder[10, 9n]], {{2 | 5, _} ...}]
Select[Prime@Range@PrimePi@1*^5, Q] // Total
  • 计时: 19:41.30

# P134: 质数对连接

TIP

考虑连续的质数 .

可以验证, 是所有以 结尾并且能被 整除的数中最小的一个.

事实上, 除了 这一对之外, 对于任意一对连续质数 , 都存在一系列的数 , 其尾数是 , 且能够被 整除.

记 是所有的 中的最小值.

对于 内的所有连续质数对, 求 .

阅读理解, 算呗

S[{p1_, p2_}] := Block[{n = 10^(Floor@Log[10, p1] + 1)}, Mod[-PowerMod[n, -1, p2]p1, p2]n + p1];
S /@ Partition[Prime@Range[3, PrimePi[1*^6] + 1], 2, 1] // Total
  • 12:41

# P135: 相同的差

Same differences

已知正整数 构成等差数列, 使得方程 有两个解的最小正整数为 :

使得方程有十个解的最小正整数为 .

在小于一百万的数中, 有多少个 的取值使得方程恰好有十个不同的解?

说明 是 的因数, 且满足: 

For[n = 1;count = 0, n <= 1000000, n++,
    i = Select[Divisors[n], # < Sqrt[3 n]&];
    i = Mod[i + n / i, 4];
    If[Count[i, 0] == 10, count++;];
];
count

太慢了, 可以优化下:

limit = 1000000;
solutions = ConstantArray[0, limit];
Do[
    v = Floor[u / 3] + 1;
    While[u v <= limit, If[Mod[u + v, 4] == 0 && Mod[3 v - u, 4] == 0 && (3 v > u), solutions[[u v]] += 1;v += 4 , v += 1]],
    {u, 1, limit}
];
Count[solutions, 10]
  • 20:04

# P136: 唯一的差

Singleton difference

正整数 构成等差数列. 取正整数 , 此时方程 只有一个解:

事实上, 在小于一百的数中, 有 个 的取值使得方程有唯一解.

在小于五千万的数中, 有多少个 的取值使得方程有唯一解?

傻乎乎的用上题魔改就完啦.

其实这题反而简单, 有唯一解, 也就是 唯一.

只有以下三种情况:

  • 且 
n = 50000000;
Count[Prime@Range@PrimePi@n, x_ /; Mod[x, 4] == 3] + PrimePi[n / 4] + PrimePi[n / 16]
  • 7:29

# P137: 斐波那契金块

Fibonacci golden nuggets

考虑无穷级数 其中 是斐波那契数列的第 k 项.

该数列由如下方式定义:, 其中 .

在这个问题中, 我们感兴趣的是那些使得 为正整数的 x.

其中一个特别的解是:

\begin{aligned} A_F\left(\frac{1}{2}\right) &= \frac{1}{2}\times 1 + \frac{1}{2^2}\times 1 + \frac{1}{2^3}\times 2 + \frac{1}{2^4}\times 3 + \frac{1}{2^5}\times 5 + \cdots \\ &= \frac{1}{2} + \frac{1}{4} + \frac{2}{8} + \frac{3}{16} + \frac{5}{32} + \cdots \\ &= 2 \end{aligned}

对应于前五个自然数的 如下所示.

当 是有理数时, 我们称 是一个斐波那契金块, 因为这样的数将会变得越来越稀少.

例如, 第 个斐波那契金块将是 .

求第 个斐波那契金块.

这不就生成函数吗, 斐波那契数列的生成函数是:

令 , 解二次方程解得:

所以只要里面的是平方数就行了咯

然后就是数论题了, 解出来的话会是:

p(n)=\left\{\begin{aligned} &\frac{1}{10} \left(\left(\sqrt{5}+1\right) \left(4 \sqrt{5}+9\right)^{2 k}-\left(9-4 \sqrt{5}\right)^{2 k} \left(\sqrt{5}-1\right)-2\right) \\ &\frac{1}{5} \left(\left(\sqrt{5}-2\right) \left(4 \sqrt{5}+9\right)^{2 k}-\left(9-4 \sqrt{5}\right)^{2 k} \left(\sqrt{5}+2\right)-1\right) \\ &\frac{1}{10} \left(\left(5 \sqrt{5}+11\right) \left(4 \sqrt{5}+9\right)^{2 k}+\left(9-4 \sqrt{5}\right)^{2 k} \left(11-5 \sqrt{5}\right)-2\right) \\ \end{aligned}\right.,n\in\mathbb{Z}_+

注意少了个 2, 所以要减掉一位

Sum[x^i Fibonacci[i], {i, Infinity}]
Solve[{x / (1 - x - x^2) == n, x > 0, n > 0}, x]
sol = n /. Solve[{1 + 2 n + 5 n^2 == p^2, n > 0, p >= 0}, {n, p}, Integers]
tb = Table[Evaluate[sol /. ConditionalExpression[a_, __] -> a /. C[1] -> k], {k, 10}];
Sort[Append[Flatten@tb, 2] // FullSimplify][[15]]

难度应该都在各种解方程上, 但是 sorry, 数学软件就是可以为所欲为.

  • 计时: 6:43.13

# P138: 特殊等腰三角形

TIP

考虑底为 , 腰为 的等腰三角形.

使用毕达哥拉斯定理, 我们可以求出三角形的高是 , 恰好比底长小 1.

当 而 $L = 305 时 $, 可以算出 , 恰好比底长大 1, 而且这是满足性质 h = b ± 1 的三角形中第二小的.

对于最小的 12 个满足 且 b, L 均为正整数的等腰三角形, 求 .

# P139: 毕达哥拉斯地砖

TIP

用 表示边长为整数的直角三角形的三边, 可以将四个这样的三角形放在一起, 使其外框构成边长为 c 的正方形.

例如, 边长为 的三角形可以构成一个 的正方形, 中间留有一个 的洞. 而这个 的正方形又恰好可以用 25 个 的小正方形组成.

然而, 如果我们用 的三角形, 则中间的洞将会是 大小, 不能用来组成 的大正方形.

考虑边长小于一亿的直角三角形, 有多少个毕达哥拉斯三角形可以用中间留下的空洞大小的地砖恰好铺满外围的大正方形?

# P140: 修正斐波那契金块

Modified Fibonacci golden nuggets

考虑无穷级数

其中 是二阶递归关系 的第 k 项

其中 , 该序列为

在这个问题中, 我们感兴趣的是那些使得 为正整数的 .

对应于前五个自然数的 如下所示.

当 是有理数时, 我们称 是一个修正斐波那契金块, 因为这样的数将会变得越来越稀少.

例如, 第 个修正斐波那契金块将是 .

求前 个修正斐波那契金块的和.

其实和 P137 没有任何区别

gk = RSolveValue[{g[k] == g[k - 1] + g[k - 2], g[1] == 1, g[2] == 4}, g[k], k]
fx = Sum[x^k gk, {k, Infinity}]
Solve[{fx == n, x > 0, n > 0}, x]
sol = n /. Solve[{1 + 14 n + 5 n^2 == p^2, n >= 1, p > 0}, {n, p}, Integers]
tb = Table[Evaluate[sol /. ConditionalExpression[a_, __] -> a /. C[1] -> k], {k, 20}];
add = Flatten[Position[Head /@ FullSimplify[Table[ Sqrt[(1 + 14 * n + 5 * n^2) / (3 + n)^2], {n, 151}]], Rational]];
Sort[Join[Flatten@tb, add] // FullSimplify][[1 ;; 30]] // Total

反正结果的话比原来更暴力一点点:

p(n)=\left\{\begin{aligned} &\frac{1}{10} \left(\left(\sqrt{5}+7\right) \left(4 \sqrt{5}+9\right)^{2 n}-\left(9-4 \sqrt{5}\right)^{2 n} \left(\sqrt{5}-7\right)-14\right) \\ &\frac{1}{10} \left(-\left(\sqrt{5}-7\right) \left(4 \sqrt{5}+9\right)^{2 n}+\left(\sqrt{5}+7\right) \left(9-4 \sqrt{5}\right)^{2 n}-14\right) \\ &\frac{1}{10} \left(\left(97 \sqrt{5}+217\right) \left(4 \sqrt{5}+9\right)^{2 n}+\left(9-4 \sqrt{5}\right)^{2 n} \left(217-97 \sqrt{5}\right)-14\right) \\ &\frac{1}{10} \left(\left(7 \sqrt{5}+17\right) \left(4 \sqrt{5}+9\right)^{2 n}+\left(9-4 \sqrt{5}\right)^{2 n} \left(17-7 \sqrt{5}\right)-14\right) \\ &\frac{1}{5} \left(\left(25 \sqrt{5}+56\right) \left(4 \sqrt{5}+9\right)^{2 n}+\left(9-4 \sqrt{5}\right)^{2 n} \left(56-25 \sqrt{5}\right)-7\right) \\ &\frac{1}{5} \left(\left(7 \sqrt{5}+16\right) \left(4 \sqrt{5}+9\right)^{2 n}+\left(9-4 \sqrt{5}\right)^{2 n} \left(16-7 \sqrt{5}\right)-7\right) \\ \end{aligned}\right.,n\in\mathbb{Z}_+

话说怎么判定缺少的有理数我还想了半天, 一时半会儿想不起这个函数了...

你要说如果不这么无赖能不能解呢?

当然可以啊, 不就佩尔方程吗, 我们知道佩尔方程可以用连分展开解决.

也就是说可以化为一个矩阵型, 进一步的我们可以写出其线性形式.

P137 = LinearRecurrence[{8, -8, 1}, {2, 15, 104}, 15] // Last
P138 = LinearRecurrence[{18, -1}, {17, 305}, 12] // Total
P140 = LinearRecurrence[{1, 7, -7, -1, 1}, {2, 5, 21, 42, 152}, 30] //Total
  • 计时: 2:24.16

← Level141-150 →