Problem 43 Project Euler Solution with python

Sub-string divisibility

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.

One might write a simple solution using direct if else statements for this problem. Using if else statements, the execution time may be a few seconds. But this is not a very good approach. I too had written a program with if else statement which will take each and every permutation of the 0-9 Pandigital and check for the conditions given in the question. The program is as follows:

# http://radiusofcircle.blogspot.com

# time module for calculating execution time
import time

# permutations method
from itertools import permutations

# time at the start of program execution
start = time.time()

# permutations of 0-9 pandigital
p = permutations('0123456789')

# variable to store the value of sum
solution = 0

# for loop to loop through permutations
for i in p:
    if (int(''.join(i[7:10])) % 17 == 0 and
        int(''.join(i[6:9])) % 13 == 0 and
        int(''.join(i[5:8])) % 11 == 0 and
        int(''.join(i[4:7])) % 7 == 0 and
        int(''.join(i[3:6])) % 5 == 0 and
        int(''.join(i[2:5])) % 3 == 0 and
        int(''.join(i[1:4])) % 2 == 0):
        solution += int(''.join(i))

# printing the solution
print solution

# time at the end of program execution
end = time.time()

# total time taken
print end - start

All the code is simple but the order in which I have written the conditions is a bit complicated(May be☺️). If you reverse the order then the execution time is increased. I haven't tried for any other combinations but, this program has a very good execution time(around 3 seconds).

The reason why using 17 at the start of the if else statement will reduce the time of execution is because, when an if statement with multiple Boolean conditions joined with and is encountered, and if the first Boolean is False, then all the other conditions are not checked, just the if statement is terminatated.

This was a good code but I was not satisfied and wanted a better performing code. So I looked back at the question and found a logic. My logic was, instead starting from the permuted combinations, why not check for the combinations of different multiples of 17, 13, 11, 7, 5, 3 ? Read on to understand more.

We know that the multiples of 17 under 1000 are: 017 034 051 068 085 102 119 136 153 170 187 204 221 238 255 272 289 306 323 340 357 374 391 408 425 442 459 476 493 510 527 544 561 578 595 612 629 646 663 680 697 714 731 748 765 782 799 816 833 850 867 884 901 918 935 952 969 986.

Multiplies of 13 below 1000 are: 013 026 039 052 065 078 091 104 117 130 143 156 169 182 195 208 221 234 247 260 273 286 299 312 325 338 351 364 377 390 403 416 429 442 455 468 481 494 507 520 533 546 559 572 585 598 611 624 637 650 663 676 689 702 715 728 741 754 767 780 793 806 819 832 845 858 871 884 897 910 923 936 949 962 975 988.

As per the question first two digits of a multiple of 17 and last two digits of multiple of 13 should match to form the given number.

For example consider:
17 x 17 = 289 and
13 x 56 = 728

We can see that 28 in 289 is equal to 28 in 728 so there two numbers can form a pair. The combined pair will form a 4 digit number which will be 7289. Let us call these kind of numbers with name i.

Considering the multiples of 11: 011 022 033 044 055 066 077 088 099 110 121 132 143 154 165 176 187 198 209 220 231 242 253 264 275 286 297 308 319 330 341 352 363 374 385 396 407 418 429 440 451 462 473 484 495 506 517 528 539 550 561 572 583 594 605 616 627 638 649 660 671 682 693 704 715 726 737 748 759 770 781 792 803 814 825 836 847 858 869 880 891 902 913 924 935 946 957 968 979 990.

At this stage according to the question, first two digits of number i(our example 7289), should be equal to the last two digits of the multiple of 11.

In our example 72 in 7289, matches with 72 in 572(11 x 52). They both combine together to form a 5 digit number 57289.

Similarly the first two digits of the newly formed number(57289) should match with the last two digits of the multiple of 7 for them to become a couple. This will continue until you have reached a number which is 9 digits long.

As we know that the 0-9 pandigital number should have all 0,1,2,3,4,5,6,7,8,9 the number which is missing from the 9 digit number formed above, will make it a 10 digit number.

We have used a lot of python in built functions to make the program still faster. I will tag a few links for important in-built functions which I have used in the program and will also explain the part which I feel might be hard for beginners to understand.

Program

File: pep43.py ------------------------- # http://radiusofcircle.blogspot.com # time module for calculating execution time import time # time at the start of program execution start = time.time() def converter(z): """function to make a given number to a three digit number by adding zeros at front""" if len(z) == 2: return '0'+z elif len(z) == 1: return '00'+z return z def m(n): """function to generate multiples of given number under 1000""" mn = [] mul = 1 i = 1 while mul < 1000: mul = i*n i += 1 mn.append(mul) mn.pop() mn = map(str, mn) mn = map(converter, mn) return mn def concat(a, b): """function to form the solution""" c = [] for i in a: for j in b: if i[:2] == j[1:] and len(set(j[0] + i)) == len(j[0] + i): c.append(j[0] + i) return c def missing(g): """function to add the missing number from 0-9 to complete the pandigital number""" for i in '0123456789': if i not in g: return i + g # forming the multiples of 2,3,5,7,11,13 m17, m13, m11, m7, m5, m3, m2 = (m(17), m(13), m(11), m(7), m(5), m(3), m(2)) # getting the required solution d = reduce(concat, [m17, m13, m11, m7, m5, m3, m2]) # adding the missing number d = map(missing, d) # converting the numbers to int d = map(int, d) # printing the sum of numbers print sum(d) # time at the end of execution end = time.time() # printing the total time for execution print end - start

Python functions - Map, filter and reduce
Map python function
Reduce python function

converter function
This function will take a number and check if the number has less than 3 digits and adds 0's in front of the number to make it a 3 digit number. Remember that the input should be a string.
Example: '5' --> '005', '17' --> '017'

m function
This function will generate the multiples of numbers less than 1000 in string format and will also add leading zeros using converter function.
Example: '005','010','015'.........

concat function
This function will take the first two digits of the multiple and last two digit of the multiple and form a new number. Same as we have discussed above.

missing function
This function will add the 10th digit after the process of forming the number is completed.

Rest of the code is left for you to understand. You should read map and filter. They are very useful.

You can download the above source code from Gist Github pep43.py

Code is written according to PEP8 standard.

Output

Summary

A very nice problem. One might get motivated to solve the problem using a very simple algorithm, but bottom up approach(I'm not sure whether I can call this bottom up approach) had a very good execution time. I am really very happy and satisfied to write the solution for this program. You can still improve the program if you want to.

As always you can comment in the comment box below if you have any doubt or didn't understand anything, not only related to this post but anything else out of the box. I will be glad to help you.

Please do comment in the comment box below, if you have found any typo, or have a different program or better program, not only in python but in any other programming languages like, C, C++, Matlab, Java, Perl, Ruby, etc. Please comment if you have any suggestion. I will be very happy to view each of them.

You can also contact me.

Thank you. Have a nice day😃!

Problem 60 Project Euler Solution with python

Prime pair sets 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. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He...

RADIUS OF CIRCLE

Search This Blog