EulerProject

# P31: 硬币求和

Coin sums

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

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

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

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

m = {1, 2, 5, 10, 20, 50, 100, 200};
Coefficient[Series[1 / Product[1 - x^m[[i]], {i, 8}], {x, 0, 200}], x^200]

# P32: 全数字的乘积

Pandigital products

如果一个 位数包含了 至 的所有数字恰好一次, 我们称它为全数字的;

例如, 五位数 就是 至 全数字的.

是一个特殊的乘积, 因为在等式 中, 被乘数, 乘数和乘积恰好是 至 全数字的.

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

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

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

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

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

fooQ = Union[IntegerDigits[#1], IntegerDigits[#2], IntegerDigits[#1 #2]] == Range[9]&;
Total[Union@@Table[If[a * b <= 9999 && fooQ[a, b], a * b, 0], {a, 100, 9999}, {b, 1, 99}]]

# P33: 消去数字的分数

Digit cancelling fractions

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

我们也会想到, 存在诸如 这样的平凡解.

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

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

也就是解方程

\begin{cases} &b = c\\ &\dfrac{10a + b}{10c + d} = \dfrac{a}{d} < 1\\ &0 < a,b,c,d \in N < 10 \end{cases}

然后转换成代码.

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

FindInstance[(10 a+b)/(10 c+d)==a/d<1&&b==c&&0<a<10&&0<b<10&&0<c<10&&0<d<10,{a,b,c,d},Integers,4]

# P34: 各位数字的阶乘

Digit factorials

是个有趣的数, 因为 .

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

注意: 因为 和 不是和的形式, 所以它们并不在讨论范围内.

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

fooQ = Total[(IntegerDigits@#)!] == #&;
max = First[n /. NSolve[{10^n == 9!n, n > 1}, n]];
Total[Select[Range[10, Floor[10^max]], fooQ]]

# P35: 圆周素数

Circular primes

被称为圆周素数, 因为将它逐位旋转所得到的数: 都是素数.

小于 的圆周素数有十三个: 和 .

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

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

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

fooQ := # == NestWhile[RotateLeft, #, PrimeQ[FromDigits[#]]&, 1, Length[#]]&;
Length@Select[IntegerDigits[Array[Prime, PrimePi[10^6]]], fooQ]

# P36: 双进制回文数

Double-base palindromes

在这两种进制下都是回文数.

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

注意: 无论在哪种进制下, 回文数均不考虑前导零.

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

Total@Select[Range[10^6], IntegerDigits[#, 2] == Reverse[IntegerDigits[#, 2]] && IntegerDigits[#] == Reverse[IntegerDigits[#]]&]

# P37: 可截素数

Truncatable primes

有着奇特的性质.

不仅它本身是一个素数, 而且如果从左往右逐一截去数字, 剩下的仍然都是素数: ;

同样地, 如果从右往左逐一截去数字, 剩下的也依然都是素数: .

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

注意: 不被视为可截素数.

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

反过来做呗, {2,3,5,7}

往左加一位就是 {13, 23, 43, 53, 73, 83, 17, 37, 47, 67, 97};

往右加一位就是 {23, 29, 31, 37, 53, 59, 71, 73, 79};

然后在这个基础上再构造.

别问我为啥只要是 次, 反正我加 次也是这个结果.

除非我能想明白为啥只有 个这样的素数...

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

fooQ[a_, b_] := Select[Plus@@@Tuples@{# a, b^#2 Range@9}, PrimeQ]&;
PrimeList[x__, n_] := Drop[Join@@FoldList[fooQ@x, {0}, 0 ~ Range ~ n], 2];
Tr[Intersection[PrimeList[1, 10, 5], PrimeList[10, 1, 5]]]

# P38: 全数字的倍数

Pandigital multiples

将 分别与 相乘:

连接这些乘积, 我们得到一个 至 全数字的数 .

我们称 为 和 的连接乘积(Concatenated Product).

同样地, 将 分别与 相乘, 得到 至 全数字的数 , 即是 和 的连接乘积.

对于 , 所有某个整数和 的连接乘积所构成的数中, 最大的 至 全数字的数是多少?

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

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

然后因为 , 这个数不可能是五位数, 所以范围就出来了 

fooQ = Sort@(IntegerDigits[#] ~ Join ~ IntegerDigits[2 #]) == Range[1, 9]&
list = Select[Range[9000, 9999], fooQ]
Row[Join@@IntegerDigits[Max@list {1, 2}]]

# P39: 整数边长直角三角形

Integer right triangles

设三边长 均为整数的直角三角形周长为 , 当 时, 恰好存在三个不同的解:

在所有的 中, 取何值时有解的数目最多?

解个方程的事儿.

$$\begin{cases} a^2 + b^2 = c^2\ p = a + b + c\ p > c > b > a > 0\ \end{cases}\$$

解得:

$$\begin{cases} 0 <a \leqslant \left\lfloor {p - \dfrac{p}{\sqrt 2 }} \right\rfloor\ b = \dfrac{p(2a - p)}{2(a - p)}\ \end{cases}\ $$

翻成代码:

a = Floor[p(1 - 1 / Sqrt[2])];
b[a_, p_] := Table[(2i - p)p / (2i - 2p), {i, 1, a}];
Last@Ordering@Table[Total@Boole[IntegerQ /@ b[a, p]], {p, 1, 1000}]

# P40: 钱珀瑙恩常数

Champernowne's constant

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

可以看出小数点后第 位数字是 .

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

我选择直接数...

Times@@RealDigits[ChampernowneNumber[10], 10, 10^6][[1, 10^Range[0, 6]]]

连续计时 10 分 54 秒, 没有压进 10 分钟有点遗憾.....

思路倒是不难找, 就是比如 P38 这种题真是阅读理解...

← Level41-50 →