Project Euler
Project Euler was started by Colin Hughes in October 2001 as a sub-section on mathschallenge.net. The popularity of Project Euler has increased tremendously over the years since its inception through the concerted effort of numerous people. Users could start wherever the problems fit their background. The first one-hundred or so problems are generally considered to be easier than the problems which follow. All the functions are annotated by numpy-style docstring.
In this blog, I will show my solutions and my code to 3 problems from the Project Euler.
Problem 43: Sub-string divisibility
Problem description: 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 d1 be the first digit, d2 be the second digit, and so on. In this way, we note the following:
* d2d3d4=406 is divisible by 2
* d3d4d5=063 is divisible by 3
* d4d5d6=635 is divisible by 5
* d5d6d7=357 is divisible by 7
* d6d7d8=572 is divisible by 11
* d7d8d9=728 is divisible by 13
* d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital number with this property.
Check whether a number has sub-string divisibility property
First, let's divide this problem into smaller pieces. We can use a function to check whether a number has sub-string divisibility property. If this number satisfies this property, it could be added to the summation.
def sub_div_check(nums):
"""
Check whether a number has sub-string divisibility property.
Parameters
-----------
nums: integer
The number is ready to test the sub-string divisibility property.
Returns
-----------
flag: boolean value
Return True if nums has sub-string divisibility property.
Return False if nums doesn't have sub-string divisibility property.
Raises
-----------
ValueError
If nums is less than zero, if nums is not an integer
Examples
-----------
Check whether 1406357289 has sub-string divisibility property:
>>> sub_div_check(1406357289)
True
"""
if isinstance(nums, int) and nums>0:
nums = str(nums)
if int(nums[1:4]) % 2 == 0 and \
int(nums[2:5]) % 3 == 0 and \
int(nums[3:6]) % 5 == 0 and \
int(nums[4:7]) % 7 == 0 and \
int(nums[5:8]) % 11 == 0 and \
int(nums[6:9]) % 13 == 0 and \
int(nums[7:10]) % 17 == 0:
flag = True
else:
flag = False
return flag
else:
raise ValueError("Only positive integer types is allowed.")
List all the pandigital numbers
We can iterate through all the pandigital numbers and use the sub_div_check function to check whether this number has the sub-string divisibility. This function doesn't need any input variables.
def sub_div():
"""
The sum of all 0 to 9 pandigital numbers with the sub-string divisibility property.
The sub-string divisibility property:
Let d1 be the first digit, d2 be the second digit, and so on.
d2d3d4 is divisible by 2
d3d4d5 is divisible by 3
d4d5d6 is divisible by 5
d5d6d7 is divisible by 7
d6d7d8 is divisible by 11
d7d8d9 is divisible by 13
d8d9d10 is divisible by 17
Returns
-------
ans: integer
the sum of all 0 to 9 pandigital numbers with the sub-string divisibility property
"""
from itertools import permutations
import string
num = list(string.digits)
lst = [''.join(x) for x in list(permutations(num))]
ans = 0
for x in lst:
flag = sub_div_check(int(x))
if flag:
ans += int(x)
return ans
The final answer is 16695334890.
Problem 52 Permuted Multiples
Problem Description: 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.
def perm_mul(mul):
"""
The smallest integer, such that 2x, 3x, 4x, 5x ... mulx, contains the same digits.
Parameters
----------
mul : integer>=2
The maximum multiplier
Returns
-------
num: integer
The smallest integer that contains the same digits
Raise
--------
ValueError
If mul is not int or less than 2
Examples
---------
>>>perm_mul(6)
142857
"""
if isinstance(mul, int) and mul>1:
from collections import Counter
flag = 0
num = 1
while flag==0:
cnt = 1
for m in range(2,mul+1):
if (Counter(list(str(num*m)))==Counter(list(str(num)))):
cnt += 1
else:
break
if cnt == mul:
return num
else:
num += 1
else:
raise ValueError("Only integer types is allowed.")
Problem 101: Optimum polynomial
Problem description: If we are presented with the first k terms of a sequence it is impossible to say with certainty the value of the next term, as there are infinitely many polynomial functions that can model the sequence.
As an example, let us consider the sequence of cube numbers. This is defined by the generating function, un = n3: 1, 8, 27, 64, 125, 216, ...
Suppose we were only given the first two terms of this sequence. Working on the principle that "simple is best" we should assume a linear relationship and predict the next term to be 15 (common difference 7). Even if we were presented with the first three terms, by the same principle of simplicity, a quadratic relationship should be assumed.
We shall define OP(k, n) to be the nth term of the optimum polynomial generating function for the first k terms of a sequence. It should be clear that OP(k, n) will accurately generate the terms of the sequence for n ≤ k, and potentially the first incorrect term (FIT) will be OP(k, k+1); in which case we shall call it a bad OP (BOP).
Find the sum of FITs for the BOPs.
Solutions:
1. List the first k term of the polynomial generating function where k = degree of generating function.
2. Fit a new polynomial function by the first i term where i = 1,2,...,k
3. Calculate the first incorrect term
4. Sum all the FIT and return it as output.
def opt_poly(z):
"""
The sum pf FITs generated by the BOPs.
Define OP(k,n) to be the nth term of the optimum polynomial generating function for
the first k terms of a sequence. The first incorrect term(FIT) will be OP(k,k+1); in
which case we should call it a bad OP(BOP). Returns a number `fits` which is the sum
of all the FIT of the generating function.
Parameters
----------
z : ndarray,
Polynomial coefficients, highest power first.
Returns
-------
fits : float
Examples
----------
>>>z = np.array([1,0,0,0])
>>>opt_poly(z)
74
>>>z = np.array([1,-1,1,-1,1,-1,1,-1,1,-1,1])
>>>opt_poly(z)
37076114526
"""
import numpy as np
deg = len(z)
p = np.poly1d(z)
x = np.arange(1,deg+1)
y = np.array([p(i) for i in range(1,deg+1)])
fits = 0
for i in range(deg-1):
x_train = x[0:i+1]
y_train = y[0:i+1]
z_train = np.polyfit(x_train, y_train, i)
p_train = np.poly1d(z_train)
fits += p_train(i+2)
return (1-np.isclose(fits,int(fits)))^int(fits)