Hello
# /t
Timing on
# /p
Implicit printing on
# // Project Euler solutions
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 1 - Find the sum of all the multiples of 3 or 5 below 1000.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# k ~ 0;?+ 999 {? {!(_ % 3) | !(_ % 5)}{k ~ k + _}};]k
233168
[25ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 2 - By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# s ~ 0; i ~ 0; j ~ 1; ?+ {j < 4000000} {i ~ i + j; j ~ i - j; ? {j % 2 = 0}{s ~ s + j}}; ]s
4613732
[947us]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 3 - What is the largest prime factor of the number 600851475143 ?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# ]Range Factors 600851475143 ' 2
6857
[10ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 4 - Find the largest palindrome made from the product of two 3-digit numbers.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# ispalin () s ~ {+s = Rev s}
[9ms]
# max ~ 0;?+ 99 {i ~ _ + 900;?+ 99 {j ~ (_ + 900) * i; ? {j > max & (j % 10 = j /% 100000) & ispalin Str j}{max ~ j;]i,900 + _,max}}}
902 909 819918
902 914 824428
913 993 906609
[202ms]
# // Or after recognising 11 must be factor of one of the numbers
# max ~ 0;?+ 8 {i ~ 11 * _ + 891;?+ 99 {j ~ (_ + 900) * i; ? {j > max & (j % 10 = j /% 100000) & ispalin Str j}{max ~ j;]i,900 + _,max}}}
902 909 819918
902 914 824428
913 993 906609
[21ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 5 - What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# p~[[0]];?+ 19 { ? {#Factors (_+1) = 1}{p :: (_+1)}}
$0
[3ms]
# c ~ [[#p]]; Fill c 0
[ 0 0 0 0 0 0 0 0 ]
[3ms]
# update () c r ~ FillIf r (c>r) c
[3ms]
# ?+ 20 {update Freq Factors _ p c}
[ 4 2 1 1 1 1 1 1 ]
[4ms]
# mul () x:xs ~ {x * mul xs}{x}
[2ms]
# ]mul (p^c)
232792560
[8ms]
# ]$ % [1:20]
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[8ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 6 - Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# sum ~ 0;sumsq ~ 0; ?+ 100 { sum ~ sum + _; sumsq ~ sumsq + _^2 }; ]sum^2 - sumsq
25164150
[9ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 7 - What is the 10 001st prime number?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# last ~ 0;count ~ 0;?+ {count < 10002}{? {#Factors _ = 1}{last ~ _;count++}};]count-1,last
10001 104743
[5.205s]
# // this will miss 1 and 2 but skip all even values
# last ~ 0;count ~ 2;?+ {count < 10002}{? {#Factors (2 * _ + 1) = 1}{last ~ 2 * _ + 1;count++}};]count-1,last
10001 104743
[3.170s]
# // avoid complete factorisation for an alternative solution, but all the calculations are interpreted in this case, so much slower
# isoddprime () n ~ {i ~ 3; f ~ 0; r ~ Int (n ^ 0.5); ?+ {i <= r}{ ?: {n % i = 0}{f ~ 1; i ~ r + 1}{i++}}; !f}
[4ms]
# c ~ 0; last ~ 0; ?+ {c < 10000}{ ? {isoddprime (_ * 2 + 1)}{last ~ 2*_+1;c++}};] last
104743
[20.342s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 8 - Find the greatest product of five consecutive digits in the 1000-digit number.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# n~7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
[5ms]
# mul5 () n ~ ?: {n < 10000}{0}{ p~1;?+ {n}{p~p*(n%10);n~n/%10};p }
[4ms]
# max~0;?+ {n > 10000}{x~mul5 (n%100000); ? {x>max}{max~x};n~n/%10};]max
40824
[105ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 9 - There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# n~1000;?+ (n/%3) { a~_;b~a+1; ?+ {b<(n-a)/2} {c~n-b-a;? {c^2-b^2-a^2=0}{]a,b,c,a*b*c};b~b+1}}
200 375 425 31875000
[1.281s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 10 - Find the sum of all the primes below two million.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# ..
[4ms]
# // Direct calculation is possible but slow
# s~2;?+ 1000000 { ? {# Factors (2 * _ + 1) = 1}{s ~ s + 2 * _ + 1}};]s
142913828922
[159.323s]
# // Alternatively, use a sieve method
# n~2000000;m~[[n]];Fill m 0;m'1~1;s~0
[1.312s]
# ?+ n { ? {!m'_}{ s~s+_;j~2*_;i~_; ?+ {j<=n}{m'j~1;j~j+i} } };]s
142913828922
[46.322s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 11 - What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?
# //
# // 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
# // 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
# // 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
# // 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
# // 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
# // 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
# // 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
# // 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
# // 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
# // 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
# // 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
# // 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
# // 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
# // 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
# // 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
# // 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
# // 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
# // 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
# // 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
# // 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# grid ~ [ 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 ]
[6ms]
# Part grid 20
[ 8 2 22 97 38 15 0 40 0 75 4 5 7 78 52 12 50 77 91 8
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 4 56 62 0
81 49 31 73 5 ... ]
[4ms]
# downprod () grid i j ~ {s~1; ?+ 4 {s ~ s * grid'[i j];i++};s}
[5ms]
# leftprod () grid i j ~ {s~1; ?+ 4 {s ~ s * grid'[i j];j++};s}
[4ms]
# bdiagprod () grid i j ~ {s~1; ?+ 4 {s ~ s * grid'[i j];i++;j++};s}
[6ms]
# fdiagprod () grid i j ~ {s~1; ?+ 4 {s ~ s * grid'[i j];i--;j++};s}
[5ms]
# max~0;?+ 17 {i~_; ?+ 20 {j~_;s~downprod grid i j; ? {s>max}{max~s}}};]max
51267216
[25ms]
# max~0;?+ 20 {i~_; ?+ 17 {j~_;s~leftprod grid i j; ? {s>max}{max~s}}};]max
48477312
[31ms]
# max~0;?+ 17 {i~_; ?+ 17 {j~_;s~bdiagprod grid i j; ? {s>max}{max~s}}};]max
40304286
[31ms]
# max~0;?+ 17 {i~_+3; ?+ 17 {j~_;s~fdiagprod grid i j; ? {s>max}{max~s}}};]max
70600674
[38ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 12 - Find the first triangular number that has more than 500 divisors
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Fastest way is using the divisors counting function
# mul () v:vs ~ {v * mul vs}{v}
[4ms]
# ndiv () n ~ {fs ~ Factors n; v ~ 1 + Freq fs Unique fs; mul v}
[4ms]
# t~0;?+ {ndiv t <= 500}{t~t+_};]t
76576500
[1.772s]
# // Can also calculate the divisors explicitly
# t~0;?+ {#Divisors t <= 500}{t~t+_};]t
76576500
[6.597s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 13 - Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# n~37107287533902102798797998220837590246510135740250
[10ms]
# n~n+46376937677490009712648124896970078050417018260538
[5ms]
# n~n+74324986199524741059474233309513058123726617309629
[6ms]
# n~n+91942213363574161572522430563301811072406154908250
[19ms]
# n~n+23067588207539346171171980310421047513778063246676
[5ms]
# n~n+89261670696623633820136378418383684178734361726757
[7ms]
# n~n+28112879812849979408065481931592621691275889832738
[19ms]
# n~n+44274228917432520321923589422876796487670272189318
[666us]
# n~n+47451445736001306439091167216856844588711603153276
[671us]
# n~n+70386486105843025439939619828917593665686757934951
[6ms]
# n~n+62176457141856560629502157223196586755079324193331
[6ms]
# n~n+64906352462741904929101432445813822663347944758178
[23ms]
# n~n+92575867718337217661963751590579239728245598838407
[5ms]
# n~n+58203565325359399008402633568948830189458628227828
[11ms]
# n~n+80181199384826282014278194139940567587151170094390
[4ms]
# n~n+35398664372827112653829987240784473053190104293586
[5ms]
# n~n+86515506006295864861532075273371959191420517255829
[4ms]
# n~n+71693888707715466499115593487603532921714970056938
[4ms]
# n~n+54370070576826684624621495650076471787294438377604
[6ms]
# n~n+53282654108756828443191190634694037855217779295145
[3ms]
# n~n+36123272525000296071075082563815656710885258350721
[6ms]
# n~n+45876576172410976447339110607218265236877223636045
[1ms]
# n~n+17423706905851860660448207621209813287860733969412
[4ms]
# n~n+81142660418086830619328460811191061556940512689692
[5ms]
# n~n+51934325451728388641918047049293215058642563049483
[5ms]
# n~n+62467221648435076201727918039944693004732956340691
[5ms]
# n~n+15732444386908125794514089057706229429197107928209
[6ms]
# n~n+55037687525678773091862540744969844508330393682126
[11ms]
# n~n+18336384825330154686196124348767681297534375946515
[7ms]
# n~n+80386287592878490201521685554828717201219257766954
[7ms]
# n~n+78182833757993103614740356856449095527097864797581
[6ms]
# n~n+16726320100436897842553539920931837441497806860984
[5ms]
# n~n+48403098129077791799088218795327364475675590848030
[650us]
# n~n+87086987551392711854517078544161852424320693150332
[5ms]
# n~n+59959406895756536782107074926966537676326235447210
[4ms]
# n~n+69793950679652694742597709739166693763042633987085
[5ms]
# n~n+41052684708299085211399427365734116182760315001271
[9ms]
# n~n+65378607361501080857009149939512557028198746004375
[4ms]
# n~n+35829035317434717326932123578154982629742552737307
[6ms]
# n~n+94953759765105305946966067683156574377167401875275
[7ms]
# n~n+88902802571733229619176668713819931811048770190271
[609us]
# n~n+25267680276078003013678680992525463401061632866526
[5ms]
# n~n+36270218540497705585629946580636237993140746255962
[674us]
# n~n+24074486908231174977792365466257246923322810917141
[7ms]
# n~n+91430288197103288597806669760892938638285025333403
[5ms]
# n~n+34413065578016127815921815005561868836468420090470
[10ms]
# n~n+23053081172816430487623791969842487255036638784583
[4ms]
# n~n+11487696932154902810424020138335124462181441773470
[23ms]
# n~n+63783299490636259666498587618221225225512486764533
[6ms]
# n~n+67720186971698544312419572409913959008952310058822
[21ms]
# n~n+95548255300263520781532296796249481641953868218774
[663us]
# n~n+76085327132285723110424803456124867697064507995236
[10ms]
# n~n+37774242535411291684276865538926205024910326572967
[4ms]
# n~n+23701913275725675285653248258265463092207058596522
[5ms]
# n~n+29798860272258331913126375147341994889534765745501
[4ms]
# n~n+18495701454879288984856827726077713721403798879715
[6ms]
# n~n+38298203783031473527721580348144513491373226651381
[6ms]
# n~n+34829543829199918180278916522431027392251122869539
[4ms]
# n~n+40957953066405232632538044100059654939159879593635
[5ms]
# n~n+29746152185502371307642255121183693803580388584903
[4ms]
# n~n+41698116222072977186158236678424689157993532961922
[5ms]
# n~n+62467957194401269043877107275048102390895523597457
[6ms]
# n~n+23189706772547915061505504953922979530901129967519
[6ms]
# n~n+86188088225875314529584099251203829009407770775672
[622us]
# n~n+11306739708304724483816533873502340845647058077308
[25ms]
# n~n+82959174767140363198008187129011875491310547126581
[7ms]
# n~n+97623331044818386269515456334926366572897563400500
[6ms]
# n~n+42846280183517070527831839425882145521227251250327
[5ms]
# n~n+55121603546981200581762165212827652751691296897789
[6ms]
# n~n+32238195734329339946437501907836945765883352399886
[10ms]
# n~n+75506164965184775180738168837861091527357929701337
[6ms]
# n~n+62177842752192623401942399639168044983993173312731
[5ms]
# n~n+32924185707147349566916674687634660915035914677504
[4ms]
# n~n+99518671430235219628894890102423325116913619626622
[10ms]
# n~n+73267460800591547471830798392868535206946944540724
[6ms]
# n~n+76841822524674417161514036427982273348055556214818
[10ms]
# n~n+97142617910342598647204516893989422179826088076852
[6ms]
# n~n+87783646182799346313767754307809363333018982642090
[13ms]
# n~n+10848802521674670883215120185883543223812876952786
[4ms]
# n~n+71329612474782464538636993009049310363619763878039
[3ms]
# n~n+62184073572399794223406235393808339651327408011116
[3ms]
# n~n+66627891981488087797941876876144230030984490851411
[10ms]
# n~n+60661826293682836764744779239180335110989069790714
[5ms]
# n~n+85786944089552990653640447425576083659976645795096
[4ms]
# n~n+66024396409905389607120198219976047599490197230297
[5ms]
# n~n+64913982680032973156037120041377903785566085089252
[4ms]
# n~n+16730939319872750275468906903707539413042652315011
[4ms]
# n~n+94809377245048795150954100921645863754710598436791
[1ms]
# n~n+78639167021187492431995700641917969777599028300699
[6ms]
# n~n+15368713711936614952811305876380278410754449733078
[6ms]
# n~n+40789923115535562561142322423255033685442488917353
[4ms]
# n~n+44889911501440648020369068063960672322193204149535
[5ms]
# n~n+41503128880339536053299340368006977710650566631954
[882us]
# n~n+81234880673210146739058568557934581403627822703280
[5ms]
# n~n+82616570773948327592232845941706525094512325230608
[608us]
# n~n+22918802058777319719839450180888072429661980811197
[5ms]
# n~n+77158542502016545090413245809786882778948721859617
[5ms]
# n~n+72107838435069186155435662884062257473692284509516
[16ms]
# n~n+20849603980134001723930671666823555245252804609722
[6ms]
# n~n+53503534226472524250874054075591789781264330331690
[16ms]
# ]n
5537376230390876637302048746832985971773659831892672
[5ms]
# ]n/%10^42
5537376230
[20ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 14 - Collatz sequence: n->n/2 if n even, n->3n+1 if n odd
# // Find the longest chain starting with a number less than 1 million
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# ..
[42ms]
# // First explore some sequences
# next () %n ~ ?: {n%2}{3*n+1}{n/2}
[507us]
# collatz () n ~ {c~0;?+ {n>1}{]%n,"";n~next n;c~_};]1;c+1}
[594us]
# ?+ 10 {]%_:":\t";collatz _}
1: 1
2: 2 1
3: 3 10 5 16 8 4 2 1
4: 4 2 1
5: 5 16 8 4 2 1
6: 6 3 10 5 16 8 4 2 1
7: 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
8: 8 4 2 1
9: 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
10: 10 5 16 8 4 2 1
[9ms]
# // Brute force calculation takes several minutes
# collatz () n ~ {c~0;?+ {n>1}{n~next n;c~_};c+1} // don't want to print this time
[5ms]
# max~0;?+ 1000000 {c~collatz _; ? {c>max}{max~c;n~_;] max,n}}
1 1
2 2
8 3
9 6
17 7
20 9
21 18
24 25
112 27
113 54
116 73
119 97
122 129
125 171
128 231
131 313
144 327
145 649
171 703
179 871
182 1161
183 2223
209 2463
217 2919
238 3711
262 6171
268 10971
276 13255
279 17647
282 23529
308 26623
311 34239
324 35655
340 52527
351 77031
354 106239
375 142587
383 156159
386 216367
443 230631
449 410011
470 511935
509 626331
525 837799
[1818.022s]
# // Quite a bit faster to avoid functions entirely, but still takes several minutes
# max~0;?+ 1000000 {c~0;n~_;?+ {n>1}{n~?: {n%2}{3*n+1}{n/2};c~_};c++; ? {c>max}{max~c;n~_;] max,n}}
1 1
2 2
8 3
9 6
17 7
20 9
21 18
24 25
112 27
113 54
116 73
119 97
122 129
125 171
128 231
131 313
144 327
145 649
171 703
179 871
182 1161
183 2223
209 2463
217 2919
238 3711
262 6171
268 10971
276 13255
279 17647
282 23529
308 26623
311 34239
324 35655
340 52527
351 77031
354 106239
375 142587
383 156159
386 216367
443 230631
449 410011
470 511935
509 626331
525 837799
[977.219s]
# // Maintaining a history of chain lengths improves the performance considerably
# m~1000000
[3ms]
# max~0
[3ms]
# cs~[[m]];Fill cs 0
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... ]
[66ms]
# ?+ m { n~_; c~0; ?+ {n>1}{n~?: {n%2}{3*n+1}{n/2};c++;? {n<m & cs'n}{c~c+cs'n;><}}; cs'_~c; ? {c>max}{]c+1,_;max~c}}
2 2
8 3
9 6
17 7
20 9
21 18
24 25
112 27
113 54
116 73
119 97
122 129
125 171
128 231
131 313
144 327
145 649
171 703
179 871
182 1161
183 2223
209 2463
217 2919
238 3711
262 6171
268 10971
276 13255
279 17647
282 23529
308 26623
311 34239
324 35655
340 52527
351 77031
354 106239
375 142587
383 156159
386 216367
443 230631
449 410011
470 511935
509 626331
525 837799
[68.764s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 15 - Starting in the top left corner of a 20x20 grid, how many routes are there (without backtracking) to the bottom right corner?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // The problem is simply to choose 20 right turns from 40 possibilities
# ]BiCo 40 20
137846528820
[4ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 16 - What is the sum of the digits of the number 2^1000?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# n~2^1000;s~0;?+ {n>0}{s~s+n%10;n~n/%10};]s
1366
[8ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 17 - If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
# // NOTE: Do not count spaces or hyphens.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // It's a nice problem just to do the conversion to word form
# // first a function to handle 1 to 99
# a~["one" "two" "three" "four" "five" "six" "seven" "eight" "nine" "ten" "eleven" "twelve" "thirteen" "fourteen" "fifteen" "sixteen" "seventeen" "eighteen" "nineteen"]
[3ms]
# b~["twenty" "thirty" "forty" "fifty" "sixty" "seventy" "eighty" "ninety"]
[4ms]
# words () a b n ~ ?: {n<20}{a'n}{t~n/%10-1;r~n%10;?: {r=0}{b't}{+(b't) :: "-" :: a'r}}
[5ms]
# // note the copy operation because join works in place
# ]words a b 4
four
[4ms]
# ]words a b 14
fourteen
[34ms]
# ]words a b 34
thirty-four
[4ms]
# // now go to 1000
# words2 () a b n ~ ?: {n=1000}{"one thousand"}{+(a'(n/%100)) :: " hundred"}
[10ms]
# words3 () a b n ~ ?: {n<100}{words a b n}{?: {n%100=0}{words2 a b n}{+(a'(n/%100)) :: " hundred and " :: (words a b (n%100))}}
[4ms]
# ]words3 a b 472
four hundred and seventy-two
[4ms]
# v~ [1 9 10 12 27 127 300 989 1000]
[4ms]
# ?+ v {]_,"\t",words3 a b _}
1 one
9 nine
10 ten
12 twelve
27 twenty-seven
127 one hundred and twenty-seven
300 three hundred
989 nine hundred and eighty-nine
1000 one thousand
[5ms]
# s~0;?+ 1000 {s~s+#words3 a b _};]s
24527
[94ms]
# // but this counts spaces - so now just look at the lengths
# a~[3 3 5 4 4 3 5 5 4 3 6 6 8 8 7 7 9 8 9]
[3ms]
# b~[6 6 5 5 5 7 6 6]
[13ms]
# length () a b n ~ ?: {n<20}{a'n}{t~n/%10-1;r~n%10;?: {r=0}{b't}{b't + a'r}}
[12ms]
# length2 () a b n ~ ?: {n=1000}{11}{a'(n/%100) + 7}
[3ms]
# length3 () a b n ~ ?: {n<100}{length a b n}{?: {n%100=0}{length2 a b n}{a'(n/%100) + 10 + (length a b (n%100))}}
[3ms]
# s~0;?+ 1000 {s~s+length3 a b _};]s
21134
[78ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 18 - Find the maximum total from top to bottom of the triangle below:
# //
# // 75
# // 95 64
# // 17 47 82
# // 18 35 87 10
# // 20 04 82 47 65
# // 19 01 23 75 03 34
# // 88 02 77 73 07 63 67
# // 99 65 04 28 06 16 70 92
# // 41 41 26 56 83 40 80 70 33
# // 41 48 72 33 47 32 37 16 94 29
# // 53 71 44 65 25 43 91 52 97 51 14
# // 70 11 33 28 77 73 17 78 39 68 17 57
# // 91 71 52 38 17 14 91 43 58 50 27 29 48
# // 63 66 04 68 89 53 67 30 73 16 69 87 40 31
# // 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# max~.
[3ms]
# max () a b ~ ?: {a > b}{a}{b}
[3ms]
# squish () a i ~ {q~a'i;r~a'(i+1); ?+ (#q) {q'_ ~ q'_ + max (r'_) (r'(_+1)) };a'i~q}
[10ms]
# a~[ [75] [95 64] [17 47 82] [18 35 87 10] [20 04 82 47 65] [19 01 23 75 03 34] [88 02 77 73 07 63 67] [99 65 04 28 06 16 70 92] [41 41 26 56 83 40 80 70 33] [41 48 72 33 47 32 37 16 94 29] [53 71 44 65 25 43 91 52 97 51 14] [70 11 33 28 77 73 17 78 39 68 17 57] [91 71 52 38 17 14 91 43 58 50 27 29 48] [63 66 04 68 89 53 67 30 73 16 69 87 40 31] [04 62 98 27 23 09 70 98 73 93 38 53 60 04 23]]
[14ms]
# ?+ a {]_}
[ 75 ]
[ 95 64 ]
[ 17 47 82 ]
[ 18 35 87 10 ]
[ 20 4 82 47 65 ]
[ 19 1 23 75 3 34 ]
[ 88 2 77 73 7 63 67 ]
[ 99 65 4 28 6 16 70 92 ]
[ 41 41 26 56 83 40 80 70 33 ]
[ 41 48 72 33 47 32 37 16 94 29 ]
[ 53 71 44 65 25 43 91 52 97 51 14 ]
[ 70 11 33 28 77 73 17 78 39 68 17 57 ]
[ 91 71 52 38 17 14 91 43 58 50 27 29 48 ]
[ 63 66 4 68 89 53 67 30 73 16 69 87 40 31 ]
[ 4 62 98 27 23 9 70 98 73 93 38 53 60 4 23 ]
[5ms]
# n~#a-1;?+ {n}{squish a n;n--};]a'1'1
1074
[8ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 19 - How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // days in month data
# days~[31 28 31 30 31 30 31 31 30 31 30 31]
[4ms]
# leapdays~[31 29 31 30 31 30 31 31 30 31 30 31]
[4ms]
# // leap year checking function
# isleap () yr ~ yr % 4 = 0 & (yr % 100 != 0 | yr % 400 = 0)
[4ms]
# // we know the first day of 1900 was a Monday (d=1), so work through 1900 to find first day of 1901
# // keep the previous month start day in the global variable 'dglobal'
# dglobal~1
[4ms]
# ?+ days{dglobal~(dglobal+_)%7}
[4ms]
# ]dglobal
2
[3ms]
# // this shows the first day for 1901 is 2 (Tuesday)
# // function to check all months in a year - return count, update dglobal
# sunstarts () d days ~ {c~0;?+ days{d~(d+_)%7;? {!d}{c++}};_dglobal~d;c}
[11ms]
# // work through 1901 to 2000
# count~0
[3ms]
# ?+ 100 { ls ~ ?: {isleap (_ + 1900)}{leapdays}{days}; count~count+sunstarts dglobal ls}
[36ms]
# ]count
171
[4ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 20 - Find the sum of the digits in the number 100!
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# n~Fact 100;s~0;?+ {n>0}{s~s+n%10;n~n/%10};]s
648
[10ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 21 - Evaluate the sum of all the amicable numbers under 10000.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# sum () x:xs ~ { x + sum xs } { x }
[4ms]
# amicable () n ~ {k~sum Divisors n - n; j~sum Divisors k - k; ?: {j>1 & j=n & j!=k}{]n,k;n}{0}}
[4ms]
# s~0;?+ 10000 {s~amicable _ + s};]s
220 284
284 220
1184 1210
1210 1184
2620 2924
2924 2620
5020 5564
5564 5020
6232 6368
6368 6232
31626
[3.439s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 22 - What is the total of all the name scores in the file?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // from file
# f ~ FOpenCSV "names.txt" "r"
[10ms]
# names ~ FRead f 20000
[476ms]
# FClose f
NaN
[6ms]
# names ~ names'1
[11ms]
# Sort names // sorts in place
[ AARON ABBEY ABBIE ABBY ABDUL ABE ABEL ABIGAIL ABRAHAM ABRAM ADA ADAH ADALBERTO ADALINE ADAM ADAN ADDIE ADELA ADELAIDA ADELAIDE ADELE ADELIA ADELINA ADELINE ADELL ADELLA ADELLE ADENA ... ]
[5ms]
# score () s p ~ {t~0;o~"A"'1-1;?+ (#s) {t~t+s'_};t~p * (t-#s*o)}
[4ms]
# a~0;?+ (#names){a~a+score (names'_) _};]a
871198282
[5.459s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 23 - Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# ..
[29ms]
# sum () x:xs ~ { x + sum xs } { x }
[4ms]
# abund () %x ~ sum Divisors x - x > x
[3ms]
# n~21200
[3ms]
# a~[[n]]
[5ms]
# Fill a 0
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... ]
[4ms]
# ?+ n {? {abund _}{a'_~1}}
[3.969s]
# check () a i ~ {j~12;b~0;?+ {j<=i/2 & !b}{? {a'j & a'(i-j)}{b~1};j++};b}
[10ms]
# s~0;?+ 23 {i~2*_;? {!check a i}{s~s+i}}
[11ms]
# ?+ (Int (n/2)) {i~2*_-1;? {!check a i}{s~s+i}};]s
4179871
[646.794s]
# // loop only over the odd abundant numbers for the odd case check
# ..
[6ms]
# sum () x:xs ~ { x + sum xs } { x }
[4ms]
# abund () %x ~ sum Divisors x - x > x
[4ms]
# n~21200
[3ms]
# a~[[n]]
[4ms]
# Fill a 0
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... ]
[4ms]
# b~[]
[3ms]
# ?+ n {? {abund _}{b :: _}}
[ 12 18 20 24 30 36 40 42 48 54 56 60 66 70 72 78 80 84 88 90 96 100 102 104 108 112 114 120 126 132 138 140 144 150 156 160 162 168 174 176 180 186 192 196 198 200 204 208 210 21 ... ]
[4.963s]
# bodd ~ b ## (b%2)
[5ms]
# beven ~ b ## (!(b%2))
[12ms]
# // odd check is odd + even
# // even check is either odd + odd or even + even
# // and even max is 46 (prove it? or use the 746 proof below?)
# bigeven () n ~ n%2=0 & n>46
[3ms]
# FnFill a @bigeven
[ $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $1 $0 $1 $0 $1 $0 $1 $0 $1 $0 $1 $0 ... ]
[95ms]
# // check odd
# ?+ beven {i~_; ?+ bodd {?: {i+_<=n}{a'(i+_)~1}{><}}}
0
[12.147s]
# // check even (only up to 46)
# beven ~ b ## (b < 46)
[5ms]
# ?+ beven {]i~_; ?+ beven {?: {i+_<=n}{a'(i+_)~1}{><}}}
12
18
20
24
30
36
40
42
[13ms]
# // since the smallest odd abundant number is 945, we do not need to check the sum of any two odd abundant numbers
# s~0;?+ n { ? {a'_=0}{s~s+_}};]s
4179871
[1.991s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 24 - What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# f () n a ~ Int (n / Fact (#a - 1))
[4ms]
# a~[0:9];r~[];n~999999
[4ms]
# ?+ {#a}{i~f n a;n~n-i*Fact (#a - 1);i++;r::a'i;a'i~.;]a,r}
[ 0 1 3 4 5 6 7 8 9 ] [ 2 ]
[ 0 1 3 4 5 6 8 9 ] [ 2 7 ]
[ 0 1 3 4 5 6 9 ] [ 2 7 8 ]
[ 0 1 4 5 6 9 ] [ 2 7 8 3 ]
[ 0 1 4 5 6 ] [ 2 7 8 3 9 ]
[ 0 4 5 6 ] [ 2 7 8 3 9 1 ]
[ 0 4 6 ] [ 2 7 8 3 9 1 5 ]
[ 0 6 ] [ 2 7 8 3 9 1 5 4 ]
[ 0 ] [ 2 7 8 3 9 1 5 4 6 ]
[ ] [ 2 7 8 3 9 1 5 4 6 0 ]
[5ms]
# // Brute force method (much slower)
# a~[1 2 3 4 5 6 7 8 9 10];?+ 999999{a ~ NextPerm a 10};]a - 1
[ 2 7 8 3 9 1 5 4 6 0 ]
[99.161s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 25 - What is the first term in the Fibonacci sequence to contain 1000 digits?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# i~1;j~1;?+ {Log j < 999}{j~i+j;i~j-i;c~_};]c+2,j
4782 107006626638275893676498058445739688508368389663215166501323520337531452060469404062188914758248979265780469488817759195748433646667256995951299603046126274809248218614406943305..
[523ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 26 - Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# mul () x:xs ~ {x * mul xs}{x}
[4ms]
# reduce () n ~ {fs ~ Factors n; fs ~ fs ## ((fs != 2) & (fs != 5)); ?: {#fs}{mul fs}{1}}
[4ms]
# len () n ~ ?: {n > 1}{a~10 % n; l~1; ?+ {a!=1}{a~a*10;a~a%n;l++};l}{0}
[5ms]
# max~0;?+ 999 {l~len reduce _; ? {l>max}{max~l;n~_}};]n,max
983 982
[9.550s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 27 - Find the product of the coefficients, for the quadratic expression that produces the maximum number of primes for consecutive values of n
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# isprime () n ~ #Factors n = 1
[4ms]
# poly () a b n ~ n*n+a*n+b
[4ms]
# max~0;r~0
[11ms]
# ?+ 1000{a~2*_-1001;?+ 1000{? {isprime _}{b~_;c~1;?+ {isprime poly a b _}{c++};? {c>max}{max~c;r~a*b}}}}
$0
[33.885s]
# ]max,r
71 -59231
[4ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 28 - What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# i~1;s~1;?+ 500 {d~2*_;?+ 4 {i~i+d;s~s+i}};]s
669171001
[13ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 29 - How many distinct terms are in the sequence generated by a^b for 2 <= a <= 100 and 2 <= b <= 100?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# e29 () n ~ {c~[];?+ (n-1) { a~_+1;?+ (n-1) {b~_+1;c::a^b}};Sort Unique c}
[6ms]
# ]#e29 100
9183
[2.166s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 30 - Digit fifth powers
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // find the upper limit and save as max
# ?+ 10 {? {Log (_*9^5) < _}{]max~_*9^5;><>}}
354294
[23ms]
# // define a function that adds powers of digits
# add5 () n p ~ {s~0;?+ {n}{s~s+(n%10)^p;n~n/%10};s}
[4ms]
# // search and sum, removing 1
# s ~ 0; ?+ max {? {add5 _ 5 = _}{s ~ s + _}}; s--
443839
[15.325s]
# ]s
443839
[4ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 31 - How many different ways can 2 pounds be made using any number of coins?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# data ~ [[201]]
[4ms]
# Fill data 0
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... ]
[4ms]
# data'1 ~ 1
[4ms]
# coins ~ [1 2 5 10 20 50 100 200]
[4ms]
# ?+ coins {c~_;m~1; ?+ {j~m+c;j<=201}{data'j~data'j+data'm;m++}}
2
[14ms]
# ]data'201
73682
[4ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 32 - Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# m~.;sum~.
[4ms]
# accept () m n ~ {a ~ Split m :: Split n :: Split (m * n); #Unique a = 9 & !(0<-a)}
[4ms]
# ns~[[0]]
[4ms]
# // 1 digit * 4 digit = 4 digit
# ?+ 7 {m~_+1;r~Int (10000/m); ?+ r {? {accept m _}{]m,_,m*_;ns::m*_}}}
4 1738 6952
4 1963 7852
[678ms]
# // 2 digit * 3 digit = 4 digit
# ?+ 86 {m~_+11;r~Int (10000/m); ?+ r {? {accept m _}{]m,_,m*_;ns::m*_}}}
12 483 5796
18 297 5346
27 198 5346
28 157 4396
39 186 7254
42 138 5796
48 159 7632
[849ms]
# sum () x:xs ~ {x + sum xs}{x}
[3ms]
# ]sum Unique ns
45228
[3ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 33 - Digit cancelling fractions
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# check () n d ~ {n1~Int (n/10);n2~n%10;d1~Int (d/10);d2~d%10; ? {(n1=d2 & n2/d1=n/d) | (n2=d1 & n1/d2=n/d)}{]n,d,n/d}}
[3ms]
# ?+ 100 { ? {_>10 & _%10} {n~_; ?+ (100-n) {d~_+n; ? {d%10 } { check n d } } } }
16 64 1/4
19 95 1/5
26 65 2/5
49 98 1/2
[145ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 34 - Find the sum of all numbers which are equal to the sum of the factorial of their digits
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# m~.
[4ms]
# factsum () x:xs ~ {Fact x + factsum xs}{Fact x}
[4ms]
# m () k ~ Log k - k + Log Fact 9
[4ms]
# Solve @m 1 100 10
6.3634560841554
[4ms]
# max ~ 10^$
[3ms]
# ]max
2309170.9438183
[3ms]
# s~-3;?+ max {? {factsum Split _ = _}{s~s+_;]_}}
1
2
145
40585
[201.999s]
# ]s
40730
[3ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 35 - How many circular primes are there below one million?
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# isprime () n ~ #Factors n = 1
[4ms]
# rotate () n ~ {x~10^Int Log n; d~n%10;d*x+n/%10}
[3ms]
# // this will include 1 and but skip 2 and 5, so start count from 1
# count~1;?+ 500000 {n~2*_-1;? {n%5 & isprime n}{d~Int Log n + 1;c~0;?+ d {n~rotate n;?: {isprime n}{c++}{><}};? {c=d}{count++}}}
$0
[65.479s]
# ]count
55
[4ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 36 - Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# ispalin () s ~ {+s = Rev s}
[3ms]
# s~0;?+ 1000000 {? {ispalin Str _ & ispalin Str Base _ 2}{]_;s ~ s + _}};]s
1
3
5
7
9
33
99
313
585
717
7447
9009
15351
32223
39993
53235
53835
73737
585585
872187
[30.674s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 37 - Truncatable Primes
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# ..
[10ms]
# isprime () n ~ n>1 & #Factors n=1
[3ms]
# truncR2L () n ~ ?+ {n & isprime n}{n~Combine (`Split n)}{><};n}
[10ms]
# truncR2L () n ~ {?+ {n & isprime n}{n~Combine (`Split n)}{><};n}
[11ms]
# truncL2R () n ~ {?+ {n & isprime n}{n~n/%10}{><};n}
[4ms]
# trunc () n ~ !truncL2R n & !truncR2L n
[3ms]
# count~0; sum~0
[3ms]
# ?+ {count<11}{n1~6*(_+1)-1;n2~n1+2;? {isprime n1 & trunc n1}{]n1,count++,sum~sum+n1}; ? {isprime n2 & trunc n2}{]n2,count++,sum~sum+n2}}
23 1 23
37 2 60
53 3 113
73 4 186
313 5 499
317 6 816
373 7 1189
797 8 1986
3137 9 5123
3797 10 8920
739397 11 748317
[49.586s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 38 - Pandigital multiples
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# check () max min n ~ {?+ (max-min) {i~_+min;a~[1:n]*i;d~Int Combine Str a;? {#Unique Split d=9 & !(0<-Split d)}{]i,d}}}
[3ms]
# check 9 6 5
9 918273645
[4ms]
# check 329 123 3
192 192384576
219 219438657
273 273546819
327 327654981
[15ms]
# check 9876 1234 2
6729 672913458
6792 679213584
6927 692713854
7269 726914538
7293 729314586
7329 732914658
7692 769215384
7923 792315846
7932 793215864
9267 926718534
9273 927318546
9327 932718654
[424ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 39 - Integer right triangles
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# ?+ 499{n~(1000-2*_);i~0;?+ (n/%3) { a~_;b~a+1; ?+ {b<(n-a)/2} {c~n-b-a;? {c^2-b^2-a^2=0}{i++};b++}};? {i>3}{]1000-2*_,i}}
990 4
960 4
924 5
900 4
840 8
780 4
756 4
720 6
672 4
660 5
630 4
504 4
480 4
420 5
360 4
240 4
[172.141s]
# // much faster
# ?+ 500{p~2*_;t~0;a~2; ?+ {a<p}{b~p*(p-2*a)/(2*p-2*a); ? {b<a}{><}; ? {b=Int b}{t++};a++};? {t>3}{]t,p}}
4 240
4 360
5 420
4 480
4 504
4 630
5 660
4 672
6 720
4 756
4 780
8 840
4 900
5 924
4 960
4 990
[1.159s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 40 - Champernowne's constant
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // brute force method
# ]s~Combine Str [1:1000000]
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283...
[749ms]
# ]d~10^([1:7]-1)
[ 1 10 100 1000 10000 100000 1000000 ]
[741ms]
# mul () x:xs ~ {x * mul xs}{x}
[3ms]
# ]r~Int Split s'd
[ 1 1 5 3 7 2 1 ]
[20.085s]
# ]mul r
210
[5.001s]
# // digit calculation method
# sum9 () n ~ {s~0; ?+ n {s~s+_*9*10^(_-1)};s}
[3ms]
# // this gives the digit place range for values from 10^(n-1) to 10^n - 1
# range () n ~ [(sum9 (n-1)+1) (sum9 n)]
[3ms]
# d~10^([1:7]-1)
[3ms]
# getdig () f ~ {a~Split f;n~a'1;d~?: {#a>1}{a'2}{1};v~Int f;n~n%d;?: {n}{v++;Split v'n}{:Rev Split v}}
[3ms]
# v~1;?+ d {l~1;e~_;?+ {r~range l;e>r'2}{l++};res~(e-r'1+1)/l+(10^(l-1)-1);v~v*getdig res}
[5ms]
# ]v
210
[3ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 41 - Pandigital prime
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# isprime () n ~ #Factors n=1
[3ms]
# tonum () x:xs ~ {10 * tonum xs + x}{x}
[3ms]
# sum () x:xs ~ {x + sum xs}{x}
Evaluation failed: clash of variable and function name because of 'sum () x:xs ~ {x + sum xs}{x}'
[7ms]
# panprime () n ~ {max~0;a~[1:n];?+ {a}{v~tonum Rev (+a);? {isprime v}{max~v};a~NextPerm a n;max}}
[3ms]
# ?+ 8 {]_+1,? {sum [1:_+1]%3}{panprime (_+1)}}
2 0
3 0
4 4231
5 0
6 0
7 7652413
8 0
9 0
[262.251s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 42 - Coded triangle numbers
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // from file
# f ~ FOpenCSV "words.txt" "r"
[3ms]
# words ~ FRead f 20000
[169ms]
# FClose f
NaN
[5ms]
# score () s ~ {t~0;o~"A"'1-1;?+ (#s) {t~t+s'_-o}}
[3ms]
# istriangular () t ~ {i ~ (-1 + (1 + 8 * t)^(1/2)) / 2; Int i = i}
[3ms]
# count~0;?+ (words'1){? {istriangular score _}{count++}};]count
162
[492ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 43 - Sub-string divisibility
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# sum~.
[3ms]
# ps ~ [1 2 3 5 7 11 13 17]
[3ms]
# get3 () ds i ~ {sub~ds'[i:i+2];sub'1*100+sub'2*10+sub'3}
[3ms]
# tonum () x:xs ~ {10 * tonum xs + x}{x}
[3ms]
# checkdiv () ds ~ {?: {ds'1 & (ds'6=5)}{i~0;?+ 7 {j~9-_;g~get3 ds j;?: {g%_ps'j}{><}{i~_}};i}{0}}
[3ms]
# pandiv () ~ {sum~0;a~[1:10];?+ {a}{q~a-1;? {checkdiv q = 7}{v~tonum Rev q;]v,sum~sum+v};a~NextPerm a 10;sum}}
[3ms]
# ]pandiv
1406357289 1406357289
1430952867 2837310156
1460357289 4297667445
4106357289 8404024734
4130952867 12534977601
4160357289 16695334890
16695334890
[286.808s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 44 - Pentagon numbers
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# ispent () n ~ ??((24*n+1)^(1/2)+1)/6="integer"
[3ms]
# pent () n ~ n*(3*n-1)/2
[4ms]
# done~0;?+ {!done} {s~_+1; p1~pent s; ?+ (s-1){p2~pent (s-_); ? {ispent (p1+p2) & ispent (p1-p2)}{done~1;]s,_,p1,p2,p1-p2}}}
2167 1147 7042750 1560090 5482660
[174.691s]
#
[3us]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 45 - Find the next triangle number (after H143) that is also pentagonal and hexagonal.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Every hexagonal number is a triangular number, so only need to check hexagonal and pentagonal.
# hex () n ~ n * (2 * n - 1)
[3ms]
# ispent () p ~ {i ~ (1 + (1 + 24 * p)^(1/2)) / 6; Int i = i}
[3ms]
# n~1;?+ {!ispent hex n}{n++};]n,hex n
1 1
[3ms]
# n~2;?+ {!ispent hex n}{n++};]n,hex n
143 40755
[14ms]
# n~144;?+ {!ispent hex n}{n++};]n,hex n
27693 1533776805
[1.836s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 46 - Goldbach's other conjecture
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# isprime () n ~ #Factors n = 1
[4ms]
# test () n ~ {found~0;diff~1; ?+ {diff>0}{diff~n-2*_^2;? {isprime diff}{found ~ $1;><}}; ? {!found}{]n,diff,_}; found}
[3ms]
# run~1;?+ {run} {n~2*_+1; ? {!isprime n}{run~test n}}
5777 -55 2888
[884ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 47 - Distinct prime factors
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# nfact () n ~ #Unique Factors n
[4ms]
# n~1;done~$0
[4ms]
# ?+ {!done}{ ?: {nfact n > 3 & nfact (n+1) > 3 & nfact (n+2) > 3 & nfact (n+3) > 3}{]n,n+1,n+2,n+3;done~$1}{n++}}
134043 134044 134045 134046
[18.689s]
# n~4;a~[[n]];Fill a 0;done~$0
[4ms]
# ?+ {!done}{i~_%n+1;a'i~nfact _; ? {ArrayCmp (a>3) $1}{]_-3,_-2,_-1,_;done~$1}}
134043 134044 134045 134046
[16.040s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 48 - Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# k~0;?+ 1000 {k ~ k + _^_};]k % 10^10
9110846700
[57ms]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 49 - Prime permutations
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# ps~[]
[4ms]
# isprime () n ~ #Factors n=1
[3ms]
# ?+ 1501{ n1~996+6*_-1;n2~n1+2;? {isprime n1}{ps::n1}; ? {isprime n2}{ps::n2} }
$0
[212ms]
# perm () a b ~ ArrayCmp Sort Split a Sort Split b
[638us]
# n~#ps;?+ n {i~_;p1~ps'i; ?+ (n-i){p2~ps'(i+_);? {p3~2*p2-p1;p3<10000 & perm p1 p2 & (p3<-ps) & perm p1 p3}{]p1,p2,p3}}}
1487 4817 8147
2969 6299 9629
[49.861s]
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // Problem 50 - Consecutive prime sum
# //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# // setup
# isprime () n ~ #Factors n=1
[4ms]
# // we know that there are at least 21 terms,
# // and this is the point at which the sum of 21 consecutive primes is definitely > one million
# n~5046
[4ms]
# l~Int (1.2*n/Ln n);c~2;ps~[[l]];ps'1~2;ps'2~3;n2~0
[5ms]
# // calculate primes
# ?+ {n2<n}{n1~6*_-1;n2~n1+2;? {isprime n1}{c++;ps'c~n1};? {isprime n2}{c++;ps'c~n2}}
$0
[102ms]
# ps ~ ps ## !NaN ps
[4ms]
# m~#ps
[4ms]
# n~1000000
[4ms]
# // precalculate cumulative sums of primes
# sums~[[m+1]];sums'1~0;?+ m {sums'(_+1)~sums'_+ps'_}
[36ms]
# add () start end ~ _sums'end - _sums'start
[3ms]
# // and search for longest
# max~0;?+ (m-1) {st~_; ?+ (m-st) {l~_+1;? {l>max}{end~_+st;s~add st end;? {s>n}{><}; ? {isprime s & l>max}{max~l;]st,end,l,s}}}}
1 2 2 2
1 3 3 5
1 5 5 17
1 7 7 41
1 13 13 197
1 15 15 281
1 61 61 7699
1 65 65 8893
1 97 97 22039
1 101 101 24133
1 103 103 25237
1 109 109 28697
1 115 115 32353
1 123 123 37561
1 125 125 38921
1 131 131 43201
1 133 133 44683
1 147 147 55837
1 153 153 61027
1 159 159 66463
1 163 163 70241
1 179 179 86453
1 193 193 102001
1 199 199 109147
1 205 205 116533
1 207 207 119069
1 209 209 121631
1 215 215 129419
1 217 217 132059
1 297 297 263171
1 309 309 287137
1 327 327 325019
1 329 329 329401
1 331 331 333821
1 333 333 338279
1 335 335 342761
1 343 343 360979
1 351 351 379667
1 357 357 393961
1 359 359 398771
1 427 427 581921
1 447 447 642869
1 459 459 681257
1 461 461 687767
1 465 465 700897
1 481 481 754573
1 485 485 768373
1 489 489 782263
1 513 513 868151
1 531 531 935507
1 537 537 958577
3 540 538 970219
3 542 540 978037
4 547 544 997651
[10.034s]
#