Aster 未完成 Leave a Comment

P171:寻找数字平方和为平方数的数

对于正整数n,记f(n)为n(十进制表示下)的各位数的平方和,例如

f(3) = 32 = 9,
f(25) = 22 + 52 = 4 + 25 = 29,
f(442) = 42 + 42 + 22 = 16 + 16 + 4 = 36

找出所有满足0 < n < 1020,且各位数字平方和为平方数的数n,求出它们的和的最后九位数字。

 

 

 

 

 

 

 

欧拉挑战:初阶6段

Aster 未完成 Leave a Comment

P161:三联骨牌

三联骨牌是由三个正方形方块拼接而成的骨牌,它一共有两种基本形状:

如果计入旋转,则一共有六种可能的形状:

任何n乘m的方阵,只要nxm能够被3整除,就能用三联骨牌拼出来。
如果我们认为翻转或旋转是不同的拼法,那一个2乘9的方阵有一共有41种拼法:

一个9乘12的方阵有多少种拼法?

 

 

 

P162:十六进制数

十六进制数系统使用16个不同的数字:

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
十六进制数AF在十进制下等于10x16+15=175。

三位十六进制数10A,1A0,A10和A01都包含数字0,1和A。
和十进制下一样,在十六进制中没有前导零。

有多少至多十六位的十六进制数同时包含0,1和A?
用十六进制数表示你的答案。

(A,B,C,D,E和F均为大写字母,没有前导零或末尾标识符来表明该数字为十六进制,例如,1A3F不能写成:1a3f或0x1a3f或$1A3F或#1A3F或0000001A3F)

 

P163:纵横交错的三角形

考虑一个等边三角形,从三角形的每个顶点向对边的中点引一条线段,构成如下图所示的1级三角形。

我们可以从这个三角形中数出16个不同形状、不同大小、不同方向、不同位置的三角形。使用1级三角形作为材料,我们可以构成更大的三角形,比如右边的2级三角形。在2级三角形中可以输出一百零四个不同形状、不同大小、不同方向、不同位置的三角形。

可以看出一个2级三角形包含有4个1级三角形。一个3级三角形包含有9个1级三角形,而一个n级三角形包含有n2个1级三角形。

如果我们用T(n)表示n级三角形中能够数出的三角形个数,那么

T(1) = 16
T(2) = 104

求T(36)。

 

 

 

 

P164:没有连续三位数字的和超过给定值的数

有多少个20位数字n(不包括前导0)满足,不存在连续三位数字的和超过9?

 

 

P165:交点

一条线段由其两个端点唯一决定。考虑平面几何中的两条线段,一共有如下三种可能性:
两条线段没有、有一个或者有无数个交点。

进一步地,当两条线段恰好有一个交点时,可能这个交点是其中一条或两条的端点。如果这个交点不是任一条线段的端点,那它一定是这两条线段的内点。
当两条线段L1和L2的交点T是这两条线段唯一的交点且是这两条线段的内点时,我们称T为这两条线段的真交点。

考虑以下三条线段L1,L2和L3

L1: (27, 44) to (12, 32)
L2: (46, 53) to (17, 62)
L3: (46, 70) to (22, 40)

可以验证,线段L2和L3有一个真交点。注意到L3的一个端点(22,40)恰好在L1上,因此这不是一个真交点。L1和L2则没有交点。因此在这三条线段中,一共有一个真交点。

现在我们来对5000条线段求真交点数。首先,我们用“布鲁姆-布鲁姆-舒布”伪随机数生成算法生成2000个数。

s0 = 290797
sn+1 = sn×sn (modulo 50515093)
tn = sn (modulo 500)

为了生成每一条线段,我们使用tn的连续四项,也就是说,第一条线段是:

(t1, t2)至(t3, t4)

由上述算法生成的前四个数是:27,144,12和232,因此第一条线段是(27,144)至(12,232)。

在这5000条线段中,有多少个真交点?

 

 

P166:

 

 

 

 

 

 

 

 

 

 

P167:乌拉姆序列研究

任取两个正整数a和b,乌拉姆序列U(a,b)按如下方式定义:U(a,b)1 = a,U(a,b)2 = b,对于k > 2,U(a,b)k是比U(a,b)(k-1)更大,且存在用U(a,b)之前的这些项中的不同两项之和唯一表示的最小整数。

例如,序列U(1,2)的开头部分如下所示
1, 2, 3 = 1 + 2, 4 = 1 + 3, 6 = 2 + 4, 8 = 2 + 6, 11 = 3 + 8;
5不在这个序列是,因为5 = 1 + 4 = 2 + 3,有两种表示方法,同样地7也是如此因为7 = 1 + 6 = 3 + 4。

对于2 ≤ n ≤10,求∑U(2,2n+1)k,其中k = 1011.

 

 

P168:数字轮换

考虑数142857,我们可以将它的数字右移一位并把最后一个数字7放到最前面,得到714285。
可以验证714285=5×142857。
这表明了142857的一个特殊性质:它右移一位并把末位数字移至最前得到的数是它的倍数。

找出所有10 < n < 10100范围内满足这一性质的整数n,求它们的和的最后五位数字。

 

 

 

P169:探索将数表达为2的幂之和的方式数目

记f(0)=1,f(n)是将n表达为2的幂之和,且不同的幂至多使用两次的方式数目。

例如,f(10)=5,即有五种不同的方式表示10:

1 + 1 + 8
1 + 1 + 4 + 41 + 1 + 2 + 2 + 4
2 + 4 + 4
2 + 8

求f(1025)。

 

 

P170:求用乘积拼接而成的最大0至9全数字数

将6分别乘以1273和9854:

6 × 1273 = 7638
6 × 9854 = 59124

连接这两个乘积我们得到1至9全数字数763859124.我们称763859124为“6和(1273,9854)乘积的连接”。注意到,被乘的这些数的连接612739854,同样也是1至9全数字数。

对于0至9全数字数也存在同样的可能。

在所有由一个整数和另外至少两个整数的乘积连接而成且被乘的整数连接起来也是0至9全数字数的0至9全数字数中,求其中最大的一个。

 

Aster 未完成 Leave a Comment

# 在此处输入标题

标签(空格分隔): 未分类

---

$$L(s):=\sum_{m,n \in \mathbb{Z\backslash\{0\}}}^{'}\frac{1}{\left ( m^2+n^2 \right )^s}=4\,\sum_{m=0}^{\infty}\;\sum_{n=1}^{\infty}\frac{1}{\left ( m^2+n^2 \right )^s}$$

$$L(s)=4\zeta(s)\beta(s)$$

在此输入正文

$$\sum_{n=1}^{\infty}\frac{\operatorname{csch}^2(\pi n)}{n^2 }=\frac{4}{\pi^2}\sum_{n=1}^{\infty}\sum_{k=1}^{\infty}\frac{1}{\left ( n^2+k^2 \right )^2} -\frac{\pi^2}{60}$$

$$\sum_{(n,k)\neq (0,0)}\frac{1}{\left ( n^2+k^2 \right )^2}=4\left(\sum_{n=1}^{\infty}\sum_{k=1}^{\infty}\frac{1}{\left ( n^2+k^2 \right )^2}+\zeta(4)\right)$$

---

一般来说数学家会考虑一个更难的问题, 把原来的情况视为一个特例, 从而发现更本质的规律.

我们不妨设:

$$\begin{aligned}
R_{s}(\alpha)&=\sum_{n=1}^{\infty}\frac{1}{n^s\left(e^{\alpha n}-1\right)}\\
T_{s}(\alpha)&=\sum_{n=1}^{\infty}\frac{1}{n^s\left(e^{\alpha n}+1\right)}\\
\end{aligned}$$

通常 $s$ 是一个正的奇数, 而 $\alpha$ 则是 $\pi\sqrt{k},k\in\mathbb{Z_+}$的形式.

我们可以把这个求和转写成多对数函数 $\displaystyle \mathrm{Li}_{s}(z)=\sum_{n=1}^{\infty}\frac{z^n}{n^s}$ 的形式

$$R_{s}(x) = \sum_{n=1}^{\infty}\sum_{\alpha=0}^{\infty}\frac{e^{-xn(\alpha+1)}}{n^s}= \sum_{\alpha=1}^{\infty}\mathrm{Li}_{s}\left(e^{-\alpha x}\right)$$

然后代入下列关系式, 该关系可以由梅林变换得到.

Wiki 有这个的推导, 对此不做进一步解释: [Polylogarithm Integral](https://en.wikipedia.org/wiki/Polylogarithm#Integral_representations)

$$\mathrm{Li}_{s}\left(e^{-u}\right)=\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty}\Gamma(z)\zeta(z+s)u^{-z}\, dz$$

代入变形, 最终我们能得到:

$$\begin{aligned}
R_{s}(x) &= \frac{1}{2\pi i}\sum_{m=1}^{\infty}\int_{c-i\infty}^{c+i\infty}\Gamma(z)\zeta(z+s)\left(xm\right)^{-z}\, \mathrm{d}z\\
&= \frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty}\frac{\Gamma(z)}{x^{z}}\zeta(z+s)\zeta(z)\, \mathrm{d}z
\end{aligned}$$

接下里就是复变函数的内容了, 考虑如下围道积分:

$$I_{s}(x)=\frac{1}{2\pi i}\oint_{\gamma}f(z)\mathbb{d}z$$

$$f(z)=\frac{\Gamma(z)}{x^{z}}\zeta(z+s)\zeta(z)$$

我们来看看有哪些奇点, $\zeta$ 函数带来的 $z=1$, $z+s=1$ 还有 $\Gamma$ 函数的 $z=0,-1,-2\cdots\cdots$, 围道$\gamma$ 直接从左边过来顺时针绕一圈回去就行.

先看奇点 $z=1$, 这个不难:

$$\operatorname{Res}\limits_{z=1}f(z)=\frac{\zeta(s+1)}{x}$$

然后是奇点 $z=-n$, 这个也不麻烦:

$$\operatorname{Res}\limits_{z=-n}f(z)=\frac{(-x)^{n}}{n!}\zeta(s-n)\zeta(-n)$$

于是就差最后一部分了:

$$I_{s}(x)=\operatorname{Res}\limits_{z=1-s}f(z)+\frac{\zeta(s+1)}{x}+\sum_{n=0}^{\infty}\frac{(-x)^{n}}{n!}\zeta(s-n)\zeta(-n)$$

这部分的留数不是很好求, 对于非整数情况易得:
$$\operatorname{Res}\limits_{z=1-s}f(z)=\frac{\Gamma(1-s)}{x^{1-s}}\zeta(1-s),s\not \in \mathbb{Z}$$

但我们感兴趣的是正整数时的情况 $s\in\mathbb{Z}_+$, 此时函数奇点与Gamma函数的一个奇点重叠,而另一个极点为双重奇点.

$$\begin{aligned}
\frac{1}{2\pi i}\oint_{z=1-s}f(z)dz
&=\frac{1}{2\pi i}\oint_{z=1-s}\frac{f(z)}{(z+s-1)^{2}}dz\\
&=\left.\frac{d}{dz}\left[(z+s-1)^{2}\Gamma(z)\;\zeta(z+s)\frac{\zeta(z)}{x^{z}}\right]\right|_{z=1-s}\\
&=\frac{(-x)^{s-1}}{(s-1)!}\left[\zeta^{\prime}(1-s)+\left(H_{s-1}-\ln2\pi\right)\zeta(1-s)\right] \end{aligned}$$

加上这部分, 最终的表达式就是:

$$\begin{aligned}
I_{k}(x)=&\frac{\zeta(k+1)}{x}+\!\sum_{\begin{array}{c}n=0\\
n\ne k-1\end{array}}^{\infty}\!\frac{(-x)^{n}}{n!}\zeta(k-n)\zeta(-n)\\
+&\frac{(-x)^{k-1}}{(k-1)!}\left[\zeta^{\prime}(1-k)+\left(H_{k-1}-\ln2\pi\right)\zeta(1-k)\right] \end{aligned}$$

转载: 现在谷歌网盘文件

Aster 未完成 Leave a Comment

说到如何在Linux命令行下下载Google网盘(云端硬盘)的文件,第一个想到的应该是gdriveprasmussen/gdrive),这个脚本可以下载、上传、同步等功能,当然需要事先命令gdrive about关联网盘,显然适合自己使用。

如果说要下载别人分享的文件呢?直接wget命令会多次跳转,可能会导致下载失败。找到个脚本(circulosmeos/gdown.pl)可以实现正常下载。

Read More

欧拉挑战:初阶5段

Aster 未完成 Leave a Comment

P151:标准大小的纸张:有关期望的问题

一家打印店每周有16份打印工作,每份打印工作需要一张A5大小的特殊彩色打样纸。

每周一早晨,领班会打开一个新信封,其中有一张A1大小的特殊彩色打样纸。

他将这张纸一裁为二,得到两张A2大小的纸。再将其中一张一裁为二,得到A3大小的纸,如此直到他裁出一张用于第一份打印工作的A5大小的彩色打样纸。

所有剩下的纸张将会重新放回信封里。

接下来的每次打印工作前,领班会从信封里拿出随机拿出一张纸,如果恰好是A5大小的,他会直接拿去使用,否则他会重复一裁为二的过程直到他得到一张A5大小的纸,并将剩下的纸重新放回信封里。

除了每周的第一次和最后一次打印工作外,求在这周当中领班在拿纸时发现信封里只有一张纸的次数的期望值。

你的答案应当保留六位小数,即以如下的形式x.xxxxxx。

 

P152:将1/2写成平方数的倒数和

有许多种方式将1/2写成一系列不同整数的平方的倒数和。

例如,可以用这些数{2,3,4,5,7,12,15,20,28,35}:

事实上,只用2至45之间的数的方式一共有三种,另两种分别是:{2,3,4,6,7,9,10,20,28,35,36,45}和{2,3,4,6,7,9,12,15,28,30,35,36,45}。

如果只用2至80之间的数,将1/2写成不同整数的平方的倒数和共有多少种方式?

 

 

 

 

P153:高斯整数的研究

我们都知道方程x2=-1在实数范围内无解。
但如果我们引入虚数i,这个方程将会有两个解x=i和x=-i。
进一步地,方程(x-3)2=-4有两个复数解:x=3+2i和x=3-2i。
x=3+2i和x=3-2i互称为共轭复数。
形如a+bi的数被称为复数。
概括地说,a+bi和a−bi互称为共轭复数。

高斯整数是形如a+bi且a和b均为整数的复数。
一般意义上的整数也是高斯整数(取b=0)。
为了把它们和b ≠ 0的高斯整数区分开来,称它们为“有理整数”。
如果一个高斯整数除有理整数n的结果仍然是高斯整数,则称它为该有理整数的约数。
例如,我们用1+2i除5,按如下方式简化51+2i51+2i
分子和分母同时乘以1+2i的共轭:1−2i。
结果是:51+2i=51+2i12i12i=5(12i)1(2i)2=5(12i)1(4)=5(12i)5=12i51+2i=51+2i1−2i1−2i=5(1−2i)1−(2i)2=5(1−2i)1−(−4)=5(1−2i)5=1−2i
所以1+2i是5的约数。
注意1+i不是5的约数,因为51+i=5252i51+i=52−52i
同时注意如果高斯整数(a+bi)是有理整数n的约数,那么它的共轭复数(a−bi)也是n的约数。

事实上,5一共有六个实数部分是正数的约数:{1, 1 + 2i, 1 − 2i, 2 + i, 2 − i, 5}。
如下表格列出了前五个正有理整数的所有约数:

n实数部分是正数的高斯整数约数约数的和s(n)
111
21, 1+i, 1-i, 25
31, 34
41, 1+i, 1-i, 2, 2+2i, 2-2i,413
51, 1+2i, 1-2i, 2+i, 2-i, 512

对于实数部分为正数的约数,我们有:5n=1s(n)=35∑n=15s(n)=35

对于1 ≤ n ≤ 105,∑ s(n)=17924657155。

对于1 ≤ n ≤ 108,求∑ s(n)。

 

 

 

P154:探索帕斯卡四面体

我们用球构建一个三角形四面体,每一个球的下一层都由恰好三个球支撑。

然后,我们计算从顶端到每一个位置的路径数:

每一条路径从顶端出发,然后每次都走向下一层支撑当前位置的球的三个球之一。

最终,到达每个位置的路径数是它上方的球的路径数之和(根据位置的不同,每个位置的上方最多可能有三个球)。

最终的结果被称为帕斯卡四面体,这个四面体第n层的结果将是三项式(x + y + z)n的系数。

在三项式(x + y + z)200000的展开式中,有多少个系数是1012的倍数?

 

 

 

 

P155:电容电路计算

考虑如下电路,其中使用的电容都是完全相同的值C。
电容之间互相串联构成次级单元,然后次级单元之间互相串联或和其它次级单元或电容并联构成更大的次级单元,最终组成整个电路。

使用n个电容并重复这个简单的过程,我们可以构建出一系列总电容不同的电路。例如,使用最多n=3个值为60μF的电容,我们可以得到7种不同的总电容:

我们用D(n)表示当我们使用最多n个相同的电容并重复上述简单过程后,我们能够得到的总电容的种数,我们有:D(1)=1, D(2)=3, D(3)=7 …

求D(18)。

提醒:当电容C1,C2等等并联时,总电容为CT = C1 + C2 +…,
而当它们串联时,总电容为:1CT=1C1+1C2+1CT=1C1+1C2+…

 

 

 

P156:数字计数

从零开始的自然数在十进制中如下表示:
0 1 2 3 4 5 6 7 8 9 10 11 12….

考虑数字d=1。当我们写下数n之后,我们计算一下到目前为止数字1出现的次数,并记为f(n,1)。f(n,1)的前面一部分值如下所示:

nf(n,1)
00
11
21
31
41
51
61
71
81
91
102
114
125

注意到f(n,1)从不等于3。
等式f(n,1)=n的前两个解是n=0和n=1,下一个解是n=199981。

同样地我们记f(n,d)表示在写下n之后d出现的次数。
事实上,对于任意一个数字d ≠ 0,0都是方程f(n,d)=n的第一个解。

记s(d)是所有f(n,d)=n的解的和。
已知s(1)=22786974071。

对于1 ≤ d ≤ 9,求∑ s(d)。

注意:如果对于某些n,对于多于一个的d均满足f(n,d)=n,这个数n对于每个d都要计算一遍。

 

 

 

P157: 解不定方程1/a+1/bp/10n

考虑不定方程1/a+1/bp/10n,其中a, b, p, n均为正整数,且a ≤ b。
对于n=1,这个方程有20个解,如下所示:

1/1+1/1=20/101/1+1/2=15/101/1+1/5=12/101/1+1/10=11/101/2+1/2=10/10
1/2+1/5=7/101/2+1/10=6/101/3+1/6=5/101/3+1/15=4/101/4+1/4=5/10
1/4+1/20=3/101/5+1/5=4/101/5+1/10=3/101/6+1/30=2/101/10+1/10=2/10
1/11+1/110=1/101/12+1/60=1/101/14+1/35=1/101/15+1/30=1/101/20+1/20=1/10

对于1 ≤ n ≤ 9,方程一共有多少个解?

 

 

 

P158:按字典序升序排列的字符串研究

从字母表的26个字母中取出三个不同的字母,可以组成一个长度为3的字符串。
这样的例子包括’abc’,’hat’和’zyx’。
可以发现,对于字符串’abc’,有两个字符与其左侧字符是按照字典序升序排列的。
对于字符串’hat’,只有一个字符与其左侧字符是按照字典序升序排列的,而对于字符串’zyx’则不存在这样的字符。
总共有10400个长度为3的字符串,其中恰好有一个字符与其左侧字符是按照字典序升序排列的。

现在考虑由字母表中的n ≤ 26个不同字符组成的字符串。
对于任意n,我们用p(n)表示长度为n且恰好有一个字符与其左侧字符是按照字典序升序排列的字符串数目。

p(n)的最大值是多少?

 

 

 

 

 

 

P159:分解约数数字根之和

每个合数都有很多种分解约数的方式。例如,如果不允许多次乘1,有7种不同的方式分解24的约数:

24 = 2x2x2x3
24 = 2x3x4
24 = 2x2x6
24 = 4x6
24 = 3x8
24 = 2x12
24 = 24

在十进制下,一个数的数字根是不断重复将其各位数字相加,直到得到的结果小于10为止。因此467的数字根是8。

我们记数字根和(DRS)是所有分解出的约数的数字根之和。
下表是24的所有约数分解的DRS值。

约数分解数字根和
2x2x2x39
2x3x49
2x2x610
4x610
3x811
2x125
246

对于24的所有分解,最大的数字根和是11。
函数mdrs(n)表示对于n的不同分解最大的数字根和。因此mdrs(24)=11。
对于1 < n < 1,000,000,求∑mdrs(n)。

 

 

 

 

 

 

P160:阶乘的尾数

对于任意N,记f(N)为N!除去末尾零后的最后五位数字。
例如,

9! = 362880,所以f(9)=36288
10! = 3628800,所以f(10)=36288
20! = 2432902008176640000,所以f(20)=17664

求f(1,000,000,000,000)

 

 

 

 

 

非均匀赠券收集

Aster 未完成 Leave a Comment

记事件$A_{n,i}$为第$n$次选取后第$i$个样本未被选中的情形,于是概率即为相应情形之并.

然后依容斥原理展开:

$$\begin{aligned}
P(X>n) &= P\biggl(\bigcup_{1\leq i\leq n} A_{n,i}\biggr)\\
&=\sum_{1\leq i\leq n}P(A_{n,i}) - \sum_{1\leq i < j\leq n}P(A_{n,i}\cap A_{n,j}) + \sum_{1\leq i < j < k\leq n}P(A_{n,i}\cap A_{n,j}\cap A_{n,k}) + \cdots\\
&= \sum_{J \subseteq \{1, ..., n\}}^{J \ne \phi}(-1)^{|J| + 1}\left(1 - \sum_{j \in J} p_j\right)^{n}\\
\end{aligned}$$

其中,$J$代表一种选法集合, $|J|=\mathrm{card}(J)$, 即集合$J$中元素的数量.

其概率生成函数为:

$$\mathcal{P}(z)=1+(z-1)\sum_{J \subseteq \{1, ..., n\}}^{J \ne \phi} \frac{(-1)^{|J|+1}}{z-1+\sum_{j \in J }p_j}$$

接下来求期望

$$\begin{aligned}
E(n)=&\frac{d}{dz}\mathcal{P}(z)\biggl|_{z=1^-}\\
=&\sum_{J \subseteq \{0, 1, ..., n-1\}}^{J \ne \phi} \frac{(-1)^{|J|+1}}{\sum_{j \in J }p_j}\\
=&\sum_{i=1}^n (-1)^{i+1}\sum_{1\leq j_1 < \cdots < j_i\leq n} (-1)^{i+1}\frac{1}{p_{j_1}+\cdots + p_{j_i}} \\
=&\sum_{i=1}^n \frac{1}{p_i} - \sum_{1\leq j_1<j_2\leq n}\frac{1}{p_{j_1} + p_{j_2}} + \cdots \end{aligned}$$ 注意到 $\displaystyle \int_0^\infty e^{-px}dx=\frac{1}{p},\, p>0$

所以上式可以进一步可以写成:

$$\begin{aligned}
E(n)=&\sum_{i=1}^n \int_0^\infty e^{-p_ix}dx- \sum_{1\leq j_1<j_2\leq n}\int_0^\infty e^{-(p_{j_1} + p_{j_2})x}dx + \cdots\\
=&\int_0^\infty1-\prod_{i=1}^n(1-e^{p_ix})dx
\end{aligned}$$

由于在无穷区间上做数值计算不好采样, 所以我们再做一步代换得到:

$$E(n)=\int_0^1\left[1-\prod_{i=1}^n(1-x^{p_i})\right]\frac{dx}{x}$$

方差可以从期望转化得到:

$$\begin{aligned}
V(n)&=\int_0^1 (2 \ln x+1)v(x) \, dx - E^2(n)\\
v(x)&=\frac{1}{x}\left[\prod_{i=1}^n(1-x^{p_i})-1\right]\\
\end{aligned}$$

当然也可以从概率生成函数出发计算,但是我找不到关系不会化简...

设定的时候可能用的是权重,那只要归一化就行了.

浮点误差也无所谓,这个公式不至于加起来不是1就爆炸.

### 近似计算

使用容斥原理计算的复杂度高达 $O(2^n)$, 这是无法承受的.

如果你身经百战见的多了,看到这个期望的表达形式可能就会猜测:

$$\mathrm{CDF}(x)\sim \prod_{i=1}^n(1-e^{p_ix})$$

实验表明这是个不错的近似, 这暗示当概率相同时, 有:

$$\frac{n!}{n^k} \mathcal{S}_2(k - 1, n - 1)\sim\frac{\partial }{\partial n}\left(1-e^{-\frac{n}{k}}\right)^k=e^{-\frac{n}{k}} \left(1-e^{-\frac{n}{k}}\right)^{k-1}$$

数值计算表明这其实是个相对而言很烂的近似,也许是误差累积了起来,反正是劣化了...

这玩意甚至满足归一化条件(零阶矩):

$$\int_0^{\infty } e^{-\frac{x}{n}} \left(1-e^{-\frac{x}{n}}\right)^{n-1} \, \mathrm{d}x=1$$

可以通过这个计算高阶矩...

$$\int_0^{\infty } x e^{-\frac{x}{n}} \left(1-e^{-\frac{x}{n}}\right)^{n-1} \, \mathrm{d}x =nH_n$$

真是神奇, Confused...

我们可以定义一个变限积分:

$$f(t)=\int_0^t e^{-\frac{x}{n}} \left(1-e^{-\frac{x}{n}}\right)^{n-1} \, \mathrm{d}x=\left(1-e^{-\frac{t}{n}}\right)^n$$

那么如果取最佳效益 $t=nH_n$,此时 $f(t)=e^{-e^{-\gamma }}\approx 57\%$.

欧拉挑战:初阶4段

Aster 未完成 Leave a Comment

P141:累进平方数n的研究

正整数n被d的商和余数分别是q和r,除此之外,d,q,r恰好是一个等比数列中的连续三个正整数项,但其对应顺序不一定一致。

例如,58被6除商9余4,可以发现4,6,9构成等比数列的连续三项,公比是3/2。
我们称这样的数n为累进数。

有些累进数,例如9或者10404=1022,恰好也是完全平方数。
所有小于十万的累进平方数的和是124657。

求所有小于一万亿(1012)的累进平方数之和。

 

 

 

 

 

P142:完全平方数收集

找出最小的x + y + z的值,其中正整数x > y > z > 0满足x + y, x - y, x + z, x - z, y + z, y - z 均为完全平方数。

 

 

 

 

 

P143:三角形托里拆利点的研究

三角形ABC的每一个内角均小于120度,取三角形内的任意一点X满足XA = p,XC = q以及XB = r。

费马曾经向托里拆利提出挑战,找到点X的位置,使得p + q + r最小。

托里拆利证明了,如果对三角形ABC的三边分别构造等边三角形AOB,BNC和AMC,这三个三角形的外接圆将会交于三角形内一点T。T点,也被称为托里拆利点或费马点,是使得p + q + r最小的点。更神奇的是,此时AN = BM = CO = p + q + r,且AN,BM和CO相交于点T。

如果当和最小时有a,b,c,p,q,r均为正整数,我们称这个三角形ABC为托里拆利三角形。例如,a = 399,b = 455,c = 511就是托里拆利三角形的一个例子,此时p + q + r = 784。

对于所有满足p + q + r ≤ 120000的托里拆利三角形,求所有不同的p + q + r的值之和。

 

 

 

 

P144:一束激光多次反射的研究

在激光物理学中,“白腔”指的是一个使激光束发生延迟的镜面系统。激光进入镜面系统后,最终会不断反射并重新射出。

在本题中考察的白腔系统是一个椭圆,其方程为4x2 + y2 = 100

在椭圆顶端割去了-0.01 ≤ x ≤ +0.01的区域,使得激光能够进入和离开白腔。

本题中,激光从白腔外的点(0.0,10.1)发出,首次接触镜面的位置是(1.4,-9.6)。

每当激光击中椭圆表面时,它遵循反射定律“入射角等于反射角”,也就是说,入射光线和反射光线在入射点和法线的夹角相等。

在左图中,红线表示的是激光前两次击中镜面的过程;蓝线表示的是激光第一次击中镜面时入射点的切线。

对于椭圆的任意点(x,y),其切线的斜率m满足:m = -4x/y

法线垂直于入射点的切线。

右侧的动画展现了激光束前十次反射的路径。

在激光离开白腔之前,它在椭圆的内表面上击中了多少次?

 

 

 

 

P145:有多少小于十亿的可逆数?

有些正整数n满足这样一种性质,将它的数字逆序排列后和本身相加所得到的和[ n + reverse(n) ]的十进制表示只包含有奇数数字。例如,36 + 63 = 99 以及409 + 904 = 1313。我们称这样的数是可逆的;因此36,63,409和904都是可逆的。无论是n还是reverse(n)都不允许出现前导0。

在小于一千的数中,一共有120个可逆数。

在小于十亿(109)的数中,一共有多少个可逆数?

 

 

 

P146:素数模式研究

使得n2+1,n2+3,n2+7,n2+9,n2+13以及n2+27均为素数的最小的n是10.所有小于一百万的数中,满足这一条件的所有整数n的和为1242490。

在小于一亿五千万的数中,所有满足这一条件的正整数n的和是多少?

 

 

P147交叉对角线方格中的长方形

在一个3x2的标记了所有交叉对角线的方格中,一共有37种不同的长方形其各边是方格内的线段,如下图所示:

从长和宽两方面考虑,有五个方格比3x2要小,大小分别是1x1,2x1,3x1,1x2和2x2。 如果将它们都标记上交叉对角线,则在这些更小的方格中有如下数目的不同长方形:

1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18

把这些数和37加起来,可知对于3x2或更小的交叉对角线方格,一共有72种不同的长方形。

对于47x43或更小的交叉对角线方格,一共有多少种不同的长方形?

 

 

 

P148:探索帕斯卡三角

可以验证,帕斯卡三角的前7行是,没有一个整数能够被7整除:

1
11
121
1331
14641
 1 51010 5 1
 1 6152015 6 1

然而,如果我们检查前一百行就会发现,在这5050个数上,只有2361个不能被7整除。

找出帕斯卡三角前十亿(109)行中不能被7整除的数的数目。

 

 

 

 

P149:寻找最大和子序列

观察下面的表格,很容易发现,在所有同一横行、竖列或对角线的任意数量相邻数之和中,最大值是16 (= 8 + 7 + 1)。

-253 2
9-65 1
327 3
-18-4 8

现在,让我们再来找一次,不过是在一个更大尺寸的表格中:

首先,使用现在被称为“延迟斐波那契生成器”的方法,生成四百万个伪随机数:

对于1 ≤ k ≤ 55,sk = [100003 ? 200003k + 300007k3] (modulo 1000000) ? 500000。
对于56 ≤ k ≤ 4000000, sk = [sk?24 + sk?55 + 1000000] (modulo 1000000) ? 500000.

如此一来,可以得到s10 = ?393027,而s100 = 86613。

这些s的项随后被填入一个2000×2000的表格,前2000个数字按顺序填入第一行,然后2000个数字在第二行,依此类推。

最后,求所有同一横行、竖列或对角线的任意数量相邻数之和的最大值。

 

 

 

 

 

P150:寻找三角形数组的最小和子三角形

我们希望在一个包含正数和负数的三角形数组中找到一个子三角形,其中元素的和尽可能小。

在下面这个例子中,可以验证带标记的三角形满足题述,它的元素和是-42。

我们希望搭建起一个有一千行的三角形数组,因此我们使用一种随机数生成算法(称为线性同余生成器),生成了500500个在范围±219之间的伪随机数sk,如下所示:

因此,$s_1= 273519,s_2= −153582,s_3= 450905$,依此类推。

接下来就将这些伪随机数填入三角形数组:

s1
s2  s3
s4  s5  s6
s7  s8  s9  s10
子三角形可以从数组中的任意元素开始,向下可以延伸至无限长(先取下一行的两个元素,再取接下来一行的三个元素,依此类推)。

“子三角形的和”被定义为其中所有元素的和。

求最小的子三角形的和。

compared to others, a rather optimized solution by recursion (smallest sum is either a part of the whole triangle (vertically) or of the triangle with the leftmost part removed, or of that with the rightmost part removed)

 

rnd=NestList[Mod[615949*#+797807,2^20]&,0,500500]-2^19;
tri=Accumulate/@Array[rnd[[(4-#+#^2)/2;;(2+#+#^2)/2]]&,1000];
min5[{}]=min6[{}]=Infinity;
min5[arr_]:=Min[Accumulate[Total/@arr],min5[Rest[Rest/@arr]],min6[Rest[Most/@arr]]] min6[arr_]:=Min[Accumulate[Accumulate/@Transpose[PadLeft[#,Length@arr]&/@arr]]] Block[{$RecursionLimit=2048},min5[tri]]

 

 

欧拉挑战:初阶3段

Aster 未完成 Leave a Comment

P131:素数立方数组合

对于某些素数$p$,存在正整数$n$,使得表达式$n^3+n^2×p$是立方数。

例如,对于$p = 19$,$8^3+8^2×19=12^3$。

非常奇特的是,对于满足这个性质的素数,$n$的值都是唯一的。在小于一百的素数中,只有四个素数满足这个性质。

在小于一百万的素数中,有多少个素数满足这个神奇的性质?

这题哪来的, 这么水,  放这里几个意思???

$$n+x=(a+1)^3;n=a^3$$

$$1 + 3 a + 3 a^2<10^6\Rightarrow n\leq 576$$

  • 计时: 4:17.33

P132:大循环单位数的因数

只包含数字1的数被称为循环单位数,我们定义R(k)是长为k的循环单位数。

例如,$R(10) = 1111111111 = 11×41×271×9091$,这些质因数的和是9414。

找出$R(10^9)$的前$40$个质因数的和。

找前几个因数, 那就是试除法, 但也不可能去除这么大的数啊.

所以, 取模呗, 这题考的还是快速幂模.

$$R(n)=\sum _{k=0}^{n-1} 10^k=\frac{1}{9} \left(10^n-1\right)$$

$$R(n)\bmod p=\frac{1}{9} \left(10^n\bmod p-1\right)$$

注意从10开始, 扔了2,3,5,7

唔, 要是你说这样不够函数式的话, 也不是不能用递归解法, 这样还快一个数量级.

$IterationLimit=2^15;
sf[n_,0,p_]:=0;
sf[n_,m_,p_]:=If[PowerMod[10,n,9*Prime[p]]==1,Prime[p]+sf[n,m-1,p+1],sf[n,m,p+1]];
sf[10^9,40,1]

  • 计时: 10:47.95

P133:循环单位数的非质因数

只包含数字1的数被称为循环单位数,我们定义R(k)是长为k的循环单位数;例如,R(6)=111111。

考虑形如R(10n)的循环单位数。

尽管R(10),R(100)和R(1000)都不能被17整除,R(10000)却能够被17整除。

然而,不存在n使得R(10n)能被19整除。

事实上,在小于100的质数中,只有11,17,41和73能够成为R(10n)的质因数。

找出所有小于十万且永远不会成为R(10n)的质因数的质数之和。

 

上一题是水题, 这题就触及核心问题了

实在搞不懂的话搞个$R\left(10^{10^20}\right)$的上界然后还是试除也能过

Reap@For[i=1,(p=Prime[i])<=10^5,i++,If[p==2||p==5||Mod[(PowerMod[10,10^20,9p]-1)/9,p]!=0,Sow@p]]//Flatten//Rest//Total

不要这么暴力的解法就麻烦了.

定义: 乘法阶数
若 $a, m$ 互素 , 定义集合 $A = \{n | a^n\bmod m = 1, n\in\mathbb {Z}\}$
那么将集合 $A$ 中的最小正数称为 $a\bmod m$ 的阶, 且A仅由阶的整数倍组成.

 

Table[MultiplicativeOrder[10, 9 Prime[n]], {n, PrimePi[100]}] MultiplicativeOrder[10, 9 #] & /@ {11, 17, 41}

  • 计时: 19:41.30

P134:质数对连接

考虑连续的质数$(p_1,p_2)=(19,23)$。可以验证,$1219$是所有以p1结尾并且能被p2整除的数中最小的一个。

事实上,除了$(p_1,p_2)=(3,5)$这一对之外,对于任意一对连续质数$p_2\ge p_1$,都存在一系列的数$n$,其尾数是$p_1$,且能够被$p_2$整除。记S是所有的n中的最小值。

对于$5\leq p_1\leq 10^6$内的所有连续质数对,求$\sum S$。

 

 

 

P135:相同的差

已知正整数x,y,z构成等差数列,使得方程$x^2-y^2-z^2=n$有两个解的最小正整数为$n=27$:

$$34^2-27^-20^2=12^2-9^2-6^2=27$$

使得方程有十个解的最小正整数为$n = 1155$。

在小于一百万的数中,有多少个n的取值使得方程恰好有十个不同的解?

 

 

 

P136:唯一的差

正整数$(x,y,z)$构成等差数列。取正整数$n=20$,此时方程$x^2-y^2-z^2=n$只有一个解:

$$13^2-10^2-7^2=20$$

事实上,在小于一百的数中,有25个n的取值使得方程有唯一解。

在小于五千万的数中,有多少个n的取值使得方程有唯一解?

 

 

 

P137:斐波那契金块

考虑无穷级数$A_F(x)=xF_1+x^2F_2+x^3F_3+\cdots$ 其中 $F_k$ 是斐波那契数列的第k项。

该数列由如下方式定义:$F_k=F_{k-1}+F_{k-2}$,其中$F_1=F_2=1$。

在这个问题中,我们感兴趣的是那些使得AF(x)为正整数的x。

其中一个特别的解是:

$$\begin{aligned}
A_F(1/2)&=(1/2)\dot1 + (1/2)2\dot1 + (1/2)3\dot2 + (1/2)4\dot3 + (1/2)5\dot5 +\cdots\\
&=  \frac{1}{2} + \frac{1}{4 + \frac{2}{8} + \frac{3}{16} + \frac{5}{32} +\cdots\\
&=  2
\end{aligned}$$

对应于前五个自然数的x如下所示。

xAF(x)
√2−11
1/22
(√13−2)/33
(√89−5)/84
(√34−3)/55

当x是有理数时,我们称AF(x)是一个斐波那契金块,因为这样的数将会变得越来越稀少,例如,第10个斐波那契金块将是74049690。

求第15个斐波那契金块。

这不就生成函数吗, 斐波那契数列的生成函数是:

$\displaystyle A_F(x)=\sum _i^{\infty } F_i x^i=-\frac{x}{x^2+x-1}$

令 $A_F(x)=n$, 解二次方程解得:

$\displaystyle F(n)=\frac{\sqrt{5 n^2+2 n+1}}{2 n}-\frac{n+1}{2 n}$

所以只要里面的是平方数就行了咯

$\displaystyle 5 n^2+2 n+1=p^2$

然后就是数论题了, 解出来的话会是:

$$p(n)=\left\{\begin{aligned}
&\frac{1}{10} \left(\left(\sqrt{5}+1\right) \left(4 \sqrt{5}+9\right)^{2 k}-\left(9-4 \sqrt{5}\right)^{2 k} \left(\sqrt{5}-1\right)-2\right) \\
&\frac{1}{5} \left(\left(\sqrt{5}-2\right) \left(4 \sqrt{5}+9\right)^{2 k}-\left(9-4 \sqrt{5}\right)^{2 k} \left(\sqrt{5}+2\right)-1\right) \\
&\frac{1}{10} \left(\left(5 \sqrt{5}+11\right) \left(4 \sqrt{5}+9\right)^{2 k}+\left(9-4 \sqrt{5}\right)^{2 k} \left(11-5 \sqrt{5}\right)-2\right) \\
\end{aligned}\right.,n\in\mathbb{Z}_+$$

注意少了个2, 所以要减掉一位

难度应该都在各种解方程上, 但是sorry, 数学软件就是可以为所欲为.

  • 计时: 6:43.13

P138:特殊等腰三角形

考虑底为$b = 16$,腰为$L = 17$的等腰三角形。

使用毕达哥拉斯定理,我们可以求出三角形的高是$h=\sqrt{17^3-8^2}=15$,恰好比底长小1。

当$b = 272$而$L = 305时$,可以算出$h = 273$,恰好比底长大1,而且这是满足性质h = b ± 1的三角形中第二小的。

对于最小的12个满足$h = b ± 1$且b,L均为正整数的等腰三角形,求$\sum L$。

 

 

 

 

P139:毕达哥拉斯地砖

用$(a, b, c)$表示边长为整数的直角三角形的三边,可以将四个这样的三角形放在一起,使其外框构成边长为c的正方形。

例如,边长为$(3, 4, 5)$的三角形可以构成一个$5x5$的正方形,中间留有一个$1x1$的洞。而这个$5x5$的正方形又恰好可以用25个$1x1$的小正方形组成。

然而,如果我们用$(5, 12, 13)$的三角形,则中间的洞将会是$7x7$大小,不能用来组成$13x13$的大正方形。

考虑边长小于一亿的直角三角形,有多少个毕达哥拉斯三角形可以用中间留下的空洞大小的地砖恰好铺满外围的大正方形?

 

 

 

 

P140:修正斐波那契金块

考虑无穷级数$A_G(x)=xG_1+x^2G_2+x^3G_3+\cdots$,其中Gk是二阶递归关系$G_k=G_{k-1}+G_{k-2}$的第k项

其中$G_1=1,G_2=4$,该序列为1, 4, 5, 9, 14, 23, … 。

在这个问题中,我们感兴趣的是那些使得$A_G(x)$为正整数的x。

对应于前五个自然数的x如下所示。

xAG(x)
(√5-1)/41
2/52
(√22-2)/63
(√137-5)/144
1/25

当x是有理数时,我们称AG(x)是一个修正斐波那契金块,因为这样的数将会变得越来越稀少,例如,第20个修正斐波那契金块将是211345365。

求前30个修正斐波那契金块的和。

其实和P137没有任何区别

$$G(k)=\frac{1}{2} \left(3 L_k-F_k\right)$$

$$A_G(x)=-\frac{3 x^2+x}{x^2+x-1}$$

$$G(n)=\frac{\sqrt{5 n^2+14n+1}-n-1}{2 n+6}$$

反正结果的话比原来更暴力一点点.

$$p(n)=\left\{\begin{aligned}
&\frac{1}{10} \left(\left(\sqrt{5}+7\right) \left(4 \sqrt{5}+9\right)^{2 n}-\left(9-4 \sqrt{5}\right)^{2 n} \left(\sqrt{5}-7\right)-14\right) \\
&\frac{1}{10} \left(-\left(\sqrt{5}-7\right) \left(4 \sqrt{5}+9\right)^{2 n}+\left(\sqrt{5}+7\right) \left(9-4 \sqrt{5}\right)^{2 n}-14\right) \\
&\frac{1}{10} \left(\left(97 \sqrt{5}+217\right) \left(4 \sqrt{5}+9\right)^{2 n}+\left(9-4 \sqrt{5}\right)^{2 n} \left(217-97 \sqrt{5}\right)-14\right) \\
&\frac{1}{10} \left(\left(7 \sqrt{5}+17\right) \left(4 \sqrt{5}+9\right)^{2 n}+\left(9-4 \sqrt{5}\right)^{2 n} \left(17-7 \sqrt{5}\right)-14\right) \\
&\frac{1}{5} \left(\left(25 \sqrt{5}+56\right) \left(4 \sqrt{5}+9\right)^{2 n}+\left(9-4 \sqrt{5}\right)^{2 n} \left(56-25 \sqrt{5}\right)-7\right) \\
&\frac{1}{5} \left(\left(7 \sqrt{5}+16\right) \left(4 \sqrt{5}+9\right)^{2 n}+\left(9-4 \sqrt{5}\right)^{2 n} \left(16-7 \sqrt{5}\right)-7\right) \\
\end{aligned}\right.,n\in\mathbb{Z}_+$$

话说怎么判定缺少的有理数我还想了半天, 一时半会儿想不起这个函数了...

你要说如果不这么无赖能不能解呢?

当然可以啊, 不就佩尔方程吗, 我们知道佩尔方程可以用连分展开解决.

也就是说可以化为一个矩阵型, 进一步的我们可以写出其线性形式.

P137 = LinearRecurrence[{8, -8, 1}, {2, 15, 104}, 15] // Last

P138 =LinearRecurrence[{18, -1}, {17, 305}, 12] // Total
P140 = LinearRecurrence[{1, 7, -7, -1, 1}, {2, 5, 21, 42, 152}, 30] //Total

  • 计时: 2:24.16

欧拉挑战:初阶2段

Aster 未完成 Leave a Comment

P121:碟子游戏奖金

一开始,包里装有一个红色碟子和一个蓝色碟子。在一场概率游戏中,每一轮玩家从包中取出一个碟子,记录下其颜色,随后将碟子放回包中,并在包中加入一个红色碟子,再进行下一轮。

玩家需要付£1来玩这个游戏,如果他们在游戏结束时拿出的蓝色碟子数比红色碟子数更多,则获得胜利。

如果游戏进行4轮,那么玩家获胜的概率是11/120,因此游戏所设定的最高奖金为£10,否则可能会造成亏损。注意奖金必须是整数,而且包含了玩家付出用于玩游戏的£1,也就是说玩家实际上赢得的数额是£9。

如果游戏进行15轮,求游戏所设定的最高奖金。

 

 

 

P122:高效指数计算

计算n15最朴素的方式需要14次乘法:

n × n × … × n = n15

但使用一个“二进制”的算法,你可以只用6次乘法:

n × n = n2
n2 × n2 = n4
n4 × n4 = n8
n8 × n4 = n12
n12 × n2 = n14
n14 × n = n15

然而,实际上仅用5次乘法也是可以的:

n × n = n2
n2 × n = n3
n3 × n3 = n6
n6 × n6 = n12
n12 × n3 = n15

记m(k)是计算nk所需要的最少次数,例如m(15) = 5。

对于1 ≤ k ≤ 200,求∑m(k)。

 

 

 

 

P123:素数平方余数

记pn是第n个素数:2、3、5、7、11……;记r是(pn?1)n + (pn+1)n被pn2除所得的余数。

例如,当n = 3时,p3 = 5,而43 + 63 = 280 ≡ 5 mod 25。

使余数首次超过109的最小n值是7037。

求使余数首次超过1010的最小n值。

 

 

P124:基排序

数n的基rad(n),是指n的不同质因数之积。例如,504 = 23 × 32 × 7,所以rad(504) = 2 × 3 × 7 = 42。

如果我们计算1 ≤ n ≤ 10的rad(n),并先按照rad(n)再按照n从小到大排序,我们得到:

排序前排序后
nrad(n)nrad(n)k
11111
22222
33423
42824
55335
66936
77557
82668
93779
1010101010

记E(k)是前n个数排序后的第k个数,例如,E(4) = 8以及E(6) = 9。

对1 ≤ n ≤ 100000按照rad(n)排序后,求E(10000)。

 

P125:回文和

回文数595很有趣,因为它可以写成连续平方数的和:62 + 72 + 82 + 92 + 102 + 112 + 122

恰好有十一个小于一千的回文数可以写成连续平方数的和,这些回文数的和是4164。注意1 = 02+ 12并没有算在内,因为本题只考虑正整数的平方。

在小于108的数中,找出所有可以写成连续平方数的和的回文数,并求它们的和。

 

 

 

P126:立方体层

要完全包住一个3x2x1的长方体的表面,最少需要的立方体数目为22。

如果我们要再包一层,需要46个立方体才能挡住所有表面,而第三层需要78个立方体,第4层则需要180个立方体。

同样地,要完全包住一个5x1x1的长方体的表面也需要22个立方体。而要包住5x3x1或是7x2x1或是11x1x1的长方体表面,第一层就需要46个立方体。

记C(n)是在任意一层中需要n个立方体的长方体数目。所以C(22) = 2,C(46) = 4,C(78) = 5,C(118) = 8。

可以验证154是第一个使得C(n) = 10的n。

找出使得C(n) = 1000的最小的n。

 

P127:abc匹配

数n的基rad(n)被定义为n的不同质因数之积。例如504 = 23 × 32 × 7,所以rad(504) = 2 × 3 × 7 = 42。

我们定义正整数三元组(a, b, c)为abc匹配,当其满足如下条件:

  1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
  2. a < b
  3. a + b = c
  4. rad(abc) < c

例如,(5, 27, 32)是一个abc匹配,因为:

  1. GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
  2. 5 < 27
  3. 5 + 27 = 32
  4. rad(4320) = 30 < 32

实际上,abc匹配是非常稀少的,对于c < 1000,只有31组abc匹配,在这些匹配中∑c = 12523。

对于c < 120000,求∑c。

 

 

 

 

 

P128:六边形地砖的差

标有数1的六边形地砖被一圈六个六边形地砖包围,这些地砖从12点钟方向(正上方)开始沿逆时针顺序依次标记为2至7。

在这个图形的外面,继续加上新的六边形地砖,接下来的几圈分别按照同样的规则标上8至19,20至37,38至61,依此类推。下图显示了前三圈所构成的图形。

考虑标有n的地砖与其周围六块地砖的差,我们定义PD(n)是这些差中素数的数目。

例如,按顺时针顺序,标有8的地砖与周围地砖的差是12,29,11,6,1和13。所以PD(8) = 3。

同样的,标有17的地砖与周围地砖的差是1,17,16,1,11和10,所以PD(17) = 2。

可以验证,PD(n)的最大值就是3。

如果所有PD(n) = 3的地砖构成从小到大排列的序列,那么第10块将是标有271的地砖。

找出这个序列中的第2000块地砖所标的数。

 

 

P129:循环单位数整除性

只包含数字1的数被称为循环单位数,我们定义R(k)是长为k的循环单位数,例如,R(6) = 111111。

如果n是一个整数,且GCD(n, 10) = 1,可以验证总存在k使得R(k)能够被n整除,并且记A(n)是这些k中最小的一个。例如,A(7) = 6,而A(41) = 5。

使得A(n)第一次超过十的n是17。

求使得A(n)第一次超过一千万的n。

 

 

P130:满足素数循环单位数性质的合数

只包含数字1的数被称为循环单位数,我们定义R(k)是长为k的循环单位数,例如,R(6) = 111111。

如果n是一个整数,且GCD(n, 10) = 1,可以验证总存在k使得R(k)能够被n整除,并且记A(n)是这些k中最小的一个。例如,A(7) = 6,而A(41) = 5。

已知对于素数p > 5,p − 1能够被A(p)整除。例如,当p = 41时,A(41) = 5,而40能够被5整除。

然而,有很少的一部分合数也满足这条性质,前5个这样的数分别是91,259,451,481以及703。

找出前25个合数n满足
GCD(n, 10) = 1且n − 1能够被A(n)整除,并求它们的和。