Project Euler - Solutions

Go to problem:

Problem 1 — Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Solving this requires a simple while loop containing a conditional to check divisibility, summing if appropriate. Note the use of _ for the current loop index (starting from 1), and, unlike C for example, the logical or operator is a single bar.

Problem 2 — Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Here we have another conditional sum, though this time calculating Fibonacci numbers as we go and checking an exit condition, rather than using a fixed loop count.

Problem 3 — Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Range returns the minimum and maximum values in an array. Select the 2nd entry for the maximum.

Problem 4 — Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

First we need a function to check if a string is a palindrome. The ispalin function does this by comparing a copy of the input string (created by the unary + operator) with the reverse of the string (Rev reverses in place). Note a single = for the logical equality test.

Next use nested while loops to multiply all numbers greater than 900 and check if we have a palindrome. Given a solution is found there is no need to check smaller numbers.

Problem 5 — Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

To solve this problem we need the prime numbers less than 20, so loop to calculate them, building up the array p. Then create an equally sized array c which will store the required power for each of these primes, and initialise it with zeros. Also define an update function that will check each entry of its two input arrays, and update the second array to have the largest value at each index.

Now we can work out the required power for each prime by factorising each integer to 20, counting the frequency of each factor and passing the result and the running count in c to the update function. Finally raise our array of primes to the powers in c and multiply to get the answer. Check by calculating the remainder when dividing by each of the integers from 1 to 20.

Problem 6 — Sum square difference

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

This problem is trivially solved by looping, directly calculating the two sums and taking the difference.

Problem 7 — 10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Another straightforward problem. We simply loop checking each odd number for primality and stopping when we have found the 10 001st prime.

Problem 8 — Largest product in a series

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

To solve this problem we define the mul5 function to multiply the digits of a number of five or more digits. This function uses integer division operator /% to drop the least significant digit each iteration of the loop, and finishes with a lone p as return value. Given this function, we can then work through the 1000-digit number provided 5 digits at a time, saving the maximum product found.

Problem 9 — Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a b c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

To solve this problem we use nested loops to construct all sets of three integers a<b<c such that a+b+c=1000, and print any that form a Pythagorean triad, along with their product.

Problem 10 — Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

The solution to this problem is just a straightforward loop, prime check and sum.

Problem 11 — Largest product in a grid

In the 2020 grid below, four numbers along a diagonal line have been marked in red.

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

The product of these numbers is 26 63 78 14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?

First we need to enter the values for the grid and partition into a 20x20 matrix. Then define functions that given a starting position will calculate the across, down and two diagonal products respectively. Then it is just a matter of applying these functions with all legal starting positions and determining the maximum result.

Problem 12 — Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

The number of positive divisors of an integer is the product of 1 greater than each power in its prime factorisation. Using this, we can loop and generate each triangular number, calculate the number of factors, and finish when there are more than 500.

Problem 13 — Large sum

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690

Just add the numbers directly then do an integer division.

...

Problem 14 — Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

n n/2 (n is even)
n 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 40 20 10 5 16 8 4 2 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

For a first attempt, we define functions for evaluating the Collatz sequence, and then check all starting values up to 1 million. Evaluating the nested loops is quite slow in the interpreter and this takes several minutes to complete.

Avoiding functions entirely improves the speed by about one third, but this remains unacceptably slow.

Maintaining a history of chain lengths improves the performance considerably.

...

Problem 15 — Lattice paths

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

This problem reduces to simply counting the number of ways to choose 20 right turns from 40 possibilities

Problem 16 — Power digit sum

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2¹⁰⁰⁰?

Simply calculate the power and sum the digits.

Problem 17 — Number letter counts

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

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. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

A nice start to solving this problem is to do the conversion to word form.

First define the words in a couple of arrays, select them appropriately and join using the :: operator. Note the copy operation (unary +) because join works in place.

Now try some test values.

To calculate the solution to the problem we use a similar technique, but instead of working with the actual words, we work with their lengths. Since spaces are not to be counted we cannot simply use the previous functions and count lengths of the resulting expressions.

Problem 18 — Maximum path sum I

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

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

We will represent the triangle as an array of arrays of increasing size.

Consider the second last row of the triangle. In order to maximise the total, we must always choose a path that takes us to the larger of the two possible values in the last row. So we can delete the last row, and replace each element in the second last row with the sum of its value plus the larger of the two below. This process is carried out by the function squish.

Having done so, we have a new last row and can repeat until the triangle has been reduced to a single value.

Problem 19 — Counting Sundays

You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.

Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.

A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

To solve this problem we need to know the number of days in each month for any year from 1901 to 2000. This is managed by the isleap function combined with the two arrays of month sizes (days and leapdays). We will keep the last calculated start day in the global variable dglobal. Given we are told 1 Jan 1900 was a Monday, we can calculate the first day of 1901 to be Tuesday (dglobal=2). From this point, we can use the same process to work through all the years from 1901 to 2000 month by month, and calculate how many start days are 0 (i.e. Sunday). To do this we use the sunstarts function with the start day and days array for one year passed in as arguments, and returning the number of months found to start on a Sunday. The dglobal variable is updated using the special global variable access syntax at the end of the function.

Problem 20 — Factorial digit sum

n! means n (n 1) ... 3 2 1

For example, 10! = 10 9 ... 3 2 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

Simply calculate the factorial, then sum the digits.

Problem 21 — Amicable numbers

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

The amicable function calculates k, the proper sum of the divisors of its argument, and j, the proper sum of the divisors of k. If this brings us back to the first number we have an amicable pair, so print the pair and return the value of the argument, else return 0. To solve the problem, loop and check all values to 10000.

Expand to see all amicable pairs.

Problem 22 — Names scores

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 53 = 49714.

What is the total of all the name scores in the file?

First we use some file functions to read in the names data from the csv file, and then sort the names array. The score function both calculates the sum of the letter values of the string argument s and multiplies by the position in the list p.

Problem 23 — Non-abundant sums

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

In order to test if a number us abundant we define the abund function that takes an explicitly integer argument (indicated by the % prefix). We then loop through all numbers up to our limit and build up the array b of abundant numbers. Each element of the array a holds a boolean value that indicates if we have found an abundant sum for the corresponding integer. Since this can be fairly easily shown to be true for all even numbers greater than 46, we use the FnFill builtin function to set these values to true ($1). Next, from the array of abundant numbers we extract the even and odd entries into separate arrays (the set of even numbers is much larger). If an odd integer is the sum of two abundant numbers, one must be even and one odd, so using a nested loop we check all possibilities and update the array a for the sums found. Since we have already excluded all the even integers greater than 46, we only need to check sums of the smaller even abundant numbers (the smallest odd abundant number is 945, so we do not need to check the sum of any two odd abundant numbers). Having completed these calculations it only remains to sum all integers for which a is zero.

Problem 24 — Lexicographic permutations

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

One way to solve this problem is to calculate the number of permutations of a set of digits one smaller than the number of digits available, and see how many full cycles are completed before passing a given number. For example, given the 10 digits 0 to 9 and the number one million, the fact that 2 * Fact 9 < 1000000 but 3 * Fact 9 > 1000000 means the initial digit will be a 2. Next, since 100000 - 2 * Fact 9 = 274240 we calculate that 6 * Fact 8 < 274240 but 7 * Fact 8 > 274240, so the next digit is the 6th in the set, i.e. 7 (since the 2 is used already). This calculation is handled by the function f. To determine the final result we iterate, removing the digit found from a and adding it to r each step.

Slower, but much more direct, is to use the builtin function NextPerm.

Problem 25 — 1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n1 + F_n2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

Taking the log to base 10 is an easy way to determine number of digits, so we just need to calculate the Fibonacci numbers until we find one with log 1000 or greater.

Problem 26 — Reciprocal cycles

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

¹/₂ = 0.5

¹/₃ = 0.(3)

¹/₄ = 0.25

¹/₅ = 0.2

¹/₆ = 0.1(6)

¹/₇ = 0.(142857)

¹/₈ = 0.125

¹/₉ = 0.(1)

¹/₁₀ = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ¹/₇ has a 6-digit recurring cycle.

Find the value of d 1000 for which ¹/_d contains the longest recurring cycle in its decimal fraction part.

The reduce function removes all factors of 2 and 5 from its argument, since in base 10 these will not contribute to the cycle length. The cycle length is then given by l where (10ⁿ−1) mod l = 0. This is found using the len function. With these two functions in hand, it is just a matter of checking values and finding the maximum.

Problem 27 — Quadratic primes

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula n² 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, 79 and 1601, is 126479.

Considering quadratics of the form:

n² + an + b, where |a| 1000 and |b| 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

The case n = 0 implies b must be prime, and the case n = 1 implies a must be odd. So loop within these constraints, and save the coefficients which give the maximum length.

Problem 28 — Number spiral diagonals

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

Ignoring the the central 1, each corner of the ith internal square increases by 2 * i. The 5 by 5 sample shown contains 2 such squares, and a 1001 by 1001 spiral will contain 500 such squares. To calculate the required sum, the outer loop in the soution iterates over each square, updating the difference d, and the inner loop sums the four corners.

Problem 29 — Distinct powers

Consider all integer combinations of a^b for 2 a 5 and 2 b 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 a 100 and 2 b 100?

This is another problem that requires nested loops to solve. The expression below will loop over all a and b and build up an array with the values a^b. Once the array is complete, all that is necessary is to remove duplicates with the Unique builtin function and then calculate the size.

Problem 30 — Digit fifth powers

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

The maximum possible value can be determined by finding the point at which the sum of the fifth powers of n digits, each 9, is always less than 10ⁿ. Given this maximum, it is simply a matter of evaluating the digit fifth powers for all numbers less than the limit and summing those were the equality holds.

Problem 31 — Coin sums

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1£1 + 150p + 220p + 15p + 12p + 31p

How many different ways can £2 be made using any number of coins?

First create an array to hold the number of ways to use the given coins to some to each value up to 200p. (Note that index i represents the value i-1). Initialise it to zero everywhere except the first entry which needs to be 1 (since there is 1 way to add to 0). Using this array allows us to avoid unnecessary recalculation. The nested while loops mean a little care must be taken when using the underscore — hence the use of the variable c. The solution is fast and easily adapted to other totals and sets of coins.

Problem 32 — Pandigital products

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

The most interesting aspect of this solution is the function accept that splits each of m, n and m*n into their component digits, concatenates these digits into a single array, removes duplicates, and checks that 9 unique values remain and that 0 is not one of them. A little bit of analysis reveas that the only possibilities are a 1 digit number times a 4 digit number producing a 4 digit result, or a 2 digit number times a 3 digit number producing a 4 digit result. Checking all such candidates, the products are saved in the array ns. The answer is obtained from this array by summing its unique entries.

Problem 33 — Digit canceling fractions

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Considering a numerator comprised of non-zero digits n₁ and n₂, and denominator with non-zero digits d₁ and d₂, the only non-trivial candidates are when n₂=d₁ or n₁=d₂. Since the fraction must be less than 1, just need to loop over numerators from 1 to 100 and, for each numerator n, denominators from 1 to 100-n.

Problem 34 — Digit factorials

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

Similarly to problem 30, we solve to find the maximum possible value by finding the point at which the sum of the factorial sum of n digits, each 9, is always less than 10ⁿ. Given this maximum, it is simply a matter of evaluating the factorial sum for all numbers less than the limit and summing those were the equality holds.

Problem 35 — Circular primes

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

To solve this problem, we need the function rotate to rotate the digits of an arbitrary integer argument by shifting the last digit to the first position. Looping through all odd numbers and finding the primes (quickly discarding multiples of 5) we count how many rotations retain primality. We have a circular prime if all rotations are prime.

Problem 36 — Double-base palindromes

The decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

Here we once again need our ispalin function. The condition in the loop converts the current loop index to a string and a string in base 2, and returns true if both are palindromes.

Problem 37 — Truncatable primes

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Truncating from the right is simply integer division, and the function truncFromR carries this out while testing primality. Truncating from the left is implemented by splitting out the digits, and recombining from the tail of the digit array. The function truncFromL implements this logic. Each of these functions returns 0 if all truncations were prime, so the combined function trunc performs the necessary check to solve this problem. Thereafter it is simply a matter of looping and summing.

Problem 38 — Pandigital mutiples

Take the number 192 and multiply it by each of 1, 2, and 3:

192 1 = 192
192 2 = 384
192 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n 1?

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}}} check 9 6 5 check 329 123 3 check 9876 1234 2

The only possible solutions of this problem arise from multiplying a single digit number (the generating number) 5 times, ensuring the multiple of 2 is two digits long. Thus the range of generating numbers for a concatenated product of (1,2,3,4,5) is from 6 to 9.

Similarly we need to consider 3 multiples of a 3 digit number - each 3 digits in length. Thus the range of generating numbers for a concatenated product of (1,2,3) is from 123 to 329 (since all digits must be distinct and the multiple of 3 must remain 3 digits in length).

Finally, we need to consider 2 multiples of a 4 digit number - with the second multiple being 5 digits in length. In this case the range of generating numbers for a concatenated product of (1,2) is from 5123 to 9876 (since all digits must be distinct and the multiple of 3 must remain 3 digits in length).

Using an array and string combine to generate the concatenated products, we check for pandigital results as for problem 32, and sum those that are found.

Problem 39 — Integer right triangles

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p 1000, is the number of solutions maximised?

We could re-use some of the problem 9 code to solve this problem, but a more efficient solution is to use the fact that a+b+c=p and a²+b²=c² implies b=p(p/2-a)/(p-a), for b<a. To solve we simply loop over all candidate values and look for integer values of b.

Problem 40 — Champernowne's constant

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12^th digit of the fractional part is 1.

If d_n represents the n^th digit of the fractional part, find the value of the following expression.

d₁ d₁₀ d₁₀₀ d₁₀₀₀ d₁₀₀₀₀ d₁₀₀₀₀₀ d_1000000

The most direct way to solve this problem is to simply generate a string of consecutive numbers that has the required 1 million digits. (From 1 to 200000 is sufficient.) Then we can read the required digits directly and multiply.

A more elegant solution is to calculate explicitly the digit positions where the values building up the decimal expansion increase in digit length. The functions sum9 and range perform this calculation. The following code finds the correct range of values for each digit position of interest, determines what value encompasses the specific position and how far we need to go into it. The digits are multiplies as we find them.

Problem 41 — Pandigital prime

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

Only 1:4 and 1:7 pandigitals are possible, since pandigitals of other sizes are always multiples of 3. Using the NextPerm standard library function we can examine all possible values, test their primality and save the maximum.

Problem 42 — Coded triangle numbers

The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

The solution to this problem is very straightforward, similar to problem 22.

Problem 43 — Sub-string divisibility

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

d₂d₃d₄=406 is divisible by 2

d₃d₄d₅=063 is divisible by 3

d₄d₅d₆=635 is divisible by 5

d₅d₆d₇=357 is divisible by 7

d₆d₇d₈=572 is divisible by 11

d₇d₈d₉=728 is divisible by 13

d₈d₉d₁₀=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

The array ps holds the prime divisors, and the function get3 returns the 3 digit number corresponding to the substring at index i. The function checkdiv takes an array of digits as argument, builds up the substrings and tests divisibility against each divisor. If all 7 substrings of a number are divisible by the corresponding prime divisor, add the number to the sum.

Problem 44 — Pentagon numbers

Pentagonal numbers are generated by the formula, P_n=n(3n1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P₄ + P₇ = 22 + 70 = 92 = P₈. However, their difference, 70 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_j and P_k, for which their sum and difference is pentagonal and D = |P_k P_j| is minimised; what is the value of D?

With a function to generate pentagonal numbers and another to check whether a given number is pentagonal, we just need to loop over pentagonal numbers, checking their sum and difference as we go.

Problem 45 — Triangular, pentagonal, and hexagonal

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle T_n=n(n+1)/2 1, 3, 6, 10, 15, ...

Pentagonal P_n=n(3n1)/2 1, 5, 12, 22, 35, ...

Hexagonal H_n=n(2n1) 1, 6, 15, 28, 45, ...

It can be verified that T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Every hexagonal number is a triangular number, so only need to check hexagonal and pentagonal. The function hex generates the nth hexagonal number, and the function ispent checks if its argument is pentagonal. After finding the trivial solution H₁, we step forward and find the example solution H₁₄₃. The next solution is the required one: H₂₇₆₉₃.

Problem 46 — Goldbach's other conjecture

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 21²
15 = 7 + 22²
21 = 3 + 23²
25 = 7 + 23²
27 = 19 + 22²
33 = 31 + 21²

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

For each odd composite number, loop over all candidate 2n² values, subtracting and checking the remainder for primality. Stop once a number has been found that does not have a prime difference for any 2n².

Problem 47 — Distinct primes factors

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 7
15 = 3 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² 7 23
645 = 3 5 43
646 = 2 17 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

Count unique prime factors with the function nfact, and check adjacent numbers. Thd first approach does so directly, the second is more extensible — using the array a to hold the number of distinct prime factors, and the standard function ArrayCmp to check if each value is greater than 3.

Problem 48 — Self powers

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

Support for arbitrary precision integer arithmetic makes this trivial to solve. A slightly different approach would be to take the modulus each step rather than just at the finish to reduce memory usage at the slight expense of speed.

Problem 49 — Prime permutations

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

Start by calculating and storing all primes below 10000 into the array ps (checking 6n±1 and excluding 2 and 3 since they will not affect the answer). Using the function perm that returns true if the digits of its two arguments are permutations of each other, we can solve by building up candidate three value arithmetic series, and checking both permutation and primality.

Problem 50 — Consecutive prime sum

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

To solve this it is convenient to precalculate the primes to 1 million, and then calculate and save the cumulative sums. Using Gauss's simple prime counting function π(n)≈n / ln n and deliberately overestimating, we can allocate the prime number array in one step. Then we fill the prime array (checking 6n±1 as for other solutions), trim to the found size by excluding all uninitialised values (NaN), allocate and fill the sums array with the cumulative prime sums, and define the function add that returns the sum of primes in a given range. Then loop and search, checking for the longest sum.