Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. In this post, three problems solved from the Euler Project using Python. Every function was annotated with nuympy-styple docstrings.
1001st prime
Problem 7 (420680 Solved)
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10, 001st prime number?
My solution:
For solving this problem, we can first find a list of the first n prime number and then return the last one. The helper function isPrime() is to determine whether an interger is prime. Once isPrime(x) returns True, we put the int x to the prime_list[]. Append the prime_list[] until the length of prime_list equals to 10 001. Return the last element of the prime_list which is the 10 001st prime number.
def isPrime(x):
"""
Determine whether an integer is prime
Parameters
----------
x : int
Returns
-------
bool
"""
if x ==2:
return True
for i in range(2, x//2 + 1):
if x%i == 0:
return False
return True
def prime_list(n):
"""
Find a list of the first n prime numbers and the nth prime number
Parameters
----------
n : int
Returns
-------
prime_list[n-1] : int
"""
prime_list = []
i = 2
while len(prime_list) < n:
if isPrime(i):
prime_list.append(i)
i+=1
return prime_list[n-1]
prime_list(10001)
104743
Double-base palindromes
Problem 36 (87508 Solved)
The decimal number, 585 = $1001001001_2$(binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include leading zeros.)
My solution:
For solving this problem, we can count from 0 to one million and determine whether each number is double-base palindromes. Finally, add all double-base palindromes up. Note: in the function isPalindrome(), s[::-1] will return the reverse string, and bin(n) will method converts and returns the binary equivalent string of a given integer n.
def sumPalindrome(n):
"""
The sum of all numbers, less than n, which are double-base palindromes
Parameters
----------
n : int
Returns
-------
ans : int
"""
ans = sum(i for i in range(n) if isPalindrome(i))
return ans
def isPalindrome(n):
"""
Determine whether an number is palindromic in both bases.
Parameters
----------
n : int
Returns
-------
bool
"""
s = str(n)
if s != s[ : : -1]:
return False
t = bin(n)[2:]
if t != t[::-1]:
return False
return True
sumPalindrome(1000000)
872187
Palindromic sums
Problem 125 (12856 Solved)
The palindromic number 595 is interesting because it can be written as the sum of consecutive squares:$ 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2+ 12^2$.
There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is 4164. Note that $1 = 0^2 + 1^2$ has not been included as this problem is concerned with the squares of positive integers.
Find the sum of all the numbers less than $10^8$ that are both palindromic and can be written as the sum of consecutive squares.
My solution:
For solving this problem, we can simply try every possible sum of consecutive squares and determine whether the sum is palindromic. Note that in the for loop, we limit the start number of consecutive squares from 1 to 10000 because $1 = 0^2 + 1^2$ not included and $10001^2 > 10^8$ which is not what we need to consider.
Besides, to get rid of duplications, I put all these palindromes into a set. So this set contains all the numbers less than $10^8$ that are both palindromic and can be written as the sum of consecutive squares. Then we add them up.
def sumPalindrome(n):
"""
Find the sum of all the numbers less than 10^8^ that are both palindromic and can be written as the sum of consecutive squares.
Parameters
----------
n : int
Returns
-------
sum(num) : int
"""
num = set()
for i in range(1, 10001):
square = i * i
j = i+1
while square <= n:
square += j * j
s = str(square)
if s == s[ : : -1]:
num.add(square)
j +=1
return sum(num)
sumPalindrome(100000000)
2906969179