Prime in an Arbitrary Expansion of π
Google had a recruitment puzzle in which the candidate is asked to find the first 10-digit prime in the decimal expansion of 17π. In this blog, I go through how I approached this problem.
One of the challenges with the problem is generating an arbitrary large expansion of a natural irrational number like π. This of course wouldn’t be a problem if all that we are looking for is 10 decimal points, which could be easily achieved with `numpy`. However, there is an intrinsic problem with the limit precision of that a computer can handle if we want higher precisions. Therefore, a different solution needs to be used to achieve that.
With that in mind, I’ve decided to use the divide-and-conquer approach by splitting the questions into 3 sub-problems:
1. Create a function that generates an arbitrary expansion of π;
2. Create a function that checks if a number is prime
3. Create a function that generates sliding windows of any size on a string.
This part is used in combination with the 2nd function to identify the first 10-digit prime in the string version of the expanded expression.
1st Function:
For this part, I’m using the `sympy` package, which is an open-sourced package for symbolic computation. It contains special constants like π, e, etc., which can be evaluated with arbitrary precision. Therefore, my first function takes 2 argument, a `sympy` expression and an integer that defines the precision:
2nd Function:
Many different approaches could be taken to check if a given number is prime. One of such method is the Sieve of Eratosthenes algorithm, which produces a list of primes below a given number. However, this algorithm might be an overkill for this problem since I’m only looking to check if a single number.
Instead, I try to find a divisor for the given number that yields no remainder. If such a divisor exists, the number cannot be a prime. To achieve this, I perform division on all numbers from 2 to the square root of the given number. Square root is chosen because it should be the largest possible divisor (anything larger than the square root is essentially dividing quotients resulted from previous divisions). To make sure that the square root operation yields an integer, I use `int()` function to convert any floating number to an integer, which is the same as rounding down a decimal. I then add 1 to the resulting value. This is illustrated in the code snippet below:
3rd Function:
To perform sliding window on a number, I have to first cast the number to a string, which then allows me to use slices of the string as a window. On top of that, I am using a loop that runs from the first element of the string, to the last element short by the the window length. Finally, all the windows are stored in a list, which allows for further manipulation, as shown below:
These 3 functions are used together to calculate the first 10-digit prime in the arbitrary expansion of 17π. More specifically, I first produce a string version of the expansion with 200 decimal places. I then create a list of windows of length 10, which is a list a strings. Finally, I use a while loop to check if any element is prime. This idea is shown in the following snippet:
The complete implementation can be found in this notebook:
