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