Project Euler

Problem 052

Project Euler

Permuted multiples

Problem 52

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Unbelievably, I was able to do this by hand in less than 30 minutes.

First, the number has to be at least 6 digits to be able to satisfy the criteria because each of the multiples are a permutation of the original number. Since we are looking for the smallest, I start with 6 digits and thinking that I will have to worry about 7 digits later. Turn out the answer is a 6 digits integer.

Next, the first digit must be 1 or it will become 7 digits at 5x if it is greater than 1.

 x: 1 _ _ _ _ _

Now, if we have only 6 digits, and the first digit is 1, the last digit must be 7 because 2,4,5,6,8 will give us a zero at some point for the unit digit which is impossible for a 6 digits integer to start with zero as one of the permutation, and the multiple of 3 or 9 will never produce 1 as the last digit in any of the multiples.

 x: 1 _ _ _ _ 7

In fact, since we know the last digit is 7, we also know that 1,2,4,5,7, and 8 are the digits we must work with because those are the unit digit produced by 7’s multiples. The order of those last digits from 1x to 6x are 7, 4, 1, 8, 5, and 2. We also know that the order of the first digits must be 1, 2, 4, 5, 7, 8 because the first digit must grow in sequence.

 x: 1 _ _ _ _ 7
2x: 2 _ _ _ _ 4
3x: 4 _ _ _ _ 1
4x: 5 _ _ _ _ 8
5x: 7 _ _ _ _ 5
6x: 8 _ _ _ _ 2

Now, working from 1x to 2x, we know that the 2nd digit must not carry because 1st digit must be 2 at 2x. Therefore, 2 or 4 must be the 2nd digit in the original number. We also know that 4 can not be in front of 5, 7, and 8 because 4×2+1 = 9, which is not one of the digit we are working with. In another word, 4 must be in front of 2. Therefore

 x: 1 4 2 _ _ 7
2x: 2 8 5 _ _ 4

Both combination of 5, 8 work from 1x to 2x. However, if the original 5th digit place is 8 and last digit is 7, then it will produce 3×8+2 = 6 at 3x, which is not one of the digit we are working with again. Therefore,

 x: 1 4 2 8 5 7

Continue to multiply x up to 6x will find that this number works and it is the smallest positive integer that works.

Problem 050

Project Euler

Consecutive prime sum

Problem 50

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?

Another prime problem. Since the prime numbers are consecutive, we can stop when our starting value of the chain of consecutive primes reach half a million. Here is a simple algorithm I used.

start = 2;
sum = start;
i = nextPrimeAbove(start);
count = 1;
maxStart = start
maxCount = count;

while (start < 500000) 
  sum += i;
  ++count;

  if (sum < 1000000)
    if(isPrime(sum) && (maxCount < count))
      maxCount = count;
      maxStart = start;
    i = nextPrimeAbove(i);
  else
    start = nextPrimeAbove(start);
    sum = start;
    i = nextPrimeAbove(start);
    count = 1;

nextPrimeAbove() and isPrime() are self-explanatory. There could be more optimization when sum is greater than a million, we can set start as the nextPrimeAbove(start) and calculate the sum using the maxCount since we really don’t care about any count < maxCount. We can also use more memory to pre-calculate all the cumulative prime sum from 2 to 1000000 and so sum of consecutive prime can be calculate between the differences of two cumulative prime sum. E.g. p=2, sum[2] = 2, p=3, sum[3] = 5, p=5, sum[5] = 10, and p = 7, sum[7] = 17. Consecutive prime sum from 5 to 17 is sum[17] – sum[3] = 17-5 = 12.

Problem 049

Project Euler

Prime permutations

Problem 49

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?

This problem is working with prime again and since we created a function from problem 43 to output the next permutation of a number, I thought it would be simple. However, the function I created does not account for repeating number like 1123. Since I know there is only 4 digits number involve in this problem. I created 2D array that map 0-3 into its 24 permutation and use this same array to get all 24 permutation of each number I want to test.

I want to minimize the number of value I have to test. To start of, I know I only need to test from 1001 to 9999 with increment of 2 because we need 4 digits prime number.

Since we have an array of all the prime value from our prime sieve, we can eliminate any composite value at the beginning.

Next, of the 24 permutation created from a single number, I can again test for prime, any repeated number, and any number less than 1000. For example, 1063 and its permutation 0163 are both prime but 0163 is less than 1000 so it can’t be part of the solution.

Then, I’ll sort the permutation and check for any three permutations that are equally apart. Whether I found the solution or not, I am done with all the number in the permutation list and can mark them off as if they are composite number so I don’t have to check them again. For example, once I found the solution for 1487, I can skip 4817, 8147 and any permutation of these digits later in my program.

for (i = 1001; i < 9999; i+= 2) {
  if (isValid(i))
    createPermutation(i);
    if (findAnswer())
       printAnswer();
    invalidate(i);
}

isValid() check if i is prime or i has been one of the permutation used previously. createPermutation() create a list of 24 permutation from i, remove repeat, remove invalid number, and sort the permutation in ascending order. findAnswer() check and store the 3 values that is equally apart. printAnswer() is self-explanatory and invalidate() just mark all permutation created by i as invalid so that it will never be use again to search for the solution.

Problem 048

Project Euler

Self powers

Problem 48

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

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

This problem is working with large number and using Haskell or Python is extremely easy to solve by looping through 1000 number and add up all the powers and find the last ten digits.

However, we can make some improvement of the brute force approach. The first improvement is to use modular arithmetic to ignore any digit beyond the last ten whenever we need to remember a result.

Another improvement is to implement your own integer power function that incorporate the modular arithmetic with basic property of exponent.

Therefore, let a be the base and p be the exponent,

If p is odd, then 
If p is even, then let  and find result*result as the answer.

Let n = 10000000000 and do a modular arithmetic every chance you get to keep the number from overflowing. Unfortunately, even with unsigned long long, the divide and conquer algorithm to calculate exponent still overflow. I used an iterative approach with the modular arithmetic and able to calculate the answer quite quickly.

Problem 047

Project Euler

Distinct primes factors

Problem 47

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 prime factors. What is the first of these numbers?

This problem is working with prime and prime factorization again and we should have a prime sieve working by now. The real decision was whether to remember the number of distinct prime factor for each composite number while we are creating our list of prime. Since each time we find a new prime, we visit all the number that is multiple of that prime and cross them off, we are essentially visiting the number each time we find a distinct prime for it. Therefore, we can increment a counter for each number to record this fact with any prime number have 0 count. The only problem with this approach is to set an upper limit for the number we will visit. I choose a million again and the answer is well below the limit.

Problem 046

Project Euler

Goldbach’s other conjecture

Problem 46

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 + 2×1²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

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?

Here we have another problem related to prime. Since we have done so many problems with prime number, finding the prime is not an issue at this point.

From the description, we know the following:

Notice, p can not be even or n won’t be odd.

My pseudo code algorithm is to search each odd composite number as follow starting with 9.

let n = 9
gotAnswer = false
while (!gotAnswer)
  let p = nextPrimeBelow(n)
  let found = false

  while (!found && p > 2)
    let x = (n - p) / 2
    if (isPerfectSquare(x))
      let found = true
    let p = nextPrimeBelow(p)

  if (!found)
    let answer = n
    letgotAnswer = true

  let n = nextCompositeAbove(n)

return answer

I like to return outside of a loop but you could return as soon as you found the answer. My outer while loop also only go up to one million but the answer is a lot smaller than that.

nextPrimeBelow, nextCompositeAbove and isPerfectSquare are self-explanatory. Both nextPrimeBelow and nextCompositeAbove contain another while loop that increment the search by 2 (only need odd numbers). isPerfectSquare compare the number with the square of its own rounded root.

Problem 045

Project Euler

Triangular, pentagonal, and hexagonal

Problem 45

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

Triangle	T_n=n(n+1)/2	1, 3, 6, 10, 15, …
Pentagonal	P_n=n(3n−1)/2	1, 5, 12, 22, 35, …
Hexagonal	H_n=n(2n−1)	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.

Following from last problem, we can use similar strategy to check if a number is a triangular, pentagonal, and hexagonal by verifying the following two formulas from here:

where P(s, n) = x and s is equal to the number of sides and n is the nth s-gonal number.

Another key observation from above is that every hexagonal number is also a triangular number (you can verify this using the formula above).

Therefore, we can minimize our check by finding the next hexagonal number (starting with n = 144) and verify if it is also a pentagonal number.

Problem 044

Project Euler

Pentagon numbers

Problem 44

Pentagonal numbers are generated by the formula, P_n=n(3n−1)/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 are pentagonal and D = |P_k − P_j| is minimised; what is the value of D?

This problem works with pentagonal numbers which we can solve for n using quadratic equations

Once we found the first min_D, we verify that it is the minimum by continue searching for the next D. If any D is greater than min_D, we can ignore. If any D is less than min_D, we record the new D as min_D. Once we reach a point where

We can stop because all D thereafter will be larger than min_D. The program can run really slow if we don’t exclude D that is already greater than min_D when we run the verification.

Problem 043

Project Euler

Sub-string divisibility

Problem 43

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.

This problem uses similar pandigital number from problem 32, 38 and 41. If we loop from 1023456789 to 9876543210 and check for pandigital and divisibility, this problem will run forever. Therefore, we must use only permutation of the pandigital number to get a better brute force performance. A simple lexicographic permutation algorithm can be find online.

However, more interestingly, the problem could be solve by analyzing the digits with the prime divisors. For example, if d4d5d6 must be divisible by 5, then d6 must be either 0 or 5. Furthermore, if d6 is 0, then d6d7d8 can not be divisible by 11 and be part of a pandigital number (011, 022, 033 … etc). From here, working our way from the last 4 digits (d7d8d9d10) by checking a smaller pool of possible solution based on our last two observations and the larger prime divisors. We can deduce the answer by hand.

d6 = 5;
possible solution for d6d7d8:
- {506, 517, 528, 539, 561, 572, 583, 594}
(d6d7d8 value) with possible solution for d6d7d8d9 :
- (506) no solution due to result of 5065.
- (517) no solution.
- (528) 5286.
- (539) 5390.
- (561) no solution due to result of 5611.
- (572) 5728.
- (583) 5832.
- (594) no solution due to result of 5949.
(d6d7d8d9 value) with possible solution for d6d7d8d9d10 :
- (5728) 57289.
- (5832) no solution due to result of 58323.
- (5286) 52867.
- (5390) 53901.
(d6d7d8d9d10 value) with possible solution for d5d6d7d8d9d10:
- To find d5, for 52867, find remainder r = 52 % 7 = 3. check if 103 % 7 = 0, 203 % 7 = 0, and so on until 903 % 7 = 0. (however, once you found 203 % 7 = 0, you know 903 is the other value since last 2 digit is fix. So 2 and 9 are the possible candidates for d5 but 2 is already used in 52867).
- (52867) 952867. 252867 is not a solution.
- (53901) no solution due to result of 553901.
- (57289) 357289.
(d5d6d7d8d9d10 value) with possible solution for d4d5d6d7d8d9d10:
- since d2d3d4 is divisible by 2, d4 must be an even number.
- (357289) 0357289, 4357289, 6357289
- (952867) 0952867, 4952867
(d4d5d6d7d8d9d10 value) with possible solution for d3d4d5d6d7d8d9d10:
- since d3d4d5 is divisible by 3, d3+d4+d5 must also divisible by 3.
- (0357289) 60357289. 0, 3, 9 are used.
- (0952867) 30952867. 0, 6, 9 are used.
- (4357289) no solution. 2, 5, 8 are all used.
- (4952867) no solution. 2, 5, 8 are all used.
- (6357289) 06357289. 3, 6, 9 are used.
(d3d4d5d6d7d8d9d10 value) with possible solution for d1d2d3d4d5d6d7d8d9d10:
- since d4 is already even, we are just looking for any number not used and append those permutation to the number.
- (60357289) 1460357289, 4160357289
- (30952867) 1430952867, 4130952867
- (06357289) 1406357289, 4106357289

Add them up and should get the final answer.

Problem 042

Project Euler

Coded triangle numbers

Problem 42

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?

This problem uses the same word value in problem 22. We first calculate a list of triangle number. Assume there is no word over 30 characters, the largest triangle number should not be greater than 26*30=780. From the formula, we know that

780 * 2 = 1560 = n (n+1)
$n \approx \sqrt(1560) \approx 40$

We calculate a list of triangle number up to 40. The rest is just to nest two loop, outside looping the words, inside looping through triangle numbers and count the number of triangle words.