P61: 循环的多边形数

# P61: 循环的多边形数

Cyclical figurate numbers

三角形数, 正方形数, 五边形数, 六边形数, 七边形数和八边形数统称为多边形数.

它们分别由如下的公式给出:

Name	Formula	Terms
三角形数
正方形数
五边形数
六边形数
七边形数
八边形数

由三个位数构成的有序集有如下三个有趣的性质.

这个集合是循环的, 每个数的后两位是后一个数的前两位, 最后一个数的后两位也是第一个数的前两位.

每种多边形数——三角形数 , 正方形数 . 五边形数 ——在其中各有一个代表.

这是唯一一个满足上述性质的位数有序集.

存在唯一一个包含六个位数的有序循环集, 每种多边形数——三角形数, 正方形数, 五边形数, 六边形数, 七边形数和八边形数——在其中各有一个代表.

求这个集合的元素和.

有内置多边形数 PolygonalNumber, 不用定义一堆函数了.

就算没有内置那手推一下也不是很难的事

感觉四位数也不是很多的样子, 先全部生成一下好了, 结果绑定为 data.

AA00 这种可以先删了.

data = Select[#, 1000 <= # <10000 && Mod[#, 100] > 10 &] & /@ Table[PolygonalNumber[x, y], {x, 3, 8}, {y, 1, 200}]

这次我们不用 IntegerQ 这种坑爹货色检测是否是角型数了, 我们用相对没这么坑的 MemberQ.

大概就是这么个过程:

data[[1]]
Select[data[[2]],MemberQ[Mod[%,100],Floor[#/100]]&]
Select[data[[3]],MemberQ[Mod[%,100],Floor[#/100]]&]
Select[data[[4]],MemberQ[Mod[%,100],Floor[#/100]]&]
Select[data[[5]],MemberQ[Mod[%,100],Floor[#/100]]&]
Select[data[[6]],MemberQ[Mod[%,100],Floor[#/100]]&]

我们找到了这组数中的一个头 1281, 但是这样绝对会被我大函数式玩家直接打死......

循环写法不用我教了吧, 我就教下迭代写法....

用一个列表 {n, list} 储存结果. 然后就是我们把上面一堆打包成一个纯函数.

fooQ[list_,n_]:=Select[data[[n]],MemberQ[Mod[list,100],Floor[#/100]]&]

上面的过程就可以简写为:

fooQ[fooQ[fooQ[fooQ[fooQ[data[[1]], 2], 3], 4], 5], 6]

也就是 Fold[fooQ, data[[1]], Range[2, 6]].

Ok 合起来:

data = Select[#, 1*^3 <= # < 1*^4 && Mod[#, 100] > 10&]& /@ Table[PolygonalNumber[x, y], {x, 3, 8}, {y, 1, 200}];
path = Join[#, {1}]& /@ Permutations[Range[2, 6]];
data = Select[#, 1*^3 <= # < 1*^4 && Mod[#, 100] > 10&]& /@ Table[PolygonalNumber[x, y], {x, 3, 8}, {y, 1, 200}];
fooQ[list_, n_] := Select[data[[n]], MemberQ[Mod[list, 100], Floor[# / 100]]&];
FoldList[fooQ, data[[1]], {2, 3, 4, 5, 6, 1}]

# P62: 立方数重排

Cubic permutations

立方数可以重排为另外两个立方数: 和 .

实际上, 是重排中恰好有三个立方数的最小立方数.

求重排中恰好有五个立方数的最小立方数.

找个范围开始算, 算完直接 GatherBy 按各位数的字典序分类, 分完直接选长度为的就行了.

Min@Select[GatherBy[Range[1*^4]^3, Sort@IntegerDigits@#&], Length@# == 5&]

# P63: 幂次与位数

Powerful digit counts

五位数同时也是一个五次幂.

同样的, 九位数同时也是九次幂.

有多少个位正整数同时也是次幂?

其实只有一点点可能性, 用穷举都抬举这题

$$\begin{gathered} 10^{n - 1} - 1 < a^n < 10^n\ \left\lceil \sqrt[n]{10^{n - 1} - 1} \right\rceil \leqslant a < 10,a \in N\ \sqrt[n]{10^{n - 1} - 1} < 9 \Rightarrow n < 21.85\ \end{gathered} $$

Total@Table[10 - Ceiling[10^((n - 1) / n)], {n, 1, 21}]

# P64: 奇周期平方根

Odd period square roots

所有的平方根写成如下连分数表示时都是周期性重复的:

例如, 让我们考虑√23:

如果我们继续这个过程, 我们会得到如下的展开:

这个过程可以总结如下:

\begin{aligned} a_0&=4\text{:}\quad\cfrac{1}{\sqrt{23}-4}=\cfrac{\sqrt{23}+4}{7}&=1+\cfrac{\sqrt{23}-3}{7}\\ a_1&=1\text{:}\quad\cfrac{7}{\sqrt{23}-3}=\cfrac{7(\sqrt{23}+3)}{14}&=3+\cfrac{\sqrt{23}-3}{2}\\ a_2&=2\text{:}\quad\cfrac{2}{\sqrt{23}-3}=\cfrac{2(\sqrt{23}+3)}{14}&=1+\cfrac{\sqrt{23}-4}{7}\\ a_3&=1\text{:}\quad\cfrac{7}{\sqrt{23}-4}=\cfrac{7(\sqrt{23}+4)}{7}&=8+\sqrt{23}-4\\ a_4&=8\text{:}\quad\cfrac{1}{\sqrt{23}-4}=\cfrac{\sqrt{23}+4}{7}&=1+\cfrac{\sqrt{23}-3}{7} \end{aligned}

可以看出序列正在重复. 我们将其简记为√23 = [4;(1,3,1,8)], 表示在此之后 (1,3,1,8) 无限循环.

前 10 个 (无理数) 平方根的连分数表示是:

√2=[1;(2)], 周期 = 1 √3=[1;(1,2)], 周期 = 2 √5=[2;(4)], 周期 = 1 √6=[2;(2,4)], 周期 = 2 √7=[2;(1,1,1,4)], 周期 = 4 √8=[2;(1,4)], 周期 = 2 √10=[3;(6)], 周期 = 1 √11=[3;(3,6)], 周期 = 2 √12= [3;(2,6)], 周期 = 2 √13=[3;(1,1,1,1,6)], 周期 = 5

在中, 恰好有个连分数表示的周期是奇数.

在中, 有多少个连分数表示的周期是奇数?

有内置函数, 而且量级这么小... 穷举水过....

想了想要是按照他给的这种方法自己写一个还是很难的...

说个关于语法的重要提示, 书写连分数表达式时, 要使用 \cfrac 代替 \frac 或者 \over.

不然你的公式就会挤一起特难看...

Count[Table[Length@Level[ContinuedFraction[Sqrt@n], {2}], {n, 1*^4}], _?OddQ]

# P65: e 的有理逼近

Convergents of e

可以证明, 截取算术平方根连分数表示的一部分所组成的序列, 给出了一系列最佳有理逼近值. 让我们来考虑√2 的逼近值:

\begin{aligned} 1+\cfrac{1}{2}&=\cfrac{3}{2}\\ 1+\cfrac{1}{2+\cfrac{1}{2}}&=\cfrac{7}{5}\\ 1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2}}}&=\cfrac{17}{12}\\ 1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2}}}}&=\cfrac{41}{29} \end{aligned}

因此√2 的前十个逼近值为:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, …

最令人惊讶的莫过于重要的数学常数 e 有如下连分数表示 e = [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …].

e 的前十个逼近值为:

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, …

第 10 个逼近值的分子各位数字之和为 1+4+5+7=17.

求 e 的第 100 个逼近值的分子各位数字之和.

内置函数 ContinuedFraction 水过......

Total@IntegerDigits@Numerator@FromContinuedFraction@ContinuedFraction[E,100]

# P66: 丢番图方程

Diophantine equation

考虑如下形式的二次丢番图方程:

举例而言, 当时, 的最小值出现在 .

可以断定, 当是平方数时, 这个方程不存在正整数解.

对于分别求出取最小值的解, 我们得到:

因此, 对于所有 , 当时的最小值最大.

对于 , 求使得的最小值最大的值.

佩尔方程啊, 这个其实和根号的连分逼近有关, 第一个满足方程的分式正好能给出这个最小的 x.

不过既然有内置的 FindInstance 我就懒得写了, 慢就慢吧, 毕竟我现在在刷题, 算法效率排在解题总时间后面.....

可以看下 tutorial/DiophantineReduce 了解各种丢番图方程的具体解题原理

foo = (x /. FindInstance[x^2 - # y^2 == 1 && x > 0 && y > 0, {x, y}, Integers])[[1]]&;
Last@Ordering[foo /@ (Range[1000] /. a_ /; IntegerQ[Sqrt[a]] -> 2)]

# P67: 最大路径和 II

Maximum path sum II

在这个 15K 的文本文件 triangle.txt 中包含了一个一百行的三角形, 求从其顶端出发到达底部, 所能够得到的最大路径和.

这是第 18 题的强化版. 由于总路径一共有 299 条, 穷举每条路经来解决这个问题是不可能的！即使你每秒钟能够检查一万亿 (1012) 条路径, 全部检查完也需要两千万年. 存在一个非常高效的算法能解决这个问题.

复制粘贴 18 题的代码:

input=URLExecute["https://projecteuler.net/project/resources/p067_triangle.txt","Table"];
state={PadLeft[#1,Length@#1+1]+#2,PadRight[#1,Length@#1+1]+#2}&;
choose[a_,b_]:=Max@@@Transpose@state[a,b];
Max@FoldPair[{choose[#1,#2],choose[#1,#2]}&,input]

# P68: 魔力五边形环

Magic 5-gon ring

考虑下面这个 "魔力" 三角形环, 在其中填入 1 至 6 这 6 个数, 每条线上的三个数加起来都是 9.

从最外侧结点所填的数最小的线 (在这个例子中是 4,3,2) 开始, 按顺时针方向, 每个解都能被唯一表述. 例如, 上面这个解可以记作解集: 4,3,2; 6,2,1; 5,1,3.

将环填满后, 每条线上的总和一共有四种可能: 9, 10, 11 和 12. 总共有 8 种填法:

总和解集 9 4,2,3; 5,3,1; 6,1,2 9 4,3,2; 6,2,1; 5,1,3 10 2,3,5; 4,5,1; 6,1,3 10 2,5,3; 6,3,1; 4,1,5 11 1,4,6; 3,6,2; 5,2,4 11 1,6,4; 5,4,2; 3,2,6 12 1,5,6; 2,6,4; 3,4,5 12 1,6,5; 3,5,4; 2,4,6 把解集中的数字连接起来, 可以构造一个 9 位数字串; 对于三角形环来说, 最大的数字串是 432621513.

在如下的 "魔力" 五边形环中, 在其中填入 1 至 10 这 10 个数, 根据不同的填写方式, 可以组成 16 位或 17 位数字串. 在 "魔力" 五边形环中, 最大的 16 位数字串是多少?

本题未计时, 我会告诉你我是手填的吗...

# P69: 欧拉总计函数与最大值

Totient maximum

在小于 n 的数中, 与 n 互质的数的数目记为欧拉总计函数φ(n)(有时也称为φ函数). 例如, 因为 1, 2, 4, 5, 7 和 8 均小于 9 且与 9 互质, 故φ(9)=6.

n 互质的数 φ(n) n/φ(n) 2 1 1 2 3 1,2 2 1.5 4 1,3 2 2 5 1,2,3,4 4 1.25 6 1,5 2 3 7 1,2,3,4,5,6 6 1.1666… 8 1,3,5,7 4 2 9 1,2,4,5,7,8 6 1.5 10 1,3,7,9 4 2.5 可以看出, 对于 n ⩽ 10, 当 n=6 时 n/φ(n) 取得最大值.

当 n ⩽ 1,000,000 时, 求使得 n/φ(n) 取得最大值的 n.

有内置函数, 百万量级, 不如穷举...

Last@Ordering@ParallelTable[n/EulerPhi[n],{n,1*^6}]

# P70: 欧拉总计函数与重排

Totient permutation

在小于的数中, 与互质的数的数目记为欧拉总计函数 $φ$ .

例如, 因为均小于且与互质, 故 $φ$ .

被认为和任意正整数互质, 所以 $φ$ .

有趣的是, $φ$ , 而恰好是的一个重排.

在中, 有些满足 $φ$ 是的一个重排, 求这些取值中使 $φ$ 最小的一个.

好吧这题上千万了, 穷举有点亏, 分析一下.

\begin{aligned} \phi (n) &= n\prod\limits_{p|n} {(1 - \frac{1}{p})}\\ \frac{n}{\phi (n)} &= \prod\limits_{p|n} {\frac{p}{p - 1}}\\ \end{aligned}

所以要让这个比较小取素数不就行了.

Are you kidding me?

你觉得和居然能由相同的数字组成?

所以最少就就是两个素数之积了, 千万以内 66 万素数两两组合有 2200 亿种, 狗带....

\begin{aligned} \varphi (p_1 p_2) &= p_1 p_2(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) \\ &= (p_1 - 1)(p_2 - 1) \\ \frac{n}{\varphi (n)} &= \frac{p_1 p_2}{(p_1 - 1)(p_2 - 1)} \end{aligned}

这俩数之积要充分接近 n 的话各自应该充分接近 , 搜索以下的就行;

Ok, 砍掉一半, 2 万以下素数 2262 个两两组合下还是有 256 万之多.

重排这句话简直是废话, 和当然几乎永远是相同的位数.

其实我猜上下界可以压缩到 , 不过我没法证明, 那就算了...

不要写 Subsets[Array[Prime, PrimePi[2*^4]], {2}] 这种代码...

Subsets 和人家 Py 的组合函数比起来就是个傻逼...

接下来我们能做的只有等, 我先做下上面的题, 反正 1 分钟内跑得出来就不去说啥了, 我只希望这么写的时候 Prime 能自动缓存加速下...

范围确实取大了, 最后几十亿的结果都筛掉了, 说明还有优化余地...

foo[i_,j_]:=If[Equal@@Sort/@IntegerDigits/@{Prime[i]Prime[j],(Prime[i]-1)(Prime[j]-1)},{Prime[i],Prime[j]},Nothing];
data=Flatten[Table[foo[i,j],{i,2,PrimePi[2*^4]},{j,i+1,PrimePi[2*^4]-1}],1];
Numerator@First@Sort[#1 #2/(#1-1)/(#2-1)&@@@Select[data,#[[1]]#[[2]]<1*^7&]];

连续计时 44 分 02 秒, P70 数论题分析了好久, 还有 P61 也够烦的, P68 跳过...

← Level51-60 Level71-80 →