P91:格点直角三角形
点P(x1, y1)和点Q(x2, y2)都是格点，并与原点O(0,0)构成ΔOPQ。
看到这种题第一反应就是生成函....那啥....我又看出规律了.....
编号1-14,对于s×s的正方形,首先有三种简单的情况,就是1,2,10以及8,9,14这种直角在角上的.$3{s^2}$到手.
不在角上的就比较麻烦了...画个草图
设直角那个叫$P({x_1},{y_1})$.然后就是$P({x_1},{y_1}),Q({x_2},{y_2}),O({x_0},{y_0})$.
$$ \begin{aligned}
&\because OP \bot PQ \\
&\therefore \overrightarrow{OP} \cdot \overrightarrow{PQ} = 0 \\
&\Rightarrow {x_1}{x_2} + {y_1}{y_2} = x_1^2 + y_1^2
\end{aligned}$$
化简下,于是就从几何问题转化为了代数问题,求这个的整数解.这时候开始穷举也行,不过还能化简公式.
$$ \begin{aligned}
&\quad\ \left\{ \begin{gathered}
{x_2} = {x_1} + a\\
{y_2} = {y_1} + b\\
\end{gathered} \right.\\
&\Rightarrow a{x_1} + b{y_1} = 0\\
&\quad\ d = GCD({x_1},{y_1})\\
&\Rightarrow (a,b) = ( - \frac{{{y_1}}}{d}n,\frac{{{x_1}}}{d}n)\\
&\Rightarrow f(s) = Min(\frac{{{y_1}}}{{{x_1}}}d,\frac{{s - {x_1}}}{{{y_1}}}d)\\
&\Rightarrow S = \sum\limits_{0 < {x_1},{y_1} < s} {f(s)} + 3{s^2}
\end{aligned}$$
翻译成代码,根据对称性卡死${x_1} < {y_2}$,这样还可以少一半计算量,最后乘以2补回去.
1 | Function[s,2 Total[Array[Min@Quotient[{#2,s-#},{##}/GCD@##]&,{s,s}],2]+3 s^2]@50 |
92:平方数字链
将一个数的所有数字的平方相加得到一个新的数，不断重复直到新的数已经出现过为止，这构成了一条数字链。
例如，
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
可见，任何一个到达1或89的数字链都会陷入无尽的循环。更令人惊奇的是，从任意数开始，最终都会到达1或89。
有多少个小于一千万的数最终会到达89？
硬计算差评,还有我又一次没看到小于号.....虽然不影响结果...
1 2 3 | foo=Total[IntegerDigits[#]^2]&; bar[1]=1;bar[89]=89;bar[n_]:=bar[n]=bar@foo@n Tally[ParallelMap[bar,Range[1*^7]]] |
P93:算术表达式
使用集合{1, 2, 3, 4}中每个数字恰好一次以及(+, −, *, /)四则运算和括号，可以得到不同的正整数。
例如，
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)
注意不允许直接把数字连起来，如12 + 34。
使用集合{1, 2, 3, 4}，可以得到31个不同的数，其中最大值是36，以及1到28之间所有的数。
若使用包含有四个不同数字a < b < c < d的集合可以得到从1到n之间所有的数，求其中使得n最大的集合，并将你的答案写成字符串：abcd。
9个数字选4个,C(9,4)=126.四个符号选三个C(4,3)=4,7个位子8个空选两个放括号C(8,2)=28,全部乘起来也不大...
没括号的64种情况下是这样的,好吧我就是想秀一下我珍藏多年的强力函数.....
ListToExpression[list_]:=list//.({x___,PatternSequence[a_,u:#,b_],y___}:>{x,u[a,b],y}&/@{Power|Log|Surd,Times|Divide,Plus|Subtract});
OperatorRiffle[exp_,oper_:{Times,Divide,Plus,Subtract}] :=Grid[{#,ListToExpression@#}&/@(Riffle[exp,#]&/@Tuples[oper,Length@exp-1]),Alignment->Left];
OperatorRiffle[{a,b,c,d}]
虽然后来我想到这个其实直接变字符串然后连起来然后读回表达式就行....不过那样就无法装逼了...
而且这个方法对于Log,Surd这类非算子也有效,强制解释为最高级算子.而且运算优先级完全可以魔改,我就是规定加法优先乘法怎么着.....
注意相减算子是SubMinus,Minus是取负,不是个算子.MinusPlus, PlusMinus正负号,负正号这俩就连运算都不是了,只是个保留符号罢了.
Ok,回到这道题,不管怎么样我们就考虑怎么穷举出a,b,c,d的所有计算结果好了.
1 2 3 4 5 6 | AllResults[L_]:=If[Length[L]==1,L,DeleteDuplicates@Flatten@Table[ With[{c=AllResults@DeleteCases[L,x]},{x+c,x-c,x*c,x/c,c/x,c-x}],{x,L}]] FinalResults[L_]:=Sort@Select[AllResults[L],IntegerQ[#]&&#>0&] SeqLength[L_]:=With[{res=FinalResults@L},If[Length@res==0||First@res!=1, 0,First@FirstPosition[Differences@res,x_/;x!=1]]] MaximalBy[Subsets[Range[9],{4}],SeqLength] |
P94:几乎等边的三角形
可以证明，不存在边长为整数的等边三角形其面积也是整数。但是，存在几乎等边的三角形 5-5-6，其面积恰好为12。
我们定义几乎等边的三角形是有两条边一样长，且第三边与这两边最多相差1的三角形。
对于所有边长和面积均为整数且周长不超过十亿(1,000,000,000)的三角形，求其中几乎等边的三角形的周长之和。
底边不能是奇数,否则面积就会变成无理数.
设底边是$2n$,腰就是$2n \pm 1$,周长就是$6n \pm 2$,所以n的范围就出来了,然后只要判定高$\sqrt {5{n^2} \pm 4n + 1} $是否是整数就行了.
大概像这样 Select[Table[Sqrt[#1],{n,1*^6/3}],FractionalPart[#]==0&]&/@{1.0-4 n+5 n^2,1.0+4 n+5 n^2}
不行啊,周长10亿呢,得找个更强的公式...
设三边分别是$(a,b,c) = \left( {n,n,n + 1} \right)$
$$\begin{aligned}
S &= \frac{{n + 1}}{4}\sqrt {3{n^2} - 2n - 1} \\
&\Rightarrow 3{n^2} - 2n - 1 = {y^2}\\
&\Rightarrow n = \frac{{1 \pm \sqrt {3{y^2} + 4} }}{3}\\
&\Rightarrow {x^2} - 3{y^2} = 4,(x,y) \in {N_ + }
\end{aligned}$$
佩尔方程咯.....
Reduce[{x^2-3y^2==4,x>0,y>0},{x,y},Integers]
(14,8)对应的是(5,5,6)差了一项,要位移一格...
$$\left\{ \begin{gathered}
{x_{i + 1}} = {\left( {2 - \sqrt 3 } \right)^i} + {\left( {\sqrt 3 + 2} \right)^i}\\
{y_{i + 1}} = \frac{{{{\left( {\sqrt 3 + 2} \right)}^i} - {{\left( {2 - \sqrt 3 } \right)}^i}}}{{\sqrt 3 }}\\
\end{gathered} \right.$$
或者写成矩阵式就是
$$\left( {\begin{array}{*{20}{c}}
{{x_i}} \\ {{y_i}}
\end{array}} \right) = {\left( {\begin{array}{*{20}{c}}
2&3 \\ 1&2
\end{array}} \right)^i}\left( {\begin{array}{*{20}{c}}
4 \\ 2
\end{array}} \right)$$
然后代回原来的式子就行.
$\left( {n,n,n - 1} \right)$作同样的推导也是这个式子,这倒是省心了.
公式在手别说10亿了,10亿的平方都不怕了...
1 2 | list=Most@NestWhileList[{{2,3},{1,2}}.#&,{14,8},#[[1]]<1*^9-1&] Total@Map[If[Mod[First@#,3]==1,First@#-2,First@#+2]&,list] |
P95:亲和数链
一个数除了本身之外的因数称为真因数。例如，28的真因数是1、2、4、7和14。这些真因数的和恰好为28，因此我们称28是完全数。
有趣的是，220的真因数之和是284，同时284的真因数之和是220，构成了一个长度为2的链，我们也称之为亲和数对。
有一些更长的序列并不太为人所知。例如，从12496出发，可以构成一个长度为5的链：
找出所有元素都不超过一百万的亲和数链中最长的那条，并给出其中最小的那个数。
FindCycle[Graph[Table[i$$DirectedEdge](DivisorSigma[1,i]-i),{i,1,1*^5}]],Infinity]
然后大点就爆了.....Well......换个函数就好...ConnectedComponents.....
1 2 3 | data=Table[i$$DirectedEdge](DivisorSigma[1,i]-i),{i,1*^6-1}]; gra=GatherBy[ConnectedComponents@Graph@data,Length]; First[Sort@@Last@gra] |
P96:数独
数独（日语原意为数的位置）是一种热门的谜题。它的起源已不可考，但是与欧拉发明的一种类似而更加困难的谜题拉丁方阵之间有着千丝万缕的联系。数独的目标是替换掉9乘9网格中的空白位置（或0），使得每行、每列以及每个九宫格中恰好都包含数字1~9。一个构造精良的数独谜题应该包含有唯一解，且能够通过逻辑推断来解决，尽管有时可能必须通过“猜测并检验”来排除一些选项（这一要求目前还颇受争议）。寻找答案的复杂度决定了题目的难度；上面这个谜题被认为是简单的谜题，因为我们可以通过直截了当的演绎推理来解决它。
在这个6K的文本文件sudoku.txt（右击并选择“目标另存为……”）中包含有50个不同难度的数独谜题，但保证它们都只有唯一解（文件中的第一个谜题就是上述样例）。
解开这50个谜题，找出每个谜题解答左上角的三个数字并连接起来，给出这些数的和；举例来说，上述样例解答左上角的三个数字连接起来构成的数是483。
按例跳过未计时,另外回溯会超时,最好写逻辑判别.
1 2 3 | Get["https://raw.githubusercontent.com/GalAster/BiGridGenerator/master/BiGridGenerator/Kernel/Game/OtherGames.m"]; dat=Partition[ReadList["https://projecteuler.net/project/resources/p096_sudoku.txt",Byte,RecordLists->True],9,10,-10]-48; First@First@Flatten[Total[FromDigits/@OtherGames`SudokuSolverFast/@dat],1] |
P97:非梅森大素数
1999年人们发现了第一个超过一百万位的素数，这是一个梅森素数，可以表示为26972593−1，包含有2,098,960位数字。在此之后，更多形如2p−1的梅森素数被发现，其位数也越来越多。
然而，在2004年，人们发现了一个巨大的非梅森素数，包含有2,357,207位数字：28433×27830457+1。
找出这个素数的最后十位数字。
快速幂模,水过....
1 | Mod[28433 PowerMod[2, 7830457, 1*^10] + 1, 1*^10] |
P98:重排平方数
将单词CARE中的四个字母依次赋值为1、2、9、6，我们得到了一个平方数：1296 = 362。神奇的是，使用同样的数字赋值，重排后的单词RACE同样构成了一个平方数：9216 = 962。我们称CARE和RACE为重排平方单词对，同时规定这样的单词对不允许有前导零或是不同的字母赋相同的值。
在这个16K的文本文件words.txt（右击并选择“目标另存为……”）中包含了将近两千个常见英文单词，找出所有的重排平方单词对（一个回文单词不视为它自己的重排）。
重排平方单词对所给出的最大平方数是多少？
注意：所有的重排单词必须出现在给定的文本文件中。
没做出来...放弃....
本来以为So easy的,直接照着说明写一遍就好了,结果发现赋值情况有点多,直接上估计跑到明天都跑不完...
1 2 3 4 5 6 7 8 9 10 11 | data=Import["https://projecteuler.net/project/resources/p098_words.txt","CSV"][[1]]; Anagrams=Reverse[Select[Split[Sort[{Tally[Sort[Characters[#]]],#}&/@data], First[#1]==First[#2]&],Length@#>1&][[All,All,2]]]/.{a_,b_,c_}->Sequence[{a,b},{b,c},{a,c}]; (*SP=SequencePermutation*) SP[a:{_String,_String}]:=Module[{per,sqn,l}, per=FindPermutation[Sequence@@Characters/@a]; l=StringLength[First@a]; sqn=Select[#^2&/@Range[Floor[Sqrt[10^(l-1)]+1],Floor[Sqrt[10^(l)-If[EvenQ[l],1,0]]]], Tally[Characters[First@a]][[All,2]]==Tally[IntegerDigits[#]][[All,2]]&]; {a,Select[{#,FromDigits@(Permute[IntegerDigits@#,per])}&/@sqn,MemberQ[sqn,#[[2]]]&&#[[1]]!=#[[2]]&]}]; MaximalBy[Select[SP/@Anagrams,Last@#!={}&],Last@Last@#&] |
P99:最大的幂
比较两个如211和37这样写成幂的形式的数并不困难，任何计算器都能验证211 = 2048 < 37 = 2187。
然而，想要验证632382518061 > 519432525806就会变得非常困难，因为这两个数都包含有超过三百万位数字。
22K的文本文件base_exp.txt（右击并选择“目标另存为……”）有一千行，每一行有一对底数和指数，找出哪一行给出的幂的值最大。
注意：文件的前两行就是上述两个例子。
高精计算,哦不,其实就是取个对数....真水.....
1 2 | data=Import["https://projecteuler.net/project/resources/p099_base_exp.txt","CSV"]; Last@Ordering[N[#2 Log[#1]]&@@@data] |
P100:安排概率
在一个盒子中装有21个彩色碟子，其中15个是蓝的，6个是红的。如果随机地从盒子中取出两个碟子，取出两个蓝色碟子的概率是P(BB) = (15/21)×(14/20) = 1/2。
下一组使得取出两个蓝色盘子的概率恰好为50%的安排，是在盒子中装有85个蓝色碟子和35个红色碟子。
当盒子中装有超过1012 = 1,000,000,000,000个碟子时，找出第一组满足上述要求的安排，并求此时盒子中蓝色碟子的数量。
$$\left\{ \begin{aligned}
&\frac{{B(B - 1)}}{{N(N - 1)}} = \frac{1}{2}\\
&0 < B < {10^{12}} < N
\end{aligned} \right.$$
有点懵逼,简单过头了吧放这,大概是100题了给你们庆祝下.....
1 | Reduce[0<b<10^12<n&&2 b(b-1)==n(n-1),{b,n},Integers] |
58分30秒,欧耶,一小时内搞定,也就P93比较麻烦,其他稍微推导一下都能有思路.P96未计时,P98放弃.
