Euler problem 60

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Problem 60 =       26033 elapsed time:  236 ms. Test Passed.

Euler problem 58

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13  62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Problem 58 =       26241 elapsed time:  122 ms. Test Passed.

Euler problem 51

By replacing the 1^st digit of *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3^rd and 4^th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

analyse:
1) If we replace the last digit with 0-9 we get: xxxx0, xxxx1, xxxx2, ..., xxxx9. 
    This yield at least to four even numbers, xxxx2,xxxx4,xxxx6,xxxx8, which of cause aren't prime. 
   So the last digit can't be replaced.
2) Digit must be less or equal than 2 to generate a family of eight.  0-7, 1-8, 2-9.


performance improvements: 30 ms -> 17 ms.
add 1) Don't check last digit for equalness.
add 2) Only check digits less or equal 2.

Problem51 =      121313 elapsed time:   17 ms. Test Passed.

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

analyse:


1) Sum all primes below one million.
2) Substract primes from sum until a new prime is found.

Problem 50 =      997651 elapsed time:    0.007 ms. Test Passed.

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 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 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 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 28

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?

Solution 1: Using Linq

s = spiral number                     : 1  2  3  4  5 ... 501

r = ribbe length   (2*s-1)           : 1  3  5  7  9

d = numbers/spiral 4*(r-1)         : 0  8 16 24 32

e = numbers cummulative(e+=d) : 1  9 25 49 81 <= diag North-East

f = diag South-East (e-d+r-1)     : 1  3 13 31 57 <= e-6s+6

Sum = 2 * ( NE + SE) - 3

Solution 2:

Numbers on diagonal NE: n²      ( n is size of spiral 3, 5, 7, ... 1001 )
Numbers on diagonal SE: n² -3n + 3
Sum = 2 * (NE + SE) + 1

Problem28 =   669171001 elapsed time:    0 ms. Test Passed.

Euler problem 27

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.

Problem27 =      -59231 elapsed time:    5 ms. Test Passed.

Euler problem 26

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

1/2	=	0.5
1/3	=	0.(3)
1/4	=	0.25
1/5	=	0.2
1/6	=	0.1(6)
1/7	=	0.(142857)
1/8	=	0.125
1/9	=	0.(1)
1/10	=	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.

Problem26 =         983 elapsed time:   1 ms. Test Passed.

Euler problem 12

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?

Below we see a brute force methode to solve this problem.

Performance improvement:

On http://en.wikipedia.org/wiki/Divisor_function an algorithm is described to
determine the divisors of a number by making use of prime numbers. This algorithm dramatical improves performance from 2434335 ms to 57 ms.

Problem12 =    76576500 elapsed time:   57 ms. Test Passed.