欧拉挑战:初阶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

发表评论