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;

  if (sum < 1000000)
    if(isPrime(sum) && (maxCount < count))
      maxCount = count;
      maxStart = start;
    i = nextPrimeAbove(i);
    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))
    if (findAnswer())

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, 11 + 22 + 33 + … + 1010 = 10405071317.

Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.

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.

a_1 \equiv b_1 (mod~n)
a_2 \equiv b_2 (mod~n)
a_1 + a_2 \equiv b_1 + b_2 (mod~n)

(a~mod~n)(b~mod~n) \equiv ab~(mod~n)

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

a^{p+1} = a^p \cdot a
a^{pq} = a^p \cdot a^q

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

If p is odd, then result = a \cdot a^{p-1}
If p is even, then let result = a^{\frac{p}{2}} 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×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

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:

n = p + 2 a^2 
3 \leq p < n
1 \leq a^2 \leq \frac{n-3}{2}

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 Tn=n(n+1)/2 1, 3, 6, 10, 15, …
Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, …
Hexagonal Hn=n(2n−1) 1, 6, 15, 28, 45, …

It can be verified that T285 = P165 = H143 = 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:

P(s, n) = \frac{n^2(s-2) - n(s-4)}{2}
n = \frac{\sqrt{8 (s-2)x + (s-4)^2} + (s-4)}{2(s-2)}

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).

P(6, n) = P(3, 2n-1)

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.