Number theory and a Google recruitment puzzle
There are three main steps to this question.
1) Generate an arbitrary large expansion of a mathematical expression
2) Check if a number is prime
3) Generate sliding windows of a specified width from a long iterable
We will start with the first step. The goal is to return an arbitrary expansion (expansion after the decimal) of a mathematical expression. The user inputs will be the mathematical expression along with the multiplier (can be 1) and the number of digits of the expansion.
I first tried using the decimal library to expand the mathematical expression "pi", but I realized I was approximating pi by using the expression "355/113" and I could not find a more accurate way to expand pi, so I opted to use the sympy library. I used the decimal library to expand "e".
One important thing to note is that a multiplier of the mathematical expression can be an input like "2e" or "3pi". The multiplier must be a separate input from the expression.
from decimal import *
from sympy import *
def expansion(multiplier, expression, n):
"""
Input: mathematical expression, a multiplier of the expression, and number of digits of prime number
Behavior: expands mathematical expression
Output: an arbitrary expansion (specified by user) of a mathematical expressions pi or e
"""
if expression == "pi":
# N function captures number of digits, so use log formula to capture number of specified digits after decimal
x = N(multiplier*pi, n + log(multiplier*pi, 10) + 1)
# obtain digits after decimal and return as integer
# integers that start with 0 will not capture the 0
before, after = str(x).split('.')
return int(after)
if expression == "e":
# set number of digits for expansion
getcontext().prec = n
x = (Decimal(1).exp())*multiplier
before, after = str(x).split('.')
return int(after)
# can only generate expansions of pi and e
else:
return "Can not solve"
The next step is to determine if a number is prime. To make this function efficient, we can loop through divisors in the range from 2 to the square root of the number rounded up using the ceiling function from the math module and check whether that number is a factor. The mathematical intution behind this is that a number that is not prime will have at least one factor that is less than its square root (and one factor greater). So, if a number has no factors less than its square root, it must be prime. For example, let's take the number 11. The square root of 11 rounded up is 4, so the loop will run from 2 to 4. If there are no factors in that range, that 11 is prime, which is the case. I used this mathematical intuition because looping through all numbers in the range to the specified number is very inefficient, especially because we are working with such large numbers in this question.
from math import sqrt, ceil
def prime_num(n):
"""
Input: number
Behavior: returns true if number is prime
Output: true or false
"""
# prime numbers have to be greater than 1
if n > 1:
# loop through numbers in range 2 to the ceiling of the square root of the specified number
for number in range(2, ceil(sqrt(n))):
# return to outer for loop and increment by one if input number is not divisible by number
if (n % number) == 0:
# number is not prime (divisible by a number other than one and itself)
return False
else:
# number is prime, so return true
return True
else:
# return false if number is not greater than 1
return False
The next step is to write the final helper function. The goal is to generate sliding windows of a specified width from a long iterable.
I tried a lot of different things to generate sliding windows including using itertools, but decided that using list comprehensions would be equally succinct in accomplishing this task.
First, we will make the iterable (input number) into a list of its digits as strings. For example, 1234 becomes ['1','2','3','4']. Then, we will create a window of a specified size for each element (digit) in the range of the number until a window of the specified size cannot be made. For example, if we want a window of size 3, we will loop through all the elements in range of the length of the list of digits minus the size of the window plus one. So, using our example, the loop will run from '1' to '2'. For each iteration, the window will be appeneded as a list to a list of windows. So, from our example, [['1','2','3'],['2','3','4']] will be the output from the loop. Next, we want to return a list of integers, so we will combine the digits into one number and convert to an integer. From our example, the output would be [123, 234].
def sliding_window(iterable, size):
"""
Input: integer and size of window
Behavior: generates sliding windows of a specified width from a long iterable
Output: list of windows
"""
window_list = []
# length of number has to be greater than the window size
if len(str(iterable)) >= size:
# make iterable into list of its digits
it_list = [str(x) for x in str(iterable)]
# create window as a list by grabbing elements in range of current element through the elements in the window size
windows = [it_list[x:x+size] for x in range(len(it_list) - size + 1)]
# convert list of digits in window to a single integer and append to list
for window in windows:
a_string = "".join(window)
an_integer = int(a_string)
window_list.append(an_integer)
# returns list of integers
return window_list
else:
return "Size of window bigger than iterable"
The final step is to create a function with these helper functions to return a specified digit-length prime in the decimal expansion of a mathematical expression like "pi". First, we will create the decimal expansion using the expansion helper function. Then, we will create the list of sliding windows given the size of the prime number we want using the sliding windows helper function. Finally, we will check whether each number in each window is prime using the prime helper function and return the first prime number.
def prime_expanded_expression(size, multiplier, expression, digits):
"""
Input: size of window, multiplier of expression, mathematical expression, and number of digits to expand
Behavior: returns a specified digit-length prime in the decimal expansion of a mathematical expression
Output: number
"""
# create decimal expansion of mathematical expression
expanded = expansion(multiplier, expression, digits)
# create list of sliding windows of decimal expansion given size of window
expansion_window = sliding_window(expanded, size)
# check whether each window (number) is a prime and if it is, return that number
for number in expansion_window:
# numbers that are less than a length of 10 start with 0, so cannot be prime
if len(str(number)) == 10:
# check whether number is prime
if prime_num(number):
return number
Now, we will write unit tests for each function to assert that they are returning the correct values and to check edge cases. Two tests are written for each function.
import unittest
class TestNotebook(unittest.TestCase):
def test_expansion(self):
"""test expansion."""
self.assertEqual(expansion(1, "pi", 5), 14159)
self.assertEqual(expansion(17, "pi", 9), 407075111)
def test_prime_num(self):
"""test prime_num."""
self.assertFalse(prime_num(1))
self.assertTrue(prime_num(4159))
def test_sliding_window(self):
"""test sliding_window."""
self.assertEqual(sliding_window(407075111, 4), [4070, 707, 7075, 751, 7511, 5111])
self.assertEqual(sliding_window(1234, 5), "Size of window bigger than iterable")
def prime_expanded_expression(self):
"""test prime_expanded_expression."""
self.assertEqual(prime_expanded_expression(10, 1, "e", 110), 7427466391)
self.assertEqual(prime_expanded_expression(4, 1, "pi", 110), 4159)
unittest.main(argv=[''], verbosity=2, exit=False)
Finally, let's solve the problem! The first 10-digit prime in the decimal expansion of 17π is 8649375157.
print(prime_expanded_expression(10, 17, "pi", 110))