Euler 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?

analyse:
start with next odd number 1489 and increment by two.

Problem49 =296962999629 elapsed time:    2 ms. Test Passed.

Euler problem 48

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

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

analyse:
Because only the last ten digits are needed in the answer we can avoid big integers by 
truncating each calculation to ten digits.

Problem48 =  9110846700 elapsed time:   18 ms. Test Passed.

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

Performance improvements:
Suppose we have to check number 80 for prime divisibility. The first prime can only be 2 because the next prime 3 will yield to a greater number (3 * 3 * 3 * 3 > 80). 
Stop prime division when maximum prime number is reached yield to 20 x faster code execution. The maximum prime depends on primes already found.


number  = x * x * x * x  ( x = maximum prime number )
number  = 2 * x * x * x  
number  = 2 * 3 * x * x  
number  = 2 * 3 * 5 * x  

Problem47 =      134043 elapsed time:  117 ms. Test Passed.

Euler 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 + 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?

Performance improvement:

Add .Tolist() extension result in 2 times faster execution.

List<int> primes = new PrimeNumberSieve().ToList(); // 15 ms -> 8 ms.

Problem46 =        5777 elapsed time:   8 ms. Test Passed.

Euler problem 45

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

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

analyse:
1) Every Hexagonal is also a Triangle.
performance improvements: 
2) Start looping with Hexagonal numbers because they increase faster than other two number types.
3) H143 gives 40755 so start with n = 144.
4) use difference: H(n) - H(n-1) = n(2n-1) - ((n-1)(2(n-1)-1)) = 4 * n - 3

An alternate solution is to make use of the square root formula. x = (-b+- sqrt(b2-4ac))/2a

When we rewrite the pentagon formule P(n) = n(3n-1)/2 

we get 1.5n*n - 0.5n - P(n) = 0 where P(n) = H(n)

Problem45 =  1533776805 elapsed time:    1 ms. Test Passed.

Euler problem 44

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?


Not so proud on this one. Anybody a suggestion?

Problem44 =     5482660 elapsed time:    2 ms. Test Passed.

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

analyse:


We can create a list with all 0-9 pan-digitals, see problem 41, then extract the 3 digit 
subgroups and check for divisibility by apropiate prime. However this will yield to a hell 
of a lot loops (about 10! fac). So we have to think of something smarter.
more analyse lead to the following axioma's:


axioma 1: a 10 digit pandigital can't start with a zero. d1 <> 0.
axioma 2: d4 must be even. d4 = {0,2,4,6,8}
axioma 3: d456 must be div by 5. d6 = {0,5}
axioma 4: d678 must be div by 11. With d6=0 we get 011,022,033. This is div by 11 but contains dual digits.
So d6 must be a 5. 


Solution:


Create a array with digit d1 to d10.
Increment each digit starting with digit one.
Check for unique digit and apply dividible rules recursive.

Problem43 = 16695334890 elapsed time:    8 ms. Test Passed.

Euler 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?

Problem42 =         162 elapsed time:   12 ms. Test Passed.

Euler problem 41

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?

analyse:


The 8 and 9 digit pandigital 987654321 are divideble by 3 (Sum digits divide evenly by 3).
and thus are composit numbers and no primes.
So we start with a 7 digit padigital number 7654321.


Performance improvements:


1) Use permutation to generate pandigitals. This reduces loop from 6419754 to 5040. 
2) Use the fast Miller-Rabin test to check if a big number is a prime.

Problem41 =     7652413 elapsed time:    2 ms. Test Passed.

Euler problem 40

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

analyse:

A picture tells more than a thousand words.

int b =       1          2              3                4

int c =   <-9x1=9-><--90x2=180--><--900x3=2700--><--9000x4=36000--><--enz-->

        0.12345678910......97..99100..........9991000..........999910000....

int o =   1        10      ^^    190             2890          ^^^^38890

int f = (x / b + p) = ---> 97

int e = (x % b) = -------------------------------------------> 0123

int p =   1        10            100             1000              10000

Problem40 =         210 elapsed time:    0 ms. Test Passed.

Euler problem 39

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 maximized?

analyse:

 1) a² + b² = c²
 2) a + b + c = p
 1+2) yield  
 3) b = (p²-2pa)/2(p-a)
 4) c = p - a - b

b is only integral when (p²-2pa) is evenly divisible by 2(p-a)

Performance improvements: 6 ms -> 0.2 ms

1) Don't count doubles {3,4,5} and {4,3,5}. alpha 0 - 45 deg. Maximum a = p/(2+√2)
 12 is the smallest perimeter which yield to an integral a, b & c {3,4,5}.
So answer must be a multiple of 12.



Problem39 =         840 elapsed time:    0 ms. Test Passed.

Euler problem 38

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?

Analyse:
     
Because the Euler website returns 918273645 as an incorrect answer we must find a greater pandigital number. 
Axioma 1: The pandigital must start with digit 9!
     
Search for values of n and M which yield to a 9 digit pandigital.
     
        M       Pandigital      Result (S = to short, L = to long)
        ======= =============== ======
n=2     9       918             S
        9x      9x1xx           S
        9xx     9xx1xxx         S
        9xxx    9xxx1xxxx       Okee (9 digits)
n=3     9       91827           S
        9x      9x1xx2xx        S
        9xx     9xx1xxx2xxx3xxx L
n=4     9       9182736         S
        9x      9x1xx2xx3xx4xx  L
n=5     9       918273645       Okee (website says incorrect )
        9x      9x1xx2xx3xx4xx  L
n=6     9       91827364554     L
     
So the only possibility is n = 2 and M is 9xxx.
The definition of a pandigital says that all digits must be different so start with M = 9876 and count down to 9123.
The resulting number is M plus N = M plus 2M = M*100000 + 2*M = M * 100002 

Problem38 =   932718654 elapsed time:    0 ms. Test Passed.

Euler problem 37

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.

Performance improvements:

1) Primes starting with 8 or 9 will not yield to a prime after stipping R to L.
2) Don't count primes 2,3,5,7  sum-17 is faster than primes.Skip(4) 

Problem37 =      748317 elapsed time:   12 ms. Test Passed.

Euler problem 36

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

performance improvements:

1) Generate Palindromes to reduce loop from 1000000 to 1110 times.

Problem36 =      872187 elapsed time:    3 ms. Test Passed.

Euler problem 35

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?

Performance improvements:

1) Remove all primes with digit 0,2,4,5,6,8 because they will not lead to a prime during permutation. //42243 -> 11 ms.

2) Don't use ToString() to rotate digits. Use n%10 instead.

Problem35 =          55 elapsed time:   11 ms. Test Passed.

Euler problem 34

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.

solution:

Wikipedia,

A factorion is a natural number that equals the sum of the factorials of its decimal digits. For example, 145 is a factorion because 1! + 4! + 5! = 1 + 24 + 120 = 145.

There are just four factorions and they are 1, 2, 145 and 40585 (sequence A014080 in OEIS).

analyse:

If n is a natural number of d digits that is a factorion, then 10d − 1 ≤ n ≤ 9!d. This fails for d ≥ 8 so n has at most 7 digits and the first upper bound is 9,999,999. The maximum sum of factorials of digits for a 7 digit number is 9!7 = 2,540,160 establishing the second upper bound.

performance improvements:

1) According wiki the greatest factorion is 40585         // 1034 -> 15 ms.

2) Add Cache for Fac 0 to 9                                      //     15 ->  3 ms.

Problem34 =       40730 elapsed time:    3 ms. Test Passed.