欧拉挑战:入门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秒,无妄之灾...

发表评论