欧拉挑战:入门9段

Aster 欧拉挑战 Leave a Comment

P91:格点直角三角形

点P(x1, y1)和点Q(x2, y2)都是格点,并与原点O(0,0)构成ΔOPQ。

当点P和点Q的所有坐标都在0到2之间,也就是说0 ≤ x1, y1, x2, y2 ≤ 2时,恰好能构造出14个直角三角形。

如果0 ≤ x1, y1, x2, y2 ≤ 50,能构造出多少个直角三角形?

看到这种题第一反应就是生成函....那啥....我又看出规律了.....

编号1-14,对于s×s的正方形,首先有三种简单的情况,就是1,2,10以及8,9,14这种直角在角上的.$3{s^2}$到手.

不在角上的就比较麻烦了...画个草图

 

设直角那个叫$P({x_1},{y_1})$.然后就是$P({x_1},{y_1}),Q({x_2},{y_2}),O({x_0},{y_0})$.

$$ \begin{aligned}
&\because OP \bot PQ \\
&\therefore \overrightarrow{OP} \cdot \overrightarrow{PQ} = 0 \\
&\Rightarrow {x_1}{x_2} + {y_1}{y_2} = x_1^2 + y_1^2
\end{aligned}$$

化简下,于是就从几何问题转化为了代数问题,求这个的整数解.这时候开始穷举也行,不过还能化简公式.

$$ \begin{aligned}
&\quad\ \left\{ \begin{gathered}
{x_2} = {x_1} + a\\
{y_2} = {y_1} + b\\
\end{gathered} \right.\\
&\Rightarrow a{x_1} + b{y_1} = 0\\
&\quad\ d = GCD({x_1},{y_1})\\
&\Rightarrow (a,b) = ( - \frac{{{y_1}}}{d}n,\frac{{{x_1}}}{d}n)\\
&\Rightarrow f(s) = Min(\frac{{{y_1}}}{{{x_1}}}d,\frac{{s - {x_1}}}{{{y_1}}}d)\\
&\Rightarrow S = \sum\limits_{0 < {x_1},{y_1} < s} {f(s)} + 3{s^2}
\end{aligned}$$

翻译成代码,根据对称性卡死${x_1} < {y_2}$,这样还可以少一半计算量,最后乘以2补回去.

92:平方数字链

将一个数的所有数字的平方相加得到一个新的数,不断重复直到新的数已经出现过为止,这构成了一条数字链。

例如,

44 → 32 → 13 → 10 → 11
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

可见,任何一个到达1或89的数字链都会陷入无尽的循环。更令人惊奇的是,从任意数开始,最终都会到达1或89。

有多少个小于一千万的数最终会到达89?

硬计算差评,还有我又一次没看到小于号.....虽然不影响结果...

P93:算术表达式

使用集合{1, 2, 3, 4}中每个数字恰好一次以及(+, −, *, /)四则运算和括号,可以得到不同的正整数。

例如,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)

注意不允许直接把数字连起来,如12 + 34。

使用集合{1, 2, 3, 4},可以得到31个不同的数,其中最大值是36,以及1到28之间所有的数。

若使用包含有四个不同数字a < b < c < d的集合可以得到从1到n之间所有的数,求其中使得n最大的集合,并将你的答案写成字符串:abcd。

9个数字选4个,C(9,4)=126.四个符号选三个C(4,3)=4,7个位子8个空选两个放括号C(8,2)=28,全部乘起来也不大...

没括号的64种情况下是这样的,好吧我就是想秀一下我珍藏多年的强力函数.....

ListToExpression[list_]:=list//.({x___,PatternSequence[a_,u:#,b_],y___}:>{x,u[a,b],y}&/@{Power|Log|Surd,Times|Divide,Plus|Subtract});
OperatorRiffle[exp_,oper_:{Times,Divide,Plus,Subtract}] :=Grid[{#,ListToExpression@#}&/@(Riffle[exp,#]&/@Tuples[oper,Length@exp-1]),Alignment->Left];
OperatorRiffle[{a,b,c,d}]

虽然后来我想到这个其实直接变字符串然后连起来然后读回表达式就行....不过那样就无法装逼了...

而且这个方法对于Log,Surd这类非算子也有效,强制解释为最高级算子.而且运算优先级完全可以魔改,我就是规定加法优先乘法怎么着.....

注意相减算子是SubMinus,Minus是取负,不是个算子.MinusPlus, PlusMinus正负号,负正号这俩就连运算都不是了,只是个保留符号罢了.

Ok,回到这道题,不管怎么样我们就考虑怎么穷举出a,b,c,d的所有计算结果好了.

P94:几乎等边的三角形

可以证明,不存在边长为整数的等边三角形其面积也是整数。但是,存在几乎等边的三角形 5-5-6,其面积恰好为12。

我们定义几乎等边的三角形是有两条边一样长,且第三边与这两边最多相差1的三角形。

对于所有边长和面积均为整数且周长不超过十亿(1,000,000,000)的三角形,求其中几乎等边的三角形的周长之和。

底边不能是奇数,否则面积就会变成无理数.

设底边是$2n$,腰就是$2n \pm 1$,周长就是$6n \pm 2$,所以n的范围就出来了,然后只要判定高$\sqrt {5{n^2} \pm 4n + 1} $是否是整数就行了.

大概像这样 Select[Table[Sqrt[#1],{n,1*^6/3}],FractionalPart[#]==0&]&/@{1.0-4 n+5 n^2,1.0+4 n+5 n^2}

不行啊,周长10亿呢,得找个更强的公式...

设三边分别是$(a,b,c) = \left( {n,n,n + 1} \right)$

$$\begin{aligned}
S &= \frac{{n + 1}}{4}\sqrt {3{n^2} - 2n - 1} \\
&\Rightarrow 3{n^2} - 2n - 1 = {y^2}\\
&\Rightarrow n = \frac{{1 \pm \sqrt {3{y^2} + 4} }}{3}\\
&\Rightarrow {x^2} - 3{y^2} = 4,(x,y) \in {N_ + }
\end{aligned}$$

佩尔方程咯.....

Reduce[{x^2-3y^2==4,x>0,y>0},{x,y},Integers]

(14,8)对应的是(5,5,6)差了一项,要位移一格...

$$\left\{ \begin{gathered}
{x_{i + 1}} = {\left( {2 - \sqrt 3 } \right)^i} + {\left( {\sqrt 3 + 2} \right)^i}\\
{y_{i + 1}} = \frac{{{{\left( {\sqrt 3 + 2} \right)}^i} - {{\left( {2 - \sqrt 3 } \right)}^i}}}{{\sqrt 3 }}\\
\end{gathered} \right.$$

或者写成矩阵式就是

$$\left( {\begin{array}{*{20}{c}}
{{x_i}} \\ {{y_i}}
\end{array}} \right) = {\left( {\begin{array}{*{20}{c}}
2&3 \\ 1&2
\end{array}} \right)^i}\left( {\begin{array}{*{20}{c}}
4 \\ 2
\end{array}} \right)$$

然后代回原来的式子就行.

$\left( {n,n,n - 1} \right)$作同样的推导也是这个式子,这倒是省心了.

公式在手别说10亿了,10亿的平方都不怕了...

P95:亲和数链

一个数除了本身之外的因数称为真因数。例如,28的真因数是1、2、4、7和14。这些真因数的和恰好为28,因此我们称28是完全数。

有趣的是,220的真因数之和是284,同时284的真因数之和是220,构成了一个长度为2的链,我们也称之为亲和数对。

有一些更长的序列并不太为人所知。例如,从12496出发,可以构成一个长度为5的链:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)
由于这条链最后又回到了起点,我们称之为亲和数链。

找出所有元素都不超过一百万的亲和数链中最长的那条,并给出其中最小的那个数。

FindCycle[Graph[Table[i$$DirectedEdge](DivisorSigma[1,i]-i),{i,1,1*^5}]],Infinity] 

然后大点就爆了.....Well......换个函数就好...ConnectedComponents.....

P96:数独

数独(日语原意为数的位置)是一种热门的谜题。它的起源已不可考,但是与欧拉发明的一种类似而更加困难的谜题拉丁方阵之间有着千丝万缕的联系。数独的目标是替换掉9乘9网格中的空白位置(或0),使得每行、每列以及每个九宫格中恰好都包含数字1~9。一个构造精良的数独谜题应该包含有唯一解,且能够通过逻辑推断来解决,尽管有时可能必须通过“猜测并检验”来排除一些选项(这一要求目前还颇受争议)。寻找答案的复杂度决定了题目的难度;上面这个谜题被认为是简单的谜题,因为我们可以通过直截了当的演绎推理来解决它。

在这个6K的文本文件sudoku.txt(右击并选择“目标另存为……”)中包含有50个不同难度的数独谜题,但保证它们都只有唯一解(文件中的第一个谜题就是上述样例)。

解开这50个谜题,找出每个谜题解答左上角的三个数字并连接起来,给出这些数的和;举例来说,上述样例解答左上角的三个数字连接起来构成的数是483。

按例跳过未计时,另外回溯会超时,最好写逻辑判别.

P97:非梅森大素数

1999年人们发现了第一个超过一百万位的素数,这是一个梅森素数,可以表示为26972593−1,包含有2,098,960位数字。在此之后,更多形如2p−1的梅森素数被发现,其位数也越来越多。

然而,在2004年,人们发现了一个巨大的非梅森素数,包含有2,357,207位数字:28433×27830457+1。

找出这个素数的最后十位数字。

快速幂模,水过....

P98:重排平方数

将单词CARE中的四个字母依次赋值为1、2、9、6,我们得到了一个平方数:1296 = 362。神奇的是,使用同样的数字赋值,重排后的单词RACE同样构成了一个平方数:9216 = 962。我们称CARE和RACE为重排平方单词对,同时规定这样的单词对不允许有前导零或是不同的字母赋相同的值。

在这个16K的文本文件words.txt(右击并选择“目标另存为……”)中包含了将近两千个常见英文单词,找出所有的重排平方单词对(一个回文单词不视为它自己的重排)。

重排平方单词对所给出的最大平方数是多少?

注意:所有的重排单词必须出现在给定的文本文件中。

没做出来...放弃....

本来以为So easy的,直接照着说明写一遍就好了,结果发现赋值情况有点多,直接上估计跑到明天都跑不完...

P99:最大的幂

比较两个如211和37这样写成幂的形式的数并不困难,任何计算器都能验证211 = 2048 < 37 = 2187。

然而,想要验证632382518061 > 519432525806就会变得非常困难,因为这两个数都包含有超过三百万位数字。

22K的文本文件base_exp.txt(右击并选择“目标另存为……”)有一千行,每一行有一对底数和指数,找出哪一行给出的幂的值最大。

注意:文件的前两行就是上述两个例子。

高精计算,哦不,其实就是取个对数....真水.....

P100:安排概率

在一个盒子中装有21个彩色碟子,其中15个是蓝的,6个是红的。如果随机地从盒子中取出两个碟子,取出两个蓝色碟子的概率是P(BB) = (15/21)×(14/20) = 1/2。

下一组使得取出两个蓝色盘子的概率恰好为50%的安排,是在盒子中装有85个蓝色碟子和35个红色碟子。

当盒子中装有超过1012 = 1,000,000,000,000个碟子时,找出第一组满足上述要求的安排,并求此时盒子中蓝色碟子的数量。

$$\left\{ \begin{aligned}
&\frac{{B(B - 1)}}{{N(N - 1)}} = \frac{1}{2}\\
&0 < B < {10^{12}} < N
\end{aligned} \right.$$

有点懵逼,简单过头了吧放这,大概是100题了给你们庆祝下.....


58分30秒,欧耶,一小时内搞定,也就P93比较麻烦,其他稍微推导一下都能有思路.P96未计时,P98放弃.

欧拉挑战:入门8段

Aster 欧拉挑战 Leave a Comment

P81:路径和:两个方向

在如下的5乘5矩阵中,从左上方到右下方始终只向右或向下移动的最小路径和为2427,由标注红色的路径给出。

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从该矩阵的左上方到右下方始终只向右和向下移动的最小路径和。

和67题一样,不过我那个算法只是定义给三角形的...

虽然正方形就是两个三角形叠起来,不过倒来倒去不麻烦嘛...

有的这么折腾还不如写个正统的动态规划.

$$\begin{aligned}
B[1,1] &= A[1,1]\\
B[i,j] &= B[i,j - 1] + A[i,j]\quad &if\;i = 1\\
&= B[i - 1,j] + A[i,j]\quad &if\;j = 1\\
&= \min (B[i - 1,j],B[i,j - 1]) + A[i,j]\\
\end{aligned}$$

然后直接公式翻译成代码就行了,注意Mathematica是少数和人类习惯一样下标从1开始的编程语言.

这倒不是MMA人性化或者傲娇.MMA的下标其实也是从0开始的,但是下标0分配给了类型,也就是表头.

动态规划写出来也和公式一样美观啊

B[1, 1] := A[[1, 1]];
B[1, j_] := B[1, j - 1] + A[[1, j]];
B[i_, 1] := B[i - 1, 1] + A[[i, 1]];
B[i_, j_] := B[i, j] = Min[B[i - 1, j], B[i, j - 1]] + A[[i, j]];

当然其实很多人觉得这个很丑来着你们说美观的是什么心态....所以我按另一种审美写了个:


P82:路径和:三个方向

注意:这是第81题的一个更具挑战性的版本。

在如下的5乘5矩阵中,从最左栏任意一格出发,始终只向右、向上或向下移动,到最右栏任意一格结束的最小路径和为994,由标注红色的路径给出。

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从最左栏到最右栏的最小路径和。

我感觉到了套路的味道...下一道不会要四个方向了吧?

啊哈,还真是,我测了下连三个矩阵都是一样的说,那就是Dijkstra了......

不过我为什么要自己撸一个Dijkstra,脑子瓦特了,把他变成图,剩下的交给Mathematica...

我们可以直接邻接化这个80×80的矩阵变成6400×6400的大型稀疏邻接矩阵,然后AdjacencyGraph变成Graph对象....怎么感觉有点逗比..

不行我得查查高级解决方案....唔,有个古函数MakeGraph...不过这是个古函数了得找到激活方法....

10分钟过去了.......好吧,I'm angry,我之后得撸个程序包...


P83:路径和:四个方向

注意:这是第81题的一个极具挑战性的版本。

在如下的5乘5矩阵中,从左上角到右下角任意地向上、向下、向左或向右移动的最小路径和为2297,由标注红色的路径给出。

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从左上角到右下角任意地向上、向下、向左或向右移动的最小路径和。

用HTML画表格好捉急啊...

HTML这种玩意儿是给人写的吗....


P84:大富翁几率

大富翁游戏的标准棋盘大致如下图所示:

GOA1CC1A2T1R1B1CH1B2B3JAIL
H2C1
T2U1
H1C2
CH3C3
R4R2
G3D1
CC3CC2
G2D2
G1D3
G2JF3U2F2F1R3E3E2CH2E1FP

玩家从标记有“GO”的方格出发,掷两个六面的骰子并将点数和相加,作为本轮他们前进的步数。如果没有其它规则,那么落在每一格上的概率应该是2.5%。但是,由于“G2J”(入狱)、“CC”(宝箱卡)和“CH”(机会卡)的存在,这个分布会有所改变。

除了落在“G2J”上,或者在“CC”或“CH”上抽到入狱卡之外,如果玩家连续三次都掷出两个相同的点数,则在第三次时将会直接入狱。

游戏开始时,“CC”和“CH”所需的卡片将被洗牌打乱。当一个玩家落在“CC”或“CH”上时,他们从宝箱卡和机会卡的牌堆最上方取一张卡并遵循指令行事,并将该卡再放回牌堆的最下方。宝箱卡和机会卡都各有16张,但我们只关心会影响到移动的卡片,其它的卡片我们都将无视它们的效果。

  • 宝箱卡 (2/16 张卡):
    • 回到起点“GO”
    • 进入监狱“JAIL”
  • 机会卡 (10/16 张卡):
    • 回到起点“GO”
    • 进入监狱“JAIL”
    • 移动到“C1”
    • 移动到“E3”
    • 移动到“H2”
    • 移动到“R1”
    • 移动到下一个“R”(铁路公司)
    • 移动到下一个“R”
    • 移动到下一个“U”(公共服务公司)
    • 后退三步

这道题主要考察掷出骰子后停在某个特定方格上的概率。显然,除了停在“G2J”上的可能性为0之外,停在“CH”格的可能性最小,因为有5/8的情况下玩家会移动到另一格。我们不区分是被送进监狱还是恰好落在监狱“JAIL”这一格,而且不考虑需要掷出两个相同的点数才能出狱的要求,而是假定进入监狱的第二轮就会自动出狱。

从起点“GO”出发,并将方格依次标记00到39,我们可以将这些两位数连接起来表示方格的序列。

统计学上来说,三个最有可能停下的方格分别是“JAIL”(6.24%)或方格10,E3(3.18%)或方格24以及“GO”(3.09%)或方格00。这三个方格可以用一个六位数字串表示:102400。

如果我们不用两个六面的骰子而是用两个四面的骰子,求出三个最有可能停下的方格构成的数字串。

按惯例跳过,未计时.

这道题一点意思都没有,就是蒙特卡洛...

没有监狱的话还好,是个马尔科夫过程,加入了入狱出狱的设定就瞬间炸了,没有数学模型能解了...


P85:数长方形

如果数得足够仔细,能看出在一个3乘2的长方形网格中包含有18个不同大小的长方形,如下图所示:

尽管没有一个长方形网格中包含有恰好两百万个长方形,但有许多长方形网格中包含的长方形数目接近两百万,求其中最接近这一数目的长方形网格的面积。

我就数得一点都不仔细,我数了好几遍还没数对.感觉这种题肯定有生成函数解法.

好吧不用生了,脑袋转个弯就出来了,长方形就是长里面选两条,宽里面选两条,那就是

$$S(i,j) = C_i^2C_j^2 = \frac{1}{4}({i^2} + i)({j^2} + j)$$

这么说顺便也解决掉了高维中的情况了,然后就解方程呗....

我还是给点干货吧,如果是求正方形的话就是小正方形移动呗,然后高维推广也不难看出,化简就免了...

$$\begin{aligned}
d &= \min (m,n)\\
S&=\sum\limits_{a = 1}^{d - 1} {(m - a)} (n - a)\\
&= \frac{1}{6}(d - 1)(2{d^2} - d(3m + 3n + 1) + 6mn)\\
&= \frac{1}{6}(d - 1)(3mn - d(d + 1))
\end{aligned}$$


P86:长方体路径

蜘蛛S位于一个6乘5乘3大小的长方体屋子的一角,而苍蝇F则恰好位于其对角。沿着屋子的表面,从S到F的最短“直线”距离是10,路径如下图所示:

然而,对于任意长方体,“最短”路径实际上一共有三种可能;而且,最短路径的长度也并不一定为整数。

当M=100时,若不考虑旋转,所有长、宽、高均不超过M且为整数的长方体中,对角的最短距离是整数的恰好有2060个;这是使得该数目超过两千的最小M值;当M=99时,该数目为1975。

找出使得该数目超过一百万的最小M值。

死算的话有点慢,我们来分析下:

令${F(k)}$是当最大长度为k的长方体中解的数目,所以我们要求的就是第一个使得$\sum\limits_{1 \leqslant k \leqslant n} {F(k)}$超过百万的n值减1. 其他两条边与k构成勾股三元组 .因此对于固定的b,每一种b能被写成两个小于k的正整数之和的方式代表另一个解.

于是我们发现对于给定的b ≤ 2k,解就是$\left\lfloor {\frac{b}{2}} \right\rfloor  + 1 - Max(1,k - b)$,值为0代表无解. 然后加起来就是固定$k$下的解数目了.


P87:素数幂三元组

最小的可以表示为一个素数的平方,加上一个素数的立方,再加上一个素数的四次方的数是28。实际上,在小于50的数中,一共有4个数满足这一性质:

28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24

有多少个小于五千万的数,可以表示为一个素数的平方,加上一个素数的立方,再加上一个素数的四次方?

我靠,不会是三重循环遍历吧,有点坑爹啊,我要骂人了,这几道题太不友好了....

这种题你和我说有会有数论解法?数论解法估计是没有的了,造个筛法应该还是可以的.

当然是从高次开始筛,减完筛低次,全都筛完还剩下的就是解了.该程序已同步到BGG包.


P88:积和数

若自然数N能够同时表示成一组至少两个自然数{a1, a2, … , ak}的积和和,也即N = a1 + a2 + … + ak = a1 × a2 × … × ak,则N被称为积和数。

例如,6是积和数,因为6 = 1 + 2 + 3 = 1 × 2 × 3。

给定集合的规模k,我们称满足上述性质的最小N值为最小积和数。当k = 2、3、4、5、6时,最小积和数如下所示:

k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6

因此,对于2≤k≤6,所有的最小积和数的和为4+6+8+12 = 30;注意8只被计算了一次。

已知对于2≤k≤12,所有最小积和数构成的集合是{4, 6, 8, 12, 15, 16},这些数的和是61。

对于2≤k≤12000,所有最小积和数的和是多少?

可能性太多了,写不出跑进1 min的算法...放弃

不过我当时搜索到了一篇论文Arixv,然而看不太懂他在说啥...


P89:罗马数字

要正确地用罗马数字表达一个数,必须遵循一些基本规则。尽管符合规则的写法有时会多于一种,但对每个数来说总是存在一种“最好的”写法。

例如,数16就至少有六种写法:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

然而,根据规则,只有XIIIIII和XVI是合理的写法,而后一种因为使用了最少的数字而被认为是最有效的写法。

在这个11K的文本文件roman.txt (右击并选择“目标另存为……”)中包含了一千个合理的罗马数字写法,但并不都是最有效的写法;有关罗马数字的明确规则,可以参考关于罗马数字

求出将这些数都写成最有效的写法所节省的字符数。

注意:你可以假定文件中的所有罗马数字写法都不包含连续超过四个相同字符。

阅读理解题...解略


P90:立方体数字对

在一个立方体的六个面上分别标上不同的数字(从0到9),对另一个立方体也如法炮制。将这两个立方体按不同的方向并排摆放,我们可以得到各种各样的两位数。

例如,平方数64可以通过这样摆放获得:

事实上,通过仔细地选择两个立方体上的数字,我们可以摆放出所有小于100的平方数:01、04、09、16、25、36、49、64和81。

例如,其中一种方式就是在一个立方体上标上{0, 5, 6, 7, 8, 9},在另一个立方体上标上{1, 2, 3, 4, 8, 9}。

在这个问题中,我们允许将标有6或9的面颠倒过来互相表示,只有这样,如{0, 5, 6, 7, 8, 9}和{1, 2, 3, 4, 6, 7}这样本来无法表示09的标法,才能够摆放出全部九个平方数。

在考虑什么是不同的标法时,我们关注的是立方体上有哪些数字,而不关心它们的顺序。

{1, 2, 3, 4, 5, 6}等价于{3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6}不同于{1, 2, 3, 4, 5, 9}

但因为我们允许在摆放两位数时将6和9颠倒过来互相表示,这个例子中的两个不同的集合都可以代表拓展集{1, 2, 3, 4, 5, 6, 9}。

对这两个立方体有多少中不同的标法可以摆放出所有的平方数?

允许6 9 相互表示....好好的一个组合问题,这样岂不是把问题复杂化了...

嗯?不对,其实没区别,Subsets[{0, 1, 2, 3, 4, 5, 6, 7, 8, 6}, {6}]就行了.

然后把这些组合分配给俩骰子,C(C(10, 6), 2) = 21945种,穷举不虚的...

然后就是要造一个函数判定一个俩序列是否可以组成平方数.

怎么判定呢....继续穷举好了,穷举所有能构成的数字,看看最后能否包括所有的平方数.

那计算量再乘以6×6那就是790 020,连百万都没有我就放心穷举了.

不过还是可以做点小优化的,比如先删掉所有的7,MemberQ 9次太笨了,直接Union上去看看有没有变化就行了.

不知为何这道题做出来的人不多,难度显示说有40%......


连续计时,1小时46分钟11秒....要命,都是硬计算....

你知道吗,我做到30题的时候感觉2小时能杀光100题是绰绰有余的...然后就不断被各种题各种焦作人了.....

主要是查资料查起来没时间感.....有这个查的时间自己撸代码也能撸出来了....."

欧拉挑战:入门7段

Aster 欧拉挑战 Leave a Comment

P71:有序分数

考虑形如n/d的分数,其中n和d均为正整数。如果n < d且其最大公约数为1,则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出,我们得到:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可以看出2/5是3/7直接左邻的分数。

将所有d ≤ 1,000,000的最简真分数按大小升序排列,求此时3/7直接左邻的分数的分子。

找个函数来表示接近程度,就是求

$$f(n) = \frac{1}{n}\left\lfloor {\frac{{3n}}{7}} \right\rfloor $$

最大值的意思,写完代码我看了眼输出,我突然想到,我在写什么玩意儿...

这玩意儿不是以7位周期单调递增吗, 999999 = 142857×7 那岂不是直接求f(999 992)到f(999 999)就完事了...


P72:分数计数

考虑形如n/d的分数,其中n和d均为正整数。如果n < d且其最大公约数为1,则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出,我们得到:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可以看出该集合中共有21个元素。

d ≤ 1,000,000的最简真分数构成的集合中共有多少个元素?

最简真分数的个数其实就是欧拉函数值,想下欧拉函数给出与n互质的正整数数目,互质那不就最简真分数了吗

没听说过欧拉函数的和函数有快速计算方法的,死算吧,顶多来个并行.


P73:分数有范围计数

考虑形如n/d的分数,其中n和d均为正整数。如果n < d且其最大公约数为1,则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出,我们得到:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可以看出在1/3和1/2之间有3个分数。

将d ≤ 12,000的最简真分数构成的集合排序后,在1/3和1/2之间有多少个分数?

我们用聪明点的穷举,对于分母a,先卡死上下界,求里面和a互质的数个数就行.

ParallelSum[Boole[CoprimeQ[a,b]],{a,1,12000},{b,Floor[a/3+1],Ceiling[a/2-1]}]

我们来封装成函数


P74:数字阶乘链

145之所以广为人知,是因为它的各位数字的阶乘之和恰好等于本身:

1! + 4! + 5! = 1 + 24 + 120 = 145

而169则可能不太为人所知,尽管从169开始不断地取各位数字的阶乘之和构成了最长的循环回到169;事实上,只存在三个这样的循环:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

不难证明,从任意数字出发最终都会陷入循环。例如,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

从69开始可以得到一个拥有五个不重复项的链,但是从一个小于一百万的数出发能够得到的最长的无重复项链包含有60项。

从小于一百万的数出发,有多少条链恰好包含有60个不重复项?

有种不祥的预感,是不是又要用编译了...

用点小技巧,网上去查所有的不动点和循环链,然后用模式对象和递归机制可以稍稍优化下.

其实之前Collatz那题也应该这么做,不过当时我没想到.


P75:唯一的整数边直角三角形

只能唯一地弯折成整数边直角三角形的电线最短长度是12厘米;当然,还有很多长度的电线都只能唯一地弯折成整数边直角三角形,例如:

12厘米: (3,4,5)
24厘米: (6,8,10)
30厘米: (5,12,13)
36厘米: (9,12,15)
40厘米: (8,15,17)
48厘米: (12,16,20)

相反地,有些长度的电线,比如20厘米,不可能弯折成任何整数边直角三角形,而另一些长度则有多个解;例如,120厘米的电线可以弯折成三个不同的整数边直角三角形。

120厘米: (30,40,50), (20,48,52), (24,45,51)

记电线长度为L,对于L ≤ 1,500,000,有多少种取值只能唯一地弯折成整数边直角三角形?

这题我想错了,我用的勾股树算法

后来想到干嘛不用广义勾股数组,所有的勾股数组都能写成这个形式:

$${({a^2} - {b^2})^2} + {(2ab)^2} = {({a^2} + {b^2})^2}$$

嗯,我们来看一看一个流程完整的函数是什么样子的:

一个标准的函数同时要包括说明,属性设定和错误捕捉,可以的话要有必要的注释.

换行这种东西就无所谓了,看个人风格,我喜欢写成砖头的样子,一行一赋值,有模块或者循环就缩进.If尽量写一行.该代码已整合进BGG.本来还想加上并行化的,但是并行循环这玩意儿实在是难写,写了会儿不想动了...

然后可以直接调用RTCount[15*^5].


P76:加和计数

将5写成整数的和有6种不同的方式:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

将100写成整数的和有多少种不同的方式?

F1,内置水过...


P77:素数加和

将10写成素数的和有5种不同的方式:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

写成素数的和有超过五千种不同的方式的数最小是多少?

你以为换成素数我就秒杀不了了吗,直接数?


P78:硬币分拆

记p(n)是将n枚硬币分拆成堆的不同方式数。例如,五枚硬币有7种分拆成堆的不同方式,因此p(5)=7。

OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O O

找出使p(n)能被一百万整除的最小n值。

秒杀吧.......Well,失败了,要跑好久,让他跑着吧,我做下一题了....


P79:密码推断

网上银行常用的一种密保手段是向用户询问密码中的随机三位字符。例如,如果密码是531278,询问第2、3、5位字符,正确的回复应当是317。

在文本文件keylog.txt中包含了50次成功登陆的正确回复。

假设三个字符总是按顺序询问的,分析这个文本文件,给出这个未知长度的密码最短的一种可能。

不想解释,这个问题推广一下就能黑密保卡了....

如果我能一直监听一个用户输密保密码,足够多的次数后就能得知这张密保卡上写了啥啦!


P80:平方根数字展开

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

对于前一百个自然数,求所有无理数平方根小数点后一百位数字的总和。

最近几道压轴题里最水的,RealDigits秒了.....

Total@Flatten@Table[RealDigits[Sqrt@i, 10, 100, -1], {i, 100}]

大叉,纳尼???然后我看了半天发现要求的是无理数,Well,还要额外处理一下.......

还有是求前100位不是小数点后100位,不过我记得Decimal digits不是小数位的意思吗...

Total@Flatten[First@RealDigits[#,10,100]&/@Cases[Sqrt@Range@100,Except[_Integer]]]


连续计时26分59秒,P75看上去简单但是还是有点难,P80题没看懂瞎搞,一次冻30秒,无妄之灾...

欧拉挑战:入门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跳过...

欧拉挑战:入门5段

Aster 欧拉挑战 Leave a Comment

P51:素数数字替换

将两位数*3的第一个数字代换为任意数字,在九个可能值中有六个是素数:13、23、43、53、73和83。

将五位数56**3的第三和第四位数字代换为相同的任意数字,就得到了十个可能值中有七个是素数的最小例子,这个素数族是:56003、56113、56333、56443、56663、56773和56993。56003作为这一族中最小的成员,也是最小的满足这个性质的素数。

通过将部分数字(不一定相邻)代换为相同的任意数字,有时能够得到八个素数,求满足这一性质的最小素数。

 竟然.....没做出来,放弃......实在不会剪枝....


P52:重排的倍数

可以看出,125874和它的两倍251748拥有同样的数字,只是排列顺序不同。

有些正整数x满足2x、3x、4x、5x和6x都拥有相同的数字,求其中最小的正整数。

我看了看题,第一反应142857,然后跑出来真的是142857......这就很尴尬了...


P53:组合数选择

从五个数12345中选择三个恰好有十种方式,分别是:

123、124、125、134、135、145、234、235、245和345
在组合数学中,我们记作:$C_5^3 = 10$

一般来说,

$$C_n^r = \frac{{n!}}{{r!(n - r)!}},r \leqslant n,0! = 1$$

直到n = 23时,才出现了超出一百万的组合数:$C_{23}^{10} = 1144066$

若数值相等形式不同也视为不同,对于1 ≤ n ≤ 100,有多少个组合数$C_n^r$超过一百万?

穷举水过


P54:扑克手牌

在扑克游戏中,玩家的手牌由五张牌组成,其等级由低到高分别为:

  • 单牌:牌面最大的一张牌。
  • 对子:两张牌面一样的牌。
  • 两对:两个不同的对子。
  • 三条:三张牌面一样的牌。
  • 顺子:五张牌的牌面是连续的。
  • 同花:五张牌是同一花色。
  • 葫芦:三条带一个对子。
  • 四条:四张牌面一样的牌。
  • 同花顺:五张牌的牌面是连续的且为同一花色。
  • 同花大顺:同一花色的10、J、Q、K、A。

牌面由小到大的顺序是:2、3、4、5、6、7、8、9、10、J、Q、K、A。

如果两名玩家的手牌处于同一等级,那么牌面较大的一方获胜;例如,一对8胜过一对5(参见例1);如果牌面相同,例如双方各有一对Q,那么就比较玩家剩余的牌中最大的牌(参见例4);如果最大的牌相同,则比较次大的牌,依此类推。

考虑以下五局游戏中双方的手牌:

手牌玩家1玩家2胜者
1红桃5 草花5 黑桃6 黑桃7 方片K草花2 黑桃3 黑桃8 方片8 方片10玩家2
一对5一对8
2方片5 草花8 黑桃9 黑桃J 草花A草花2 草花5 方片7 黑桃8 红桃Q玩家1
单牌A单牌Q
3方片2 草花9 黑桃A 红桃A 草花A方片3 方片6 方片7 方片10 方片Q玩家2
三条A同花方片
4方片4 黑桃6 红桃9 红桃Q 草花Q方片3 方片6 红桃7 方片Q 黑桃Q玩家1
一对Q一对Q
最大单牌9最大单牌7
5红桃2 方片2 草花4 方片4 黑桃4草花3 方片3 黑桃3 黑桃9 方片9玩家1
葫芦葫芦
(三条4)(三条3)

在这个文本文件poker.txt中,包含有两名玩家一千局的手牌。每一行包含有10张牌(均用一个空格隔开):前5张牌属于玩家1,后5张牌属于玩家2。你可以假定所有的手牌都是有效的(没有无效的字符或是重复的牌),每个玩家的手牌不一定按顺序排列,且每一局都有确定的赢家。

其中有多少局玩家1获胜?

跳过未做,未计时.

ShowHardQ函数返回给定牌局的胜负向量,输入长度除以5返回对应的排序向量.

因为梭哈赢者通吃,4人的话返回就是{0,0,0,1}这种胜负向量.不要传长度不是5倍数的异常数据,我可没有写异常捕捉.


P55:利克瑞尔数

将47倒序并相加得到47 + 74 = 121,是一个回文数。

不是所有的数都能像这样迅速地变成回文数。例如,

349 + 943 = 1292
1292 + 2921 = 4213
4213 + 3124 = 7337

也就是说,349需要迭代三次才能变成回文数。

尽管尚未被证实,但有些数,例如196,被认为永远不可能变成回文数。如果一个数永远不可能通过倒序并相加变成回文数,就被称为利克瑞尔数。出于理论的限制和问题的要求,在未被证否之前,我们姑且就认为这些数确实是利克瑞尔数。除此之外,已知对于任意一个小于一万的数,它要么在迭代50次以内变成回文数,要么就是没有人能够利用现今所有的计算能力将其迭代变成回文数。事实上,10677是第一个需要超过50次迭代变成回文数的数,这个回文数是
4668731596684224866951378664(53次迭代,28位数)。

令人惊讶的是,有些回文数本身也是利克瑞尔数数;第一个例子是4994。

小于一万的数中有多少利克瑞尔数?

它的意思就是迭代50次,还没完就是利克瑞尔数.那就直接全跑一便呗...


P56:幂的数字和

一古戈尔(10100)是一个巨大的数字:一后面跟着一百个零。100100则更是无法想像地巨大:一后面跟着两百个零。然而,尽管这两个数如此巨大,各位数字和却都只有1。

若a, b < 100,所有能表示为ab的自然数中,最大的各位数字和是多少?

穷举水过,然后我又没看到小于号.....


P57:平方根逼近

2的平方根可以用一个无限连分数表示:

$$\sqrt 2  = 2 + \frac{1}{{2 + \frac{1}{{2 + \frac{1}{ \cdots }}}}}$$

将连分数计算取前四次迭代展开式分别是:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

接下来的三个迭代展开式分别是99/70、239/169和577/408,但是直到第八个迭代展开式1393/985,分子的位数第一次超过分母的位数。

在前一千个迭代展开式中,有多少个分数分子的位数多于分母的位数?

生成分子分母的列表然后比比就行了呗.

$$\begin{aligned}
{a_n} &= \frac{b}{a}\\
{a_{n + 1}} &= \frac{{2a + b}}{{a + b}} = 1 + \frac{1}{{1 + {a_n}}}
\end{aligned}$$

 


P58:螺旋素数

从1开始逆时针螺旋着摆放自然数,我们可以构造出一个边长为7的螺旋数阵。

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
可以发现,所有的奇数平方都在这个螺旋方针的右下对角线上,更有趣的是,在所有对角线上一共有8个素数,比例达到8/13 ≈ 62%。

在这个方阵外面完整地再加上一层,就能构造出一个边长为9的螺旋方阵。如果不断重复这个过程,当对角线上素数的比例第一次低于10%时,螺旋数阵的边长是多少?

好像...更加用不到我辛辛苦苦造的螺旋矩阵了...

规律上次28题已经找过了.先生成这个序列data再说.

然后左边开始卷这个列表,卷到素数低于10%为止.

这个思路可以泛化,稍微改下通项公式就可以求一个难以分析的数列的奇偶比例变化之类的...


P59:异或解密

计算机上的每个字符都被指定了一个独特的代码,其中被广泛使用的一种是ASCII码(美国信息交换标准代码)。例如,大写字母A = 65,星号(*) = 42,小写字母k = 107。

一种现代加密方法是将一个文本文档中的符号先转化为ASCII码,然后将每个字节异或一个根据密钥确定的值。使用异或进行加密的好处在于,只需对密文使用相同的密钥再加密一次就能得到明文,例如,65 XOR 42 = 107,而107 XOR 42 = 65。

为了使加密难以破解,密钥要和明文一样长,由随机的字节构成。用户会把加密过的信息和密钥放置在不同的地方,解密时二者缺一不可。

不幸的是,这种方法对大多数人来说并不实用,因此一个略有改进的方法是使用一个密码作为密钥。密码的长度很有可能比信息要短,这时候就循环重复使用这个密码进行加密。这种方法需要达到一种平衡,一方面密码要足够长才能保证安全,另一方面需要充分短以方便记忆。

你的破解任务要简单得多,因为密钥只由三个小写字母构成。文本文档cipher.txt(右击并选择“目标另存为……”)中包含了加密后的ASCII码,并且已知明文包含的一定是常见的英文单词,解密这条消息并求出原文的ASCII码之和。

跳过未做,未计时.

轮一遍,找里面有the的...我就不信一段常见英文能没有the...

包容判定the长短正好,太长比如this,that都无解,in,of,to之类的介词就太短了人肉要死...was也没成...

怎么说呢,这么搞比较凑巧,比较正统的方法还是频度分析,一般把字母e作为切入口,因为出现次数几乎最多.

比如维基上Math的页面统计:

Take[Reverse[Sort[CharacterCounts[WikipediaData["Math"]]]],10]
<|" "->4832,"e"->3078,"t"->2586,"a"->2455,"i"->2241,"n"->1925,"s"->1884,"o"->1826,"r"->1443,"h"->1212|>

除了空格就是e出现次数最多,密文的统计结果如下:

<|" "->219,"e"->120,"h"->84,"t"->80,"o"->70,"n"->67,"i"->67,"a"->54,"s"->51,"r"->38|>

如果有人对密文感兴趣的话,我就贴出来好了.密匙:"god",密文约翰福音第一章.

(The Gospel of John, chapter 1)
1 In the beginning the Word already existed. He was with God, and he was God.
2 He was in the beginning with God.
3 He created everything there is. Nothing exists that he didn't make.
4 Life itself was in him, and this life gives light to everyone.
5 The light shines through the darkness, and the darkness can never extinguish it.
6 God sent John the Baptist
7 to tell everyone about the light so that everyone might believe because of his testimony.
8 John himself was not the light; he was only a witness to the light.
9 The one who is the true light, who gives light to everyone, was going to come into the world.
10 But although the world was made through him, the world didn't recognize him when he came.
11 Even in his own land and among his own people, he was not accepted.
12 But to all who believed him and accepted him, he gave the right to become children of God.
13 They are reborn! This is not a physical birth resulting from human passion or plan, this rebirth comes from God.
14 So the Word became human and lived here on earth among us. He was full of unfailing love and faithfulness. And we have seen his glory, the glory of the only Son of the Father.

约翰福音 第一章
1 太初有道、道与神同在、道就是神。
2 这道太初与神同在。
3 万物是借着他造的.凡被造的、没有一样不是借着他造的。
4 生命在他里头.这生命就是人的光。
5 光照在黑暗里、黑暗却不接受光。
6 有一个人、是从神那里差来的、名叫约翰。
7 这人来、为要作见证、就是为光作见证、叫众人因他可以信。
8 他不是那光、乃是要为光作见证。
9 那光是真光、照亮一切生在世上的人。
10 他在世界、世界也是借着他造的、世界却不认识他。
11 他到自己的地方来、自己的人倒不接待他。
12 凡接待他的、就是信他名的人、他就赐他们权柄、作神的儿女。
13 这等人不是从血气生的、不是从情欲生的、也不是从人意生的、乃是从神生的。
14 道成了肉身、住在我们中间、充充满满的有恩典有真理。我们也见过他的荣光、正是父独生子的荣光。


P60:素数对的集合

3、7、109和673是非常特别的一组素数。任取其中的两个并且以任意顺序连接起来,其结果仍然是个素数。例如,选择7和109,我们得到7109和1097均为素数。这四个素数的和是792,这是满足这个性质的一组四个素数的最小和。

若有一组五个素数,任取其中的两个并且以任意顺序连接起来,其结果仍然是个素数,求这样一组素数的最小和。

似乎是上次那道的简单版,就取三位被多少多少除的那道.直接穷举肯定不行,C[n,5]的复杂度,简直是在开玩笑...

我们可以先写个朴素的判定:

foo[{a_, b_}] := FromDigits[IntegerDigits@a~Join~IntegerDigits@b];
fooQ = PrimeQ[foo@#] && PrimeQ[foo@Reverse@#] &;

一个素数二元组正反连起来还是个素数.然后我们可以试一个范围比如1万以下的质数.

炫酷的事情来了,我们把这些个二元组组成一个无向图,于是有关系的点就会成团,我们只要找正好含有5个点的团就行了!


连续计时24分15秒...啊咧,越来越慢了,就算我两题没做时间还是变长了,主要是分析过程越来越长了,没法看一眼出思路..."

欧拉挑战:入门4段

Aster 欧拉挑战 Leave a Comment

P41:全数字的素数

如果一个n位数恰好使用了1至n每个数字各一次,我们就称其为全数字的。例如,2143就是一个4位全数字数,同时它恰好也是一个素数。

最大的全数字的素数是多少?

n就是个7位数,因为当n为8或9时,无论怎么排都能被3整除.

事实上1, 3, 6, 10, 15, 21, 28, 36, 45里就俩合法的位数,穷举就行.


P42:编码三角形数

三角形数序列的第n项由公式tn = 1/2n(n+1)给出;因此前十个三角形数是:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
将一个单词的每个字母分别转化为其在字母表中的顺序并相加,我们可以计算出一个单词的值。例如,单词SKY的值就是 19 + 11 + 25 = 55 = t10。如果一个单词的值是一个三角形数,我们就称这个单词为三角形单词。

在这个16K的文本文件words.txt (右击并选择“目标另存为……”)中包含有将近两千个常用英文单词,这其中有多少个三角形单词?

就是那道求姓名值的变体,直接判断判别式是否是整数就行.

$$\begin{aligned}
&t = \frac{1}{2}n(n + 1)\\
&n = - \frac{1}{2}\left( {1 \pm \sqrt {8t + 1} } \right)\\
&\sqrt {8t + 1} \in N
\end{aligned} $$

我喜欢这个出题方式,直接Import它的网页就行.


P43:子串的可整除性

1406357289是一个0至9全数字数,因为它由0到9这十个数字排列而成;但除此之外,它还有一个有趣的性质:子串的可整除性。

记d1是它的第一个数字,d2是第二个数字,依此类推,我们注意到:

  • d2d3d4=406能被2整除
  • d3d4d5=063能被3整除
  • d4d5d6=635能被5整除
  • d5d6d7=357能被7整除
  • d6d7d8=572能被11整除
  • d7d8d9=728能被13整除
  • d8d9d10=289能被17整除

找出所有满足同样性质的0至9全数字数,并求它们的和。

有点复杂,十亿级别穷举肯定是不行的了.

要找一种方法来把这7个整除集合连起来咯.比如除17的集合找到了289,然后除13的集合就要找X28,比如728,然后除11的里再找....

就是构造一个函数numLink,取一个数给他的头上加数并检测合法性.最后全部全过程试完还合法的就是最终的结果了.


P44:五边形数

五边形数由公式Pn=n(3n−1)/2生成。前十个五边形数是:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …
可以看出P4 + P7 = 22 + 70 = 92 = P8。然而,它们的差70 − 22 = 48并不是五边形数。

在所有和差均为五边形数的五边形数对Pj和Pk中,找出使D = |Pk − Pj|最小的一对;此时D的值是多少?

不穷举的话就是解这种方程.

$$D = {P_k} - {P_j} = \sqrt {{{(6k - 1)}^2} \pm 12j(3j - 1)}  \in N$$

我反正不会解.所以还是穷举吧.最后还是用了编译...

还有一种思路就是先取集合然后组合判定,我本来也是这么写的,但是没跑出来,后来我看题解,别人PY写combinations秒出,我MMA写Subsets就卡题了,垃圾商业软件....

第二道了,这题当初我用Haskell也是一点事情也没有...MMA总是死在莫名其妙的地方...

特么MemberQ,IntegerQ也是莫名其妙的慢...第二种写法比第一种写法快5倍你敢信....

a=IntegerQ@Sqrt[#] & /@ Range[10000]; // RepeatedTiming
b=FractionalPart@Sqrt[# + .0] == 0 & /@ Range[10000]; // RepeatedTiming
a==b


P45:三角形数、五边形数和六角形数

三角形数、五边形数和六角形数分别由以下公式给出:

三角形数Tn=n(n+1)/21, 3, 6, 10, 15, …
五边形数Pn=n(3n−1)/21, 5, 12, 22, 35, …
六边形数Hn=n(2n−1)1, 6, 15, 28, 45, …

可以验证,T285 = P165 = H143 = 40755。

找出下一个同时是三角形数、五边形数和六角形数的数。

那就...求仨集合交集呗...穷举一下,记得大规模赋值用With.

幸好凑出来了,要是没凑出来就要分析解方程了...


P46:哥德巴赫的另一个猜想

克里斯蒂安·哥德巴赫曾经猜想,每个奇合数可以写成一个素数和一个平方的两倍之和。

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

最终这个猜想被推翻了。

最小的不能写成一个素数和一个平方的两倍之和的奇合数是多少?

Table[IntegerQ@Sqrt[(n-NextPrime[n])/2],{n,1,10000}]

嗯,我一定没吃药...题目都看错了...

$$\begin{aligned}
c &= p + 2{r^2}\\
r &= \sqrt {\frac{{c - p}}{2}} \in N
\end{aligned} $$

穷举所有的素数不是最近的素数...1-9999找到3个反例,取第二个,为啥...第一个不是1吗.

等会儿我在干嘛,我干嘛写Table,怪不得这么慢,这种找第一个的题不应该写NestWhile吗...

啥,你说循环?我们是高逼格的函数式编程,用了循环还怎么高冷的装逼...

除非要用到编译否则我就不写循环.NestWhile写起来不比循环爽吗...


P47:不同的质因数

首次出现连续两个数均有两个不同的质因数是在:

14 = 2 × 7
15 = 3 × 5
首次出现连续三个数均有三个不同的质因数是在:

644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
首次出现连续四个数均有四个不同的质因数时,其中的第一个数是多少?

素分解...F1秒了.....

你问NestWhile这么搞和While循环到底有啥区别么,好像确实没啥区别....

主要是循环没有返回值很蛋疼好不好(其实可以有),而且还要初始化(写法对就不用)....


P48:自幂

十项的自幂级数求和为 11 + 22 + 33 + … + 1010 = 10405071317。

求如下一千项的自幂级数求和的最后10位数字:11 + 22 + 33 + … + 10001000

快速幂模,F1秒之....


P49:素数重排

公差为3330的三项等差序列1487、4817、8147在两个方面非常特别:其一,每一项都是素数;其二,两两都是重新排列的关系。

一位素数、两位素数和三位素数都无法构成满足这些性质的数列,但存在另一个由四位素数构成的递增序列也满足这些性质。

将这个数列的三项连接起来得到的12位数是多少?

四位素数好像不多的样子,穷举一下吧.重排素数这玩意儿我前面是不是写过来着...

Equal@@Differences@Sort@#&可以用来对任意元数组进行等差检验


P50:连续素数的和

素数41可以写成六个连续素数的和:

41 = 2 + 3 + 5 + 7 + 11 + 13
在小于一百的素数中,41能够被写成最多的连续素数的和。

在小于一千的素数中,953能够被写成最多的连续素数的和,共包含连续21个素数。

在小于一百万的素数中,哪个素数能够被写成最多的连续素数的和?

穷举穷举

Partition[Prime~Array~1000, n, 1]生成一个n元的等差数列

Select那些求和之后还是素数的,并取这里面最小的那个.

a*^b a×10^b的语法糖...NestWhile...你还是理解成循环好了...

还有一种思路就是从2开始加,加到100万为止,Accumulate并且选出里面是质数的

然后3开始...5开始....其实差不多...


连续计时14分36秒...好像没啥难题啊,还有好多水题,用时竟然变多了..."

欧拉挑战:入门3段

Aster 欧拉挑战 Leave a Comment

P31:硬币求和

英国的货币单位包括英镑£和便士p,在流通中的硬币一共有八种:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)

以下是组成£2的其中一种可行方式:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

不限定使用的硬币数目,组成£2有多少种不同的方式?

这么久终于有要用到点数学的题目了.经典的生成函数应用.


P32:全数字的乘积

如果一个n位数包含了1至n的所有数字恰好一次,我们称它为全数字的;例如,五位数15234就是1至5全数字的。

7254是一个特殊的乘积,因为在等式39 × 186 = 7254中,被乘数、乘数和乘积恰好是1至9全数字的。

找出所有被乘数、乘数和乘积恰好是1至9全数字的乘法等式,并求出这些等式中乘积的和。

注意:有些乘积可能从多个乘法等式中得到,但在求和的时候只计算一次。

先来个判定函数fooQ来筛选那些乘数被乘数乘积1-9全数字的.

这个式子的两个乘数也不会很大.

两位数乘以三位数等于四位数,或一位数乘以四位数等于四位数,大的叫a小的叫b,穷举一下.


P33:消去数字的分数

49/98是一个有趣的分数,因为缺乏经验的数学家可能在约简时错误地认为,等式49/98 = 4/8之所以成立,是因为在分数线上下同时抹除了9的缘故。

我们也会想到,存在诸如30/50 = 3/5这样的平凡解。

这类有趣的分数恰好有四个非平凡的例子,它们的分数值小于1,且分子和分母都是两位数。

将这四个分数的乘积写成最简分数,求此时分母的值。

也就是解方程

$$\left\{ \begin{aligned}
&b = c\\
&\frac{{10a + b}}{{10c + d}} = \frac{a}{d} < 1\\
&0 < a,b,c,d \in N < 10
\end{aligned} \right.$$

然后转换成代码.其实...唔...我每次都要这么插一句话的原因是公式不能直接连代码高亮器,否则会被转译,要加一句废话当分隔符.


P34:各位数字的阶乘

145是个有趣的数,因为1! + 4! + 5! = 1 + 24 + 120 = 145。

找出所有各位数字的阶乘和等于其本身的数,并求它们的和。

注意:因为1! = 1和2! = 2不是和的形式,所以它们并不在讨论范围内。

和30题思路差不多吧,找上界,穷举,直接把代码搬过来改一下就能用了.


P35:圆周素数

197被称为圆周素数,因为将它逐位旋转所得到的数:197/971和719都是素数。

小于100的圆周素数有十三个:2、3、5、7、11、13、17、31、37、71、73、79和97。

小于一百万的圆周素数有多少个?

才一百万?不如穷举.....

都是一个思路,写个判定函数,Select...写了好几遍了.


P36:双进制回文数

十进制数585 = 10010010012(二进制表示),因此它在这两种进制下都是回文数。

找出所有小于一百万,且在十进制和二进制下均回文的数,并求它们的和。

(请注意,无论在哪种进制下,回文数均不考虑前导零。)

又是判定加Select....唉...套路,都是套路


P37:可截素数

3797有着奇特的性质。不仅它本身是一个素数,而且如果从左往右逐一截去数字,剩下的仍然都是素数:3797、797、97和7;同样地,如果从右往左逐一截去数字,剩下的也依然都是素数:3797、379、37和3。

只有11个素数,无论从左往右还是从右往左逐一截去数字,剩下的仍然都是素数,求这些数的和。

注意:2、3、5和7不被视为可截素数。

郁闷,我想了下我没法证明只有11个素数会这样...

反过来做呗,{2,3,5,7}往左加一位{13, 23, 43, 53, 73, 83, 17, 37, 47, 67, 97}就是,往右加一位{23, 29, 31, 37, 53, 59, 71, 73, 79}就是,然后在这个基础上再构造.

别问我为啥只要是n=5次,反正我加100次也是这个结果.除非我能想明白为啥只有11个这样的素数...

Intersection取交集,Total加起来,最后减去{0,2,3,5,7}这5个.


P38:全数字的倍数

将192分别与1、2、3相乘:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

连接这些乘积,我们得到一个1至9全数字的数192384576。我们称192384576为192和(1,2,3)的连接乘积。

同样地,将9分别与1、2、3、4、5相乘,得到1至9全数字的数918273645,即是9和(1,2,3,4,5)的连接乘积。

对于n > 1,所有某个整数和(1,2, … ,n)的连接乘积所构成的数中,最大的1至9全数字的数是多少?

穷举.....然后又是Select判定.....

我们所要寻找的答案至少要大于题目给出的那个数918273645,所以怎么着9开头;

然后因为n大于1,这个数不可能是五位数,所以范围就出来了[9000,9999]


P39:整数边长直角三角形

若三边长{a,b,c}均为整数的直角三角形周长为p,当p = 120时,恰好存在三个不同的解:

{20,48,52}, {24,45,51}, {30,40,50}
在所有的p ≤ 1000中,p取何值时有解的数目最多?

解个方程的事儿.

$$\begin{gathered}
\left\{ \begin{gathered}
{a^2} + {b^2} = {c^2}\\
p = a + b + c\\
p > c > b > a > 0\\
\end{gathered} \right.\\
\left\{ \begin{gathered}
0 < a \leqslant \left\lfloor {p - \frac{p}{{\sqrt 2 }}} \right\rfloor\\
b = \frac{{p(2a - p)}}{{2(a - p)}}\\
\end{gathered} \right.\\
\end{gathered} $$

翻成代码:


P40:钱珀瑙恩常数

将所有正整数连接起来构造的一个十进制无理数如下所示:

0.123456789101112131415161718192021…
可以看出小数点后第12位数字是1。

如果dn表示上述无理数小数点后的第n位数字,求下式的值:

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

我选择直接数...


连续计时10分54秒,没有压进10分钟有点遗憾.....思路倒是不难找,就是比如P38这种题真是阅读理解...

欧拉挑战:入门2段

Aster 欧拉挑战 Leave a Comment

P21:亲和数

记d(n)为n的所有真因数(小于n且整除n的正整数)之和。
如果d(a) = b且d(b) = a,且a ≠ b,那么a和b构成一个亲和数对,a和b被称为亲和数。

例如,220的真因数包括1、2、4、5、10、11、20、22、44、55和100,因此d(220) = 284;而284的真因数包括1、2、4、71和142,因此d(284) = 220。

求所有小于10000的亲和数的和。

我不喜欢这道题,因为里面的定义和Mathematica里的定义相冲.

不然可以写的更短一些.foo用来找出亲和数,然后剃掉完全数.


P22:姓名得分

在这个46K的文本文件names.txt(右击并选择“目标另存为……”)中包含了五千多个姓名。首先将它们按照字母序排列,然后计算出每个姓名的字母值,乘以它在按字母顺序排列后的位置,以计算出姓名得分。

例如,按照字母序排列后,位于第938位的姓名COLIN的字母值是3 + 15 + 12 + 9 + 14 = 53。因此,COLIN的姓名得分是938 × 53 = 49714。

文件中所有姓名的姓名得分之和是多少?

真心不知道这个是什么鬼格式,只能手动转化成列表了.复习下URLExecute操作.

字母值正好是ASCII码减去64.介绍下内积操作Inner,Inner作用于两个对齐的向量,大概就是取出两个元素,先使用前面那种算子运算,然后全部算完后用后面那种算子表示.Plus算子就把最后结果加起来,List算子的话就能变成一个列表.


P23:非盈数之和

完全数是指真因数之和等于自身的那些数。例如,28的真因数之和为1 + 2 + 4 + 7 + 14 = 28,因此28是一个完全数。

如果一个数的真因数之和小于n,那么n被称为亏数,反之则被称为盈数。

由于12是最小的盈数,它的真因数之和为1 + 2 + 3 + 4 + 6 = 16,所以最小的能够表示成两个盈数之和的数是24。通过数学分析可以得出,所有大于28123的数都可以被写成两个盈数的和;尽管我们知道最大的不能被写成两个盈数的和的数要小于这个值,但这是通过分析所能得到的最好上界。

找出所有不能被写成两个盈数之和的正整数,并求它们的和。

啊哈,又要用到DivisorSigma了,这次满足DivisorSigma[1, n] - n>n的叫做盈数.

然后上界他给了,那就直接Select.俩盈数之和,那就Tuples[list, 2]穷举所有组合然后Total求和.

但是,他求的是不能表示的那些数,那就对28123个数求补集Complement,最后还要求和.

很好奇28123这个数是怎么来的,只能看出这是个质数,我证了下只能证明两个盈数之和还是盈数,所以可能是用某种筛法证出来的.


P24:字典序排列

排列指的是将一组物体进行有顺序的放置。例如,3124是数字1、2、3、4的一个排列。如果把所有排列按照数字大小或字母先后进行排序,我们称之为字典序排列。0、1、2的字典序排列是:

012   021   102   120   201   210
数字0、1、2、3、4、5、6、7、8、9的字典序排列中第一百万位的排列是什么?

这个F1可能搞不定,不过Mathematica用的多的话是能知道Permutations给出的是字典序的.


P25:一千位斐波那契数

斐波那契数列是按如下递归关系定义的数列:
$$\begin{aligned}
{F_1}&= 1 \\
{F_2}&= 1 \\
{F_n}&= {F_{n - 1}}+{F_{n - 2}}
\end{aligned} $$

第一个有三位数字的项是第12项F12

在斐波那契数列中,第一个有1000位数字的是第几项?

还记得NestWhile吗?又用到了哦.

然后我被坑了一下,想了半天,发现1000位数是10^999...


P26:倒数的循环节

单位分数指分子为1的分数。分母为2至10的单位分数的十进制表示如下所示:

1/2= 0.5
1/3= 0.(3)
1/4= 0.25
1/5= 0.2
1/6= 0.1(6)
1/7= 0.(142857)
1/8= 0.125
1/9= 0.(1)
1/10= 0.1

这里0.1(6)表示0.166666…,括号内表示有一位循环节。可以看出,1/7有六位循环节。

找出正整数d < 1000,其倒数的十进制表示小数部分有最长的循环节。

RealDigits能给出循环小数,不过不能直接给出循环节.循环部分会由列表给出.

所以可以用模式匹配删掉不是列表的部分.然后剩下的就是循环节啦.

我好像又无视了小于号233333,幸好1000没有循环节.


P27:二次“素数生成”多项式

欧拉发现了这个著名的二次多项式:

n2 + n + 41
对于连续的整数n从0到39,这个二次多项式生成了40个素数。然而,当n = 40时,402 + 40 + 41 = 40(40 + 1) + 41能够被41整除,同时显然当n = 41时,412 + 41 + 41也能被41整除。

随后,另一个神奇的多项式n2 − 79n + 1601被发现了,对于连续的整数n从0到79,它生成了80个素数。这个多项式的系数-79和1601的乘积为-126479。

考虑以下形式的二次多项式:

  • n2 + an + b, 满足|a| < 1000且|b| < 1000
  • 其中|n|指n的模或绝对值
    例如|11| = 11以及|−4| = 4

这其中存在某个二次多项式能够对从0开始尽可能多的连续整数n都生成素数,求其系数a和b的乘积。

穷举吗,可是有400万种组合啊...好吧我承认卡题了...

然后做完下面的题回过头来看,MDZZ.

$${n^2} + n + 41 \equiv {n^2} - 79n + 1601$$

这俩产生的素数个数相同啊,都是80个啊,欧拉找的那个是[-40,39]成立的,然后平移40格下就得到了右式

所以,其实问的就是,平移多少格正好生成b<1000还生成尽可能多的素数.手算都可以啊,水题.

$$\begin{aligned}
{\left( {n - k} \right)^2} + \left( {n - k} \right) + 41 &= 0,0 < k < 40 \\
{n^2} + \left( {1 - 2k} \right)n + \left( {{k^2} - k + 41} \right) &= 0\\
\left| {{k^2} - k + 41} \right| &< 1000\\
k \leqslant \left\lfloor {\frac{{1 + \sqrt {3837} }}{2}} \right\rfloor &= 31
\end{aligned}$$

硬要写出程序的话


P28:螺旋数阵对角线

从1开始,按顺时针顺序向右铺开的5 × 5螺旋数阵如下所示:

$$\begin{array}{*{20}{c}}
{\color{Red} {21}}&{22}&{\color{Red} {23}}&{24}&{\color{Red} {25}} \\
{20}&{\color{Red} 7}&8&{\color{Red} 9}&{10} \\
{19}&6&{\color{Red} 1}&2&{11} \\
{18}&{\color{Red} 5}&4&{\color{Red} 3}&{12} \\
{\color{Red} {17}}&{16}&{15}&{14}&{\color{Red} {13}}
\end{array}$$

可以验证,该数阵对角线上的数之和是101。

以同样方式构成的1001 × 1001螺旋数阵对角线上的数之和是多少?

唔,观察法,差是2,2,2,2,4,4,4,4,6,6,6,6,8,8,8,8.....

好吧其实我不是一上来就想到观察法的,我一上来在想怎么生成这个矩阵,然后稍微推导了一下,最后化简的时候才发现这个规律的.

我必须要祭出我研究了半天的螺旋矩阵,虽然算法效率捉鸡至极.

SpiralMatrix[n_?OddQ]:=Permute[Range[n^2],Accumulate@Take[Join[{n^2+1}/2,
Flatten@Table[(-1)^j i,{j,n},{i,{-1,n}},{j}]],n^2]]~Partition~n;
SpiralMatrix[n_]:=SpiralMatrix[n+1][[1;;-2,2;;-1]]


P29:不同的幂

考虑所有满足2 ≤ a ≤ 5和2 ≤ b ≤ 5的整数组合生成的幂ab

$$\begin{array}{llll}
2^2=4 & 2^3=8 & 2^4=16 & 2^5=32 \\
3^2=9 & 3^3=27 & 3^4=81 & 3^5=243 \\
4^2=16 & 4^3=64 & 4^4=256 & 4^5=1024 \\
5^2=25 & 5^3=125 & 5^4=625 & 5^5=3125
\end{array}$$

如果把这些幂按照大小排列并去重,我们得到以下由15个不同的项组成的序列:

$$4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125$$

在所有满足$2 ≤ a ≤ 100$和$2 ≤ b ≤ 100$的整数组合生成的幂ab排列并去重所得到的序列中,有多少个不同的项?

我们可是科学计算软件,100^100算什么大数,上穷举,不虚的.


P30:各位数字的五次幂

令人惊讶的是,只有三个数可以写成它们各位数字的四次幂之和:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

由于1 = 14不是一个和,所以这里并没有把它包括进去。

这些数的和是1634 + 8208 + 9474 = 19316。

找出所有可以写成它们各位数字的五次幂之和的数,并求这些数的和。

n位数的话最大值就是10n-1,而各位数字五次方之和最大就是n×95

解个方程求出上界.上界不算大,穷举呗,fooQ进行判定,Select选一下就行了呗.


连续计时12分44秒.卡了P27,P28.其他5分钟内秒杀.

欧拉挑战:入门1段

Aster 欧拉挑战 Leave a Comment

P11:方阵中的最大乘积

有一个20×20方阵中,在这个方阵中,四个在同一方向(从下至上、从上至下、从右至左、从左至右或者对角线)上相邻的数的乘积最大是多少?

似乎只能暴力遍历,练习一下Import,然后就变成了个矩阵.

一共有四个方向要遍历,横向,竖向,主对角方向和副对角方向.所以我们考虑的是把所有的行啊,列啊,对角线啊,全部抽出来合并成一个列表.

这样就变成了长短不一的小列表的列表了.然后每个小列表的最大乘积这个之前第8题已经搞定了.分别求出最大值然后求这些最大值中的最大值就行了.

p12:高度可约的三角形数

三角形数数列是通过逐个加上自然数来生成的。三角形数数列的前十项分别是:

$$1,3,6,10,15,21,28,36,45,55 \ldots  \ldots $$

让我们列举出前七个三角形数的所有约数:

  •  1: 1
  •  3: 1,3
  •  6: 1,2,3,6
  • 10: 1,2,5,10
  • 15: 1,3,5,15
  • 21: 1,3,7,21
  • 28: 1,2,4,7,14,28

我们可以看出,28是第一个拥有超过5个约数的三角形数。

第一个拥有超过500个约数的三角形数是多少?

多用用F1,早点认识DivisorSigma这个函数,这是个积性函数,后面很多数论题都要用到这个.

虽然有数论解法,不过我们还是先用穷举好了.一般这种题后面还会出现无法穷举解决的加强型问题.永远记住你的时间远比计算机的时间值钱.

NestWhile还记得不,我让你记住的来着.

P13:大和

计算出一百个50位数的和的前十位数字。

好吧我直接复制Import 30s就搞定了,不过我还是觉得我得教点什么,就教点网页读取与处理吧,就像这样:

P14:最长考拉兹序列

在正整数集上定义如下的迭代序列:

n → n/2 (若n为偶数)
n → 3n + 1 (若n为奇数)

从13开始应用上述规则,我们可以生成如下的序列:

$$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$$

可以看出这个序列(从13开始到1结束)共有10项。尽管还没有被证明,但我们普遍认为,从任何数开始最终都能迭代至1(“考拉兹猜想”)。

从小于一百万的哪个数开始,能够生成最长的序列呢?

注: 序列开始生成后允许其中的项超过一百万。

本题不建议用Mathematica做,跳过.

<< ExampleData/Collatz.m
Table[Length@Collatz[i], {i, 10^4 - 1}]

算了将近4秒钟的时候我就感觉不对劲了,不用编译药丸...

P15:网格路径

从一个2×2方阵的左上角出发,只允许向右或向下移动,则恰好有6条通往右下角的路径。

对于20×20方阵来说,这样的路径有多少条?

呃,高中数学排列组合,不是很想解释...

P16:幂的数字和

215 = 32768,而32768的各位数字之和是 3 + 2 + 7 + 6 + 8 = 26。

21000的各位数字之和是多少?

多用F1.

P17:表达数字的英文字母计数

如果把1到5写成英文单词,分别是:one, two, three, four, five,这些单词一共用了3 + 3 + 5 + 4 + 4 = 19个字母。

如果把1到1000都写成英文单词,一共要用多少个字母?

注意: 不要算上空格和连字符。例如,342(three hundred and forty-two)包含23个字母,而115(one hundred and fifteen)包含20个字母。单词“and”的使用方式遵循英式英语的规则。

如果不懂英语语法的话...跳过吧...没啥意思...

IntegerName并不符合语法.答案里这个函数我抽了出来整合进了程序包,我后来把语法扩展到了10^72以下,一般认为10^6以下应该读自然语法,10^9以上应该读科学记法(无and).

不过这个并没有什么软用,毕竟有Wolfram Alpha.

words[x_] :=
Nest[StringReplace[#,
n : (DigitCharacter ..) :>
WolframAlpha["spell " <> n, {{"Result", 1}, "Plaintext"}]] &,
ToString@x, 2]
words[123456789101112]

P18:最大路径和 I

从下面展示的三角形的顶端出发,不断移动到在下一行与其相邻的元素,能够得到的最大路径和是23。

3
7 4
2 4 6
8 5 9 3
如上图,最大路径和为 3 + 7 + 4 + 9 = 23。

求从下面展示的三角形顶端出发到达底部,所能够得到的最大路径和:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
注意: 在这个问题中,由于只有16384条路径,通过尝试所有的路径来解决问题是可行的。但是,对于第67题,虽然是一道相同类型的题目,但是三角形将拥有一百行,此时暴力破解将不能解决,而需要一个更加聪明的办法

讲真,这个聪明的办法并不难想,对于上层的每一个数都选下层较大的那个数走好了.

解释下state的结果是选择不同路径的结果,前一个是往左走的和,后一个是往右走的和.

choose就是取结果大的那个,FoldPair就是两层两层的比较的意思,FoldPair是个二元运算符.

P19:数星期日

下列信息是已知的,当然你也不妨自己再验证一下。

1900年1月1日是星期一。

  • 三十天在九月中,
  • 四六十一也相同。
  • 剩下都是三十一,
  • 除去二月不统一。
  • 二十八天平常年,
  • 多加一天在闰年。

闰年指的是能够被4整除却不能被100整除的年份,或者能够被400整除的年份。
在二十世纪(1901年1月1日到2000年12月31日)中,有多少个月的1号是星期天?
F1.......不想在这里深入讲,想自己算的话,右上搜索日期计数.

P20:阶乘数字和

n! 的意思是 n × (n − 1) × … × 3 × 2 × 1

例如,10! = 10 × 9 × … × 3 × 2 × 1 = 3628800,所以10!的各位数字和是 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27。

求出100!的各位数字和。

和16题又有什么区别呢?


连续计时7分41秒,P14莫名被坑....P17未计时.

欧拉挑战:入门0段

Aster 欧拉挑战 Leave a Comment

P1:3的倍数和5的倍数

如果我们列出10以内所有3或5的倍数,我们将得到3、5、6和9,这些数的和是23。

求1000以内所有3或5的倍数的和。

分别把3和5的倍数的集合穷举出来,然后就俩集合的并集就行了.注意1000以内,最大是999

P2:偶斐波那契数

斐波那契数列中的每一项都是前两项的和。由1和2开始生成的斐波那契数列前10项为:

$$1,2,3,5,8,13,21,34,55,89 \ldots  \ldots $$

考虑该斐波那契数列中不超过四百万的项,求其中为偶数的项之和。

练习F1,输入斐波那契,记住一个常用写法NestWhile[#+1&,1,Fibonacci[#]<4000000&]

很多时候有些函数比如自己写的函数是没有反函数没法Reduce的,可以用这个写法穷举上界时的x值.

上界有了直接Select就行了.

P3:最大质因数

13195的所有质因数为5、7、13和29。

600851475143最大的质因数是多少?

练习F1的使用,查找分解,然后发现FactorInteger,FactorInteger返回一个二元数组列表,前一个是因子后一个是次数,所以用First提取因子,Max找到最大因子.

P4:最大回文乘积

回文数就是从前往后和从后往前读都一样的数。由两个2位数相乘得到的最大回文乘积是 9009 = 91 × 99。

找出由两个3位数相乘得到的最大回文乘积。

1000*1000才10^6,小于100万的题我们穷举就行了.不过不要傻乎乎的写Table[i j, {i, 100, 999}, {j, 100, 999}],i j=j i,这不多算了一遍吗.

写Table[Table[i j,{j,i,99}],{i,10,99}],然后有一个语法糖可以等价写成

Table[i j,{i,10,99},{j,i,99}]

然后造一个函数ReverseQ判定是否是个回文数.然后就是Select判定取值,然后Max取得最大值.

P5:最小倍数

2520是最小的能够被1到10整除的数。

最小的能够被1到20整除的正数是多少?

也就是求最小公倍数咯,练习F1的使用.

P6:平方的和与和的平方之差

前十个自然数的平方的和是

$${1^2} + {2^2} +  \ldots  + {10^2} = 385$$

前十个自然数的和的平方是

$${(1 + 2 +  \ldots  + 10)^2} = {55^2} = 3025$$

因此前十个自然数的平方的和与和的平方之差是 3025 − 385 = 2640。

求前一百个自然数的平方的和与和的平方之差。

小于百万,直接穷举.哦不,练习一下公式推导好了.好歹挂着个数学软件的名头.

FullSimplify[Sum[i, {i, 1, n}]^2 - Sum[i^2, {i, 1, n}]]

$$f(n) = \frac{1}{{12}}(n - 1)n(n + 1)(3n + 2)$$

然后手算都可以.补一个穷举.

P7:第10001个素数

列出前6个素数,它们分别是2、3、5、7、11和13。我们可以看出,第6个素数是13。

第10,001个素数是多少?

F1用起来.

P8:连续数字最大乘积

给定了一个1000位正整数,找出这个1000位正整数中乘积最大的连续13个数字,求它们的乘积。

这道题确实能优化,但是问题规模不大就浪费时间了.

直接一位一位的连续读13个数就行了,然后乘起来比大小呗.

P9:特殊毕达哥拉斯三元组

毕达哥拉斯三元组是三个自然数a < b < c组成的集合,并满足

$${a^2} + {b^2} = {c^2}$$

例如${3^2} + {4^2} = 9 + 16 = 25 = {5^2}$

有且只有一个毕达哥拉斯三元组满足$a + b + c = 1000$。求这个三元组的乘积$abc$。

我们要跑穷举吗?跑什么跑,不是说了只有一个解吗,那就解方程啊.

$$\begin{cases}
&{a^2} + {b^2} = {c^2}\\
&a + b + c = 1000 \\
&0 < a < b < 1000 \\
&\{ a,b,c\} \in N\\
\end{cases}$$

直接把方程输进Mathematica.

P10:素数的和

所有小于$10$的素数的和是$2 + 3 + 5 + 7 = 17$.

求所有小于两百万的素数的和。

当然可以用上面的NestWhile测试下x的上界,不过多用用F1你会发现一个叫PrimePi的函数.


连续计时,3分23秒解决.