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

 

 

发表评论