P141: 累进平方数 n 的研究

# P141: 累进平方数 n 的研究

TIP

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

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

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

求所有小于一万亿 (10^12) 的累进平方数之和.

# P142: 完全平方数收集

TIP

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

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

TIP

三角形 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: 一束激光多次反射的研究

TIP

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

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

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

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

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

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

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

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

下方的动画展现了激光束前十次反射的路径.

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

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

How many reversible numbers are there below one-billion?

有些正整数满足这样一种性质, 将它的数字逆序排列后和本身相加所得到的和的十进制表示只包含有奇数数字.

例如, 以及 .

我们称这样的数是可逆的;

因此和都是可逆的.

无论是还是都不允许出现前导 .

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

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

暴力吧....

告诉你一个不幸的消息, 其实一亿到10亿之间是没有可逆数的, 所以暴力到一亿就可以了...

坑啊, 累觉不爱

不暴力的数学方法也是有的:

UV[0] = 1;
UI[1] = 5;
UI[0 | 2 | 3] = R[0 | 1] = UV[1] = 0;
(* 30: 2 × [01, 03, 05, 07, 09, 12, 14, 16, 18, 23, 25, 27, 34, 36, 45] *)
UV[k_] := 30 * UV[k - 2]
(* 20: 2 × [12, 14, 16, 18, 23, 25, 27, 34, 36, 45] *)
UI[k_] := 5 * 5 * 20 * UI[k - 4]
R[k_] := 20 * UV[k - 2] + 20 * UI[k - 2]
R /@ Range[9] // Tr

其实可以求出甚至 :

$$ S(n)=\left{ \begin{array}{ll} \dfrac{20 }{14471}\left(29\cdot2^{n/2} 5^{\frac{3 n}{4}+1}+499\cdot30^{n/2}-644\right) & (n \bmod 4)=0 \ \dfrac{2}{14471 \sqrt{3}}\left(29 \sqrt{3}\cdot2^{\frac{n+1}{2}} 5^{\frac{1}{4} (3 n+5)}+499\cdot3^{n/2} 10^{\frac{n+1}{2}}-6440 \sqrt{3}\right) & (n \bmod 4)=1 \ \dfrac{2}{14471}\left(29\cdot2^{n/2} 5^{\frac{3 n}{4}+\frac{1}{2}}+499\cdot3^{n/2} 10^{\frac{n}{2}+1}-6440\right) & (n \bmod 4)=2 \ \dfrac{2}{14471 \sqrt{3}}\left(29 \sqrt{3}\cdot2^{\frac{n+3}{2}} 5^{\frac{1}{4} (3 n+11)}+499\cdot3^{n/2} 10^{\frac{n+1}{2}}-6440 \sqrt{3}\right) & (n \bmod 4)=3 \ \end{array}\right. $$

R[k_] := 1 / 3 10^(k / 2) (3^(k / 2) (1 + (-1)^k) - (3 5^(1 / 4 (-1 + k)) (-1 + (-1)^k + 2 Sin[(k \[Pi]) / 2])) / (2 Sqrt[2]))
S[n_] := Piecewise[{
    {(20 (-644 + 29 2^(n / 2) 5^(1 + (3 n) / 4) + 499 30^(n / 2))) / 14471, Mod[n, 4] == 0},
    {(2 (-6440 Sqrt[3] + 29 2^((1 + n) / 2) Sqrt[3] 5^(1 / 4 (5 + 3 n)) + 499 3^(n / 2) 10^((1 + n) / 2))) / (14471 Sqrt[3]), Mod[n, 4] == 1},
    {(2 (-6440 + 29 2^(n / 2) 5^(1 / 2 + (3 n) / 4) + 499 3^(n / 2) 10^(1 + n / 2))) / 14471, Mod[n, 4] == 2},
    {(2 (-6440 Sqrt[3] + 29 2^((3 + n) / 2) Sqrt[3] 5^(1 / 4 (11 + 3 n)) + 499 3^(n / 2) 10^((1 + n) / 2))) / (14471 Sqrt[3]), Mod[n, 4] == 3}
}];

R /@ Range[9] // Tr
S[9]

43:00

# P146: 素数模式研究

TIP

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

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

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

TIP

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

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

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

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

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

# P148: 探索帕斯卡三角

TIP

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


						1
					1		1
				1		2		1
			1		3		3		1
		1		4		6		4		1
	1		5		10		10		5		1
1		6		15		20		15		6		1

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

找出帕斯卡三角前十亿 (10^9) 行中不能被 7 整除的数的数目.

# P149: 寻找最大和子序列

TIP

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


-2	5	3	2
9	-6	5	1
3	2	7	3
-1	8	-4	8

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

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

对于 1 ⩽ k ⩽ 55, s_k = [100003 ? 200003k + 300007k^3] (modulo 1000000) ? 500000. 对于 56 ⩽ k ⩽ 4000000, s_k = [s_k?24 + s_k?55 + 1000000] (modulo 1000000) ? 500000.

如此一来, 可以得到 s_10 = ?393027, 而 s_100 = 86613.

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

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

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

TIP

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

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

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

^19 之间的伪随机数 s_k, 如下所示:

t := 0
for k = 1 up to k = 500500:
t  := (615949*t + 797807) modulo 2^20
sk := t-219

因此, , 依此类推.

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

s_1 s_2 s_3 s_4 s_5 s_6 s_7 s_8 s_9 s_10 …

子三角形可以从数组中的任意元素开始, 向下可以延伸至无限长 (先取下一行的两个元素, 再取接下来一行的三个元素, 依此类推).

"子三角形的和" 被定义为其中所有元素的和.

求最小的子三角形的和.

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]]

← Level131-140 Level151-160 →