Solving three problems from the Euler Project (with increasing difficulty)
After reading this question, I immediately thought about prime factorization and factor trees. The goal is to program a factor tree and work backwards from the prime factors to calculate the smallest number that is evenly divisible by all numbers from 1 to 20. Note that 2520 has to be divisible by the prime numbers from 1 to 10 in order to be divisible by all numbers 1 to 10 without any remainder. Knowing this, we can save time by not checking whether 2520 is divisible by every number from 1 to 10.
So to begin, we will define a function to return a list of all the prime numbers from 1 to a given number. This will help us code our factor tree.
def prime_num(n):
"""
return list of prime numbers given a number
"""
primes = []
# prime numbers have to be greater than 1
for number in range(2, n + 1):
for i in range(2, number):
if (number % i) == 0:
# number is not prime (divisible by a number other than one and itself)
# return to outer for loop and increment by one
break
else:
# number is prime so add to list
primes.append(number)
return primes
Next, the goal is to code a factor tree where the "ends" or what is returned are all the prime factors of the given number.
We will find the prime factors of this given number (n) using knowledge about whether a number is prime in range 1 to n from the above function that returns the prime numbers in range 1 to n. Recursion works well here because we want to break down n into smaller parts each time until n equals 1 and we cannot find any more prime factors.
def find_prime_factors(n):
"""
recursively find prime factors of number given prime numbers in range 1 to that number
"""
prime_numbers = prime_num(20)
if n == 1:
# base case: if n = 1, there are no more prime factors
return []
for num in prime_numbers:
# loop through each number in the list of prime numbers in range 1 to n
if n % num == 0:
# return the prime factor and use recursion to find next prime factor
return [num] + find_prime_factors(n / num)
We will write a final function that uses the two functions we have written. We know the prime numbers from 1 to a given number from the first function. We can also find the prime factors of a number from the second function.
Now, we will find the prime factors of every number 20 and below (using the second function). We will keep track of the maximum prime factors. For example, the prime factors of 2 and 3, respectively, are 2 and 3 and the prime factors of 4 are 2 and 2. So, the maximum count of the prime factor 2 is 2 and of 3 is 1 and the prime factors of the smallest number evenly divisible by 2, 3, and 4, are 2, 2, and 3 and NOT 2, 3, 2, and 2. This means the smallest number evenly divisible by 2, 3, and 4 equals (2)(2)(3) = 12.
Using this same logic, we will use the maximum prime factors of numbers 20 and below to calculate the smallest number evenly divisible by all of the numbers from 1 to 20.
We recently reviewed the collections module, so we will use that to count the maximum number of each prime factor.
from collections import Counter
def main():
"""
print smallest number evenly divisible by all numbers from 1 to 20
"""
max_primes = Counter()
for i in range(2, 21):
# creating a factor tree for each number from 2 to 20
prime_factors = Counter(find_prime_factors(i))
# keeps maximum of counts of each prime factor
max_primes = prime_factors | max_primes
smallest_num = 1
for prime, count in max_primes.items():
# based on prime factors, calculate smallest number by multiplying
smallest_num = smallest_num * (prime ** count)
print(smallest_num)
main()
The smallest positive number that is evenly divisible by all of the numbers from 1 to 20 is 232792560.
This question involves pythagorean theorem (a^2 + b^2 = c^2). The first step is to define a function that returns the number of solutions that meet the right angle triangle side length definition given a perimeter.
We know that a and b have to be at least 1 and cannot be more than half the perimeter. So, we will use a to loop through all integers from 1 to p/2.
Given these two equations:
a^2 + b^2 = c^2 (pythagorean theorem)
a + b + c = p (definition of perimeter)
We can solve for b and c.
1) a + b + c = p --> b+c = p-a
2) a^2 + b^2 = c^2 --> c-b = a^2/(p-a)
3) (c-b) + (c+b) = a^2/(p-a) + (p-a) --> c = (a^2 + (p-a)^2)/(2 *(p-a)
Then, using pythagorean theorem, b = sqrt(c^2 - a^2)
The final step is to check whether the definition of perimeter is met and make sure we have the correct value for a.
def find_side_lengths(p):
"""
return number of solutions that meet the definition of right angle triangle side lengths given a perimeter
"""
num_solutions = 0
# an integer side length of a right triangle has to be at least 1 and not more than half the perimeter
for a in range(1, p//2):
# solve pythagorean theorem for c and b
c = (a**2 + (p-a)**2) // (2 * (p-a))
b = (c**2 - a**2) ** 0.5
# if definition of perimeter is met, increment solutions by one
if a + b + c == p:
num_solutions += 1
# a and b can be switched in a solution, but we only want one solution of possible integral side lengths
return num_solutions//2
Next, we want to find the perimeter where the number of solutions, given that we know the number of solutions for a perimeter from the previous equation, is maximized for perimeters ≤ 1000. We will use a dictionary to store the perimeter and the number of solutions for that perimeter.
def maximized(perimeter):
"""
print perimeter where the number of solutions is maximized for perimeter <= 1000
"""
data = {"perimeter": 0, "solutions": 0} # store perimeter value and number of solutions
for p in range(perimeter + 1):
# if the number of solutions of the current perimeter is greater than the solutions for all perimeters smaller
# then store that perimeter and the corresponding number of solutions
solutions = find_side_lengths(p)
if solutions > data['solutions']:
data['solutions'] = solutions
data['perimeter'] = p
return data['perimeter']
print(maximized(1000))
The number of solutions is maximised at a perimeter of 840.
Problem 112: Bouncy Numbers
Decription: Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.
Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.
We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.
Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.
Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.
Find the least number for which the proportion of bouncy numbers is exactly 99%.
The first step is to determine if a number is bouncy. Using the properties of a bouncy number, that it is neither increasing nor decreasing, we will define a function that returns true if the number is bouncy.
def bouncy(n):
"""
return true if the number is bouncy and false otherwise
"""
number = list(map(int, str(n))) # list of digits
increasing = sorted(number) # if number is sorted, it is increasing
decreasing = increasing[::-1] # if number is sorted in reverse, it is decreasing
return increasing != number and decreasing != number
Next, we will find the least number for which the proportion of bouncy numbers is exactly 99%.
I found that a while loop would work well in this case because we want the loop to run until we find the number when the proportion equals 99%. Each iteration we will check whether the number is bouncy and whether the proportion of bouncy numbers equals 99% beginning at 100.
def prop_bouncy():
"""
return least number where the proportion of bouncy numbers that is exactly 99%
"""
total = 100 # no bouncy numbers below 100
bouncy_n = 0
# continue finding bouncy numbers until proportion hits 99%
while bouncy_n / total != 0.99:
# determine if number is bouncy then increment count by one if is bouncy
if bouncy(total) is True:
bouncy_n += 1
# if proportion is eactly 99%, return number
if bouncy_n / total == 0.99:
return total
# increment total to continue finding least number
else:
total += 1
print(prop_bouncy())
The least number for which the proportion of bouncy numbers is exactly 99% is 1587000.