欧拉挑战:入门6段

Aster 欧拉挑战 Leave a Comment

P61:循环的多边形数

三角形数、正方形数、五边形数、六边形数、七边形数和八边形数统称为多边形数。它们分别由如下的公式给出:

三角形数P3,n=n(n+1)/21, 3, 6, 10, 15, …
正方形数P4,n=n21, 4, 9, 16, 25, …
五边形数P5,n=n(3n−1)/21, 5, 12, 22, 35, …
六边形数P6,n=n(2n−1)1, 6, 15, 28, 45, …
七边形数P7,n=n(5n−3)/21, 7, 18, 34, 55, …
八边形数P8,n=n(3n−2)1, 8, 21, 40, 65, …

由三个4位数8128、2882、8281构成的有序集有如下三个有趣的性质。

  1. 这个集合是循环的,每个数的后两位是后一个数的前两位(最后一个数的后两位也是第一个数的前两位)。
  2. 每种多边形数——三角形数(P3,127=8128)、正方形数(P4,91=8281)和五边形数(P5,44=2882)——在其中各有一个代表。
  3. 这是唯一一个满足上述性质的4位数有序集。

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

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

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

$${P_{s,n}} = \frac{{\left( {s - 2} \right){n^2} - \left( {s - 4} \right)n}}{2}$$

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

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

这次我们不用IntegerQ这种坑爹货色检测是否是s角型数了,我们用相对没这么坑的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合起来.


P62:立方数重排

立方数41063625(3453)可以重排为另外两个立方数:56623104(3843)和66430125(4053)。实际上,41063625是重排中恰好有三个立方数的最小立方数。

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

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


P63:幂次与位数

五位数16807=75同时也是一个五次幂。同样的,九位数134217728=89同时也是九次幂。

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

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

$$\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} $$

 


P64:奇周期平方根

所有的平方根写成如下连分数表示时都是周期性重复的:
$$\sqrt N  = {a_0} + \cfrac{1}{{{a_1} + \cfrac{1}{{{a_2} + \cfrac{1}{{{a_3} +  \cdots }}}}}}$$
例如,让我们考虑√23:
$$\sqrt {23}  = 4 + \sqrt {23}  - 4 = 4 + \cfrac{1}{{\cfrac{1}{{\sqrt {23}  - 4}}}} = 4 + \cfrac{1}{{1 + \cfrac{{\sqrt {23}  - 3}}{7}}}$$
如果我们继续这个过程,我们会得到如下的展开:
$$\sqrt N  = 4 + \cfrac{1}{{1 + \cfrac{1}{{3 + \cfrac{1}{{1 + \cfrac{1}{{8 +  \cdots }}}}}}}}$$
这个过程可以总结如下:
$$\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

在N ≤ 13中,恰好有4个连分数表示的周期是奇数。

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

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

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

说个关于$\LaTeX$语法的重要提示,书写连分数表达式时,要使用\cfrac代替\frac或者\over.不然你的公式就会挤一起特难看...


P65: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水过......


P66:丢番图方程

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

x2 – Dy2 = 1
举例而言,当D=13时,x的最小值出现在6492 – 13×1802 = 1。

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

对于D= {2, 3, 5, 6, 7}分别求出x取最小值的解,我们得到:

32 – 2×22 = 1
22 – 3×12 = 1
92 – 5×42 = 1
52 – 6×22 = 1
82 – 7×32 = 1

因此,对于所有D ≤ 7,当D=5时x的最小值最大。

对于D ≤ 1000,求使得x的最小值最大的D值。

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

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

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


P67:最大路径和 II

在这个15K的文本文件triangle.txt(右击并选择“目标另存为……”)中包含了一个一百行的三角形,求从其顶端出发到达底部,所能够得到的最大路径和。

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

复制粘贴18题的代码:


P68:魔力五边形环

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

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

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

总和解集
94,2,3; 5,3,1; 6,1,2
94,3,2; 6,2,1; 5,1,3
102,3,5; 4,5,1; 6,1,3
102,5,3; 6,3,1; 4,1,5
111,4,6; 3,6,2; 5,2,4
111,6,4; 5,4,2; 3,2,6
121,5,6; 2,6,4; 3,4,5
121,6,5; 3,5,4; 2,4,6

把解集中的数字连接起来,可以构造一个9位数字串;对于三角形环来说,最大的数字串是432621513。

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

本题看了一下,未做未计时,我会告诉你我是手填的吗...


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

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

n互质的数φ(n)n/φ(n)
2112
31,221.5
41,322
51,2,3,441.25
61,523
71,2,3,4,5,661.1666…
81,3,5,742
91,2,4,5,7,861.5
101,3,7,942.5

可以看出,对于n ≤ 10,当n=6时n/φ(n)取得最大值。

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

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


P70:欧拉总计函数与重排

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

1被认为和任意正整数互质,所以φ(1)=1。

有趣的是,φ(87109)=79180,而79180恰好是87109的一个重排。

在1 < n < 107中,有些n满足φ(n)是n的一个重排,求这些取值中使n/φ(n)最小的一个。

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

$$\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}$$

所以要让这个比较小n取素数不就行了.Are you kidding me?你觉得p和p-1居然能由相同的数字组成?

所以最少就就是两个素数之积了,千万以内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的话各自应该充分接近$\sqrt n $,搜索$2\sqrt n $以下的就行,Ok,砍掉一半,2万以下素数2262个两两组合下还是有256万之多.

重排这句话简直是废话,$pq$和$\left( {p - 1} \right)\left( {q - 1} \right)$当然几乎永远是相同的位数.其实我猜上下界可以压缩到$\sqrt[4]{n}\sim\sqrt n /2$,不过我没法证明,那就算了...

不要写Subsets[Array[Prime, PrimePi[2*^4]], {2}]这种代码...Subsets和人家Py的组合函数比起来就是个傻逼...

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

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


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

发表评论