EulerProject

# P111: 有重复数字的素数

TIP

考虑一个有重复数字的 4 位素数, 显然这 4 个数字不能全都一样: 1111 被 11 整除, 2222 被 22 整除, 依此类推; 但是, 有 9 个 4 位素数包含有 3 个 1:

我们记 是 n 位素数中数字 d 重复出现的最多次数, 是这类素数的个数, 而 是这类素数的和.

因此 是 4 位素数中数字 1 重复出现的最多次数, 有 个这类素数, 而它们的和是 .

还能得出, 对于 , 在 4 位素数中最多重复出现 次, 但是有 N(4, 0) = 13 个这类素数.

同样地, 我们可以得到 4 位素数的如下结果.

数字 d M(4, d) N(4, d) S(4, d)
2 13 67061
1 3 9 22275
2 3 1 2221
3 3 12 46214
4 3 2 8888
5 3 1 5557
6 3 1 6661
7 3 9 57863
8 3 1 8887
9 3 7 48073

对于 d = 0 至 9, 所有 的和为 273700.

求所有 的和.

传说中的数位 dp 吗...

先生成数位都相同的数, 然后生成以每一个数作为基础, 用其他数字进行替换的列表, 并判定质数.

先尝试替换 1 位数, 若没有质数 (空列表), 则尝试 2 位数, 3 位数, 直到获得第一个非空列表为止

当然越往后这个需要筛选的列表就越大, 基本上妥妥的炸内存...

不过这个题很幸运最多只要替换两位, well, 不然就不是这个难度的题了 233.

GenAll[n_,d_,len_]:=Flatten[Permutations/@Table[Join[Table[d,{n}],IntegerDigits@k],{k,0,10^(len-n)-1}],1]
GetPrime[n_,d_,len_]:=DeleteDuplicates[Select[FromDigits/@GenAll[n,d,len],PrimeQ[#]&&#>10^(len-1)&]]
Try[len_,d_]:=Catch@Do[If[(ans=GetPrime[n,d,len])=!={},Throw[ans]],{n,len-1,0,-1}];
Total[Table[GetFirst[10, d],{d,0,9}],2]
  • 计时: 25:27.14

# P112: 弹跳数

Bouncy numbers

从左往右, 如果每一位数字都大于等于其左边的数字, 这样的数被称为上升数, 比如 .

同样地, 如果每一位数字都大于等于其右边的数字, 这样的数被称为下降数, 比如 .

如果一个正整数既不是上升数也不是下降数, 我们就称之为 "弹跳" 数, 比如 .

显然不存在小于一百的弹跳数, 而在小于一千的数中有略超过一半的弹跳数.

事实上, 使得弹跳数的比例恰好达到 的最小数是 .

令人惊奇的是, 弹跳数将变得越来越普遍, 到 时, 弹跳数的比例恰好等于 .

找出使得弹跳数的比例恰好为 的最小数.

简单地阅读理解我是一个字都不想多说了...

都一百多号了...

外加还要记录状态...

这很不函数式...

bouncy = 0;
Catch@Do[
	id = IntegerDigits[n];
	rid = Reverse[id];
	If[!(OrderedQ[id] || OrderedQ[rid]), bouncy += 1];
	If[bouncy / n>= 0.99, Throw[n]],
	{n, 100000000}
]
  • 计时: 16:40.77

# P113: 非弹跳数

Non-bouncy numbers

从左往右, 如果每一位数字都大于等于其左边的数字, 这样的数被称为上升数, 比如 .

同样地, 如果每一位数字都大于等于其右边的数字, 这样的数被称为下降数, 比如 .

如果一个正整数既不是上升数也不是下降数, 我们就称之为 "弹跳" 数, 比如 .

随着 的增长, 小于 的弹跳数的比例也随之增长;

在小于一百万的数中, 只有 个非弹跳数, 而小于 的数中只有 个非弹跳数.

在小于 的数中有多少个非弹跳数?

这个可以叫数论题吗...

还是江苏高考找规律题.....

位数为 的上升数有 个, 下降数则是 个;

然后再减去类似 这 种既是上升数也是下降数的情况;

Sum[Binomial[n + 9, 9] + Binomial[n + 8, 8] - 1 - 9, {n, 100}]

# P114: 方格组合计数 I

Counting block combinations I

用黑色方块和最短长度为 的红色方块摆成长度为 的一行, 要求任意两个红色方块 (长度可以不同) 之间至少有一个黑色方块, 恰好有 种不同的摆法.

若要摆成长度为 的一行, 有多少种不同的摆法?

注意: 尽管上述样例没有混用不同长度的方格, 但这样做是允许的.

例如, 要摆成长度为 的一行, 你可以用 红红红黑红红红红.

时

  • 只有全部填充红 1 种摆法, .

时

  • 当最左为 1 个黑块, 则加上长度为 的摆法
  • 当最左为红块时
    • 一种情况是红块长度为 $n $, 占据整个行
    • 另一类情况是, 一个长度小于 的红块长度为 , 后面紧跟一个黑块, 再加上剩余长度就是 , 求个和.

a_n=\begin{cases} 1 & n = 0,1,2 \\ \displaystyle a_{n-1}+1+\sum_{i=3}^{n}a_{n-1-i}& \mathtt{otherwise}\\ \end{cases}

当然这个递推不太好解, 那就别解了, 原样输入一遍呗...

a[0 | 1 | 2] = 1;
a[3] = 2;
a[n_] := a[n] = a[n - 1] + Sum[a[k], {k, 0, n - 4}] + 1;
a[50]

除此以外没事干还可以写生成函数:

SeriesCoefficient[1 / (1 / (1 + Sum[x^i, {i, 3, 50}]) - x), {x, 0, 50}]

或者线性递推:

LinearRecurrence[{2, -1, 0, 1}, {1, 1, 2, 4}, 50] // Last

如果像我一样你牛逼的木有的话, 其实是可以解出来的, 超几何函数解如下:

HypergeometricPFQ[{-(1/4)-n/4,1/4-n/4,1/2-n/4,-(n/4)},{1/2,-(1/2)-n/2,-(n/2)},16]/.n->50

# P115: 方格组合计数 II

Counting block combinations II

用黑色方块和最短长度为 的红色方块摆成长度为 的一行, 要求任意两个红色方块 (长度可以不同) 之间至少有一个黑色方块.

我们用摆法计数函数 代表符合上述要求的摆法数目.

例如, 以及 .

也就是说, 当 时, 可以看出 是使得摆法计数函数首次超过一百万的最小值.

同样地, 当 时, 可以验证 以及 , 因此 是使得摆法计数函数首次超过一百万的最小值.

当 时, 求使得摆法计数函数首次超过一百万的最小 值.

同上, 这回是真的没法解了, 不过用生成函数的话...

嘿嘿, 那还是一模一样的...

a_n=\begin{cases} 1 & n \leq m \\ \displaystyle a_{n-1}+1+\sum_{k=0}^{n-m-1}a_{k}& \mathtt{otherwise}\\ \end{cases}

f[n_, m_] := SeriesCoefficient[1 / (1 / (1 + Sum[x^i, {i, m, n}]) - x), {x, 0, n}];
Do[If[f[n, 50] > 1*^6, Return[n]], {n, 50, 10^3}]

# P116: 红色, 绿色或蓝色的地砖

Red, green or blue tiles

将一行五块黑色方形地砖的一部分替换成红色 (长度为 2), 绿色(长度为 3) 或蓝色 (长度为 4) 的地砖.

如果只使用红色地砖, 一共有 种不同的替换方式.

如果只使用绿色地砖, 一共有 种不同的替换方式.

如果只使用蓝色地砖, 一共有 种不同的替换方式.

假定颜色不能混合使用, 一共有 种方式替换一行五块黑色地砖.

假定颜色不能混合使用, 且至少使用一种彩色地砖, 一共有多少种方式替换一行五十块黑色地砖?

这.... 难度是倒退的吗...

\begin{aligned} R_n &=R_{n-1}+R_{n-2}+1\\ G_n&=G_{n-1}+G_{n-3}+1\\ B_n&=B_{n-1}+B_{n-4}+1\\ \end{aligned}

当然我们知道类斐波那契数列 的生成函数解可以写成:

至少使用一种颜色, 也就是不能全黑, 最终结果减 , 或者生成函数加一个修正项 

SeriesCoefficient[Sum[1 / (z - 1) + 1 / (1 - z - z^m), {m, {2, 3, 4}}], {z, 0, 50}]

# P117: 红色, 绿色和蓝色的地砖

Red, green, and blue tiles

使用黑色地砖, 长度为 的红色地砖, 长度为 的绿色地砖, 长度为 的蓝色地砖的组合, 一共有恰好 种不同的方式铺满长度为 的一行.

一共有多少种不同的方式铺满长度为 的一行?

可能..... 难度真的是倒退的吧....

解出来就是:

Coefficient[Series[1 / (1 - (z + z^2 + z^3 + z^4)), {z, 0, 50}], z, 50]

# P118: 全数字素数集合

TIP

使用 1 至 9 的全部数字, 并自由连接起来组成十进制整数, 可以构造不同的集合. 其中一个集合 {2,5,47,89,631} 非常有趣, 因为它的所有元素都是素数.

有些集合包含数字 1 至 9 恰好各一次, 且所有元素都是素数, 这样的集合有多少个?

好像, 得穷举一遍吧...

不过这个鬼畜的集合到底怎么生成啊...

查了半天发现这个叫做贝尔数 Bell Number, 哦, 我还真没用过......

所以一共有 BellB[9]=21147 种切分, 可以用 Combinatorica`SetPartitions 获得全部切分...

噢耶, Mathematica 真是老给力了!

然后全排列一下也就 76 7382 3360 种组合吧......

头疼...

<<Combinatorica`
f[x_]:=f[x]=Sum[Boole@PrimeQ@FromDigits@i,{i,Permutations@x}]
Total[Fold[If[#1!=0,#1 f[#2],0]&,1,#]&/@SetPartitions@9]
  • 计时: 85:21.84

# P119: 数字和的幂

TIP

512 是一个有趣的数, 因为它等于其各位数字和的幂: 5 + 1 + 2 = 8, 而 8^3 = 512. 拥有同样性质的数的另一个例子是 614656 = 28^4.

记 a_n 是这类数中的第 n 个, 并且约定一个数至少需要两位数字才有各位数字和.

已知 a_2 = 512 以及 a_10 = 614656.

求 a_30.

生成充分多的数, 然后过滤一波呗....

mQ[{n_,m_}]:=Plus@@IntegerDigits[n^m]==n
pos=Power@@@Select[Flatten[Outer[List,Range[2,100],Range[10]],1],mQ];
Select[Sort@pos,IntegerLength[#]>1&][[30]]
  • 计时: 7:20.89

# P120: 平方余数

TIP

记 是 被 除所得的余数.

例如, 如果 而 , 则 . 随着 的变化, 也会随之变化, 但是对 , 可以得出 .

对于 , 求 .

哟, 又是一道高考题, 两边展开一下先

\begin{aligned} (a+1)^n \bmod a^2 &\equiv 1+an \qquad\quad\ \, \bmod a^2\\ (a-1)^n\bmod a^2 &\equiv (-1)^{n}(1-an) \bmod a^2\\ \end{aligned}

因此 意义下就有:

(a-1)^n + (a+1)^n\equiv\begin{cases} 2an & n\in\mathtt{odd}\\ 1 & n\in\mathtt{even}\\ \end{cases}

所以我们现在可以不管偶数的情况了.

接下来最大化

两边模掉一个 , 变成

时, 取 , 此时

的话, 取 , 此时

也就是说

这个数列怎么解的来着... 错位相减法??

最后勉为其难的编个程...

Sum[a^2 - 2 a, {a, 4, 1000, 2}] + Sum[a^2 - a, {a, 3, 1000, 2}]
1/24 (3-14 k-6 k^2+8 k^3-3 (-1)^k (1+2 k))/.k->1000
  • 计时: 27:49.22
编号 计时
P111
P112
P113
P114 36:29
P115 12:31
P116 9:01
P117 5:21
P118
P119
P120 27:49

← Level121-130 →