Solving Google’s billboard challenge

In 2004, mysterious billboard was erected on Highway 101 in Silicon Valley. The billboard had no company listed and said “{first 10-digit prime found in consecutive digits of e}.com”.

This was a challenge to the nerds of Silicon Valley. The challenge has been over for nearly a decade, but it still represents an interesting problem to solve.

Prime Numbers

Perhaps the most difficult portion of solving the billboard challenge comes in understanding what makes a number prime.

A prime number is a number that is only divisible by itself and one. The most common primality test for a number $ \n$ is to check if the number is divisible by any number from 1 to $\sqrt n $. We call this trial division, and the code to implement this is relatively straightforward.

import math
def basicPrime(n):
    if n <= 2:
        raise ValueError
    if not type(n) == int:
        raise TypeError   
    prime = True
    for iter in range(2, math.floor(math.ceil(math.sqrt(n))) + 1):
        if n % iter == 0:
            prime = False
            break
    if prime:
        print('%s is the first 10 digit prime in e.' % n)
    return prime

The output generated from the code returns the correct answer:

7427466391

This method works, but it is just brute-forcing the problem. There is a more fun way to solve the problem using a more advanced algorithm.

Fermat’s Little Theorem

Fermat’s Little Theorem (stated originally in 1640) is an interesting way of checking if a number is prime.

The theorem states that if $\ p $ is some prime number then

\[ a^p \equiv a (mod p) \]

In layman’s terms, this means that for some prime number $\ p $ and an integer $\ a $ less than $\ p $, $\ a^p - a $ is always divisible by $\ p $.

For example: let’s choose a prime number $\ p $ to be 23 and $\ a $ to be 3.

\[ 3^{23} - 3 = 94143178827 - 3 = 94143178824 = 23 * 4093181688 \]

so $\ p $ is prime.

Now, let $\ p $ equal 24 (not prime) and let’s see what happens:

\[ 3^{24} - 3 = 282429536481 - 3 = 282429536478 = 24 * 11767897353.3 \]

since the result is not an integer, $\ p $ is not prime.

Liar and Witness numbers

Unfortunately, Fermat’s Little Theorem is not foolproof and can generate false positives. We call these liar’s numbers.

For example, let $\ p $ equal 15 and let $\ a $ equal 4 and let’s check if 15 is prime (it isn’t):

\[ 4^{15} - 4 = 1073741824 -4 = 1073741820 = 15 * 71582788 \]

so $\ p $ is prime (false positive).

False positives like this exist but using a different $\ a $ value usually reveals a liar’s number to be composite (These are called witness numbers).

This begs the question: is there any number $\ n $ such that every $\ a $ from $\ 0 < a < n -1 $ a false positive is returned?

Carmichael Numbers

The answer is yes! In fact, there are infinitely many numbers that will always return a false positive. We know these numbers as Carmichael numbers. I encourage you to prove this to yourself (probably via code since the numbers can be exceptionally difficult to manage).

Does this mean that Fermat’s Little Theorem is incorrect or useless? It isn’t perfect, but per Wikipedia, there are 2183 Carmichael numbers between 0 and 25,000,000,000.

The chance of $\ n $ being a Carmichael number is:

\[\frac{2183}{250000000000} = 0.00000008732 \] or .000008732%

That’s accurate enough for the purpose of solving this challenge. So let’s implement it in code.

import math
import random
from fractions import gcd
def fermatPrime(n):
     tests = [random.randint(2,10) for i in range(5)]
     prime = True 
     for a in tests:
         print(a,n)
         x = gcd(a,n) == 1 # why
         y = (a**n - 1) % n == 1
         print('n: %s A: %s GCD: %s Fermat: %s' % (n, a, x, y))
         if not x or not y:
             prime = False
             break.
     if prime:
         print('%s is the first 10 digit prime in e.' % n)
    return prime

This code also returns the correct answer of

7427466391 

but it only conducts 6 iterations rather than $\ sqrt(n) $ iterations. In reality, it takes a long time calculate the exponentials needed when $\ n $ is a 10 digit number. It’s a more interesting solution to the problem than using trial division.

That’s all there is to the Google Billboard Challenge. I will write some tests using Python’s unittest module to provide a quick way to check if the functions are still working.

import unittest
from basicPrime import basicPrime
def test_basicPrimesWithComposities(self):
         firstComposites = [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36]
         for composite in firstComposites:
             self.assertFalse(basicPrime(composite))
def test_basicPrimesWithNegativeZeroOne(self):
         with self.assertRaises(ValueError):
             basicPrime(-1)
         with self.assertRaises(ValueError):
             basicPrime(0)
         with self.assertRaises(ValueError):
             basicPrime(2)
def test_basicPrimeWithPrimes(self):
         firstPrimes = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
         for prime in firstPrimes:
             self.assertTrue(basicPrime(prime))
## Repeated for fermatPrime - omitted from blog for brevity
if __name__ == '__main__':
     unittest.main()

That’s all I have for now. Thanks for reading. If you’re interested in the full source all my projects are available on my GitHub under an MIT license.