Solving Google’s billboard challenge

Sean ZieglerProgramming, Python

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

Clearly, this was a challenge to the nerds of Silicon Valley. The solution is known and the challenge has been over for nearly a decade, but it still represents an interesting problem for 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. This is called 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 does return 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 any 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  \]



so \ p is not prime.

Liar and Witness numbers

Unfortunately, Fermat's Little Theorem is foolproof and can generate false positives. These are known as 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. These numbers are known as Carmichael numbers. I encourage you to prove this to yourself (probably via code since the numbers can be exceptionally difficult to keep manage).

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

It follows that 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 to run because the exponentials that need to be calculated when \ n is a 10 digit number are huge. Nevertheless, it's a more interesting solution to the problem than simply using trail division.

That's all there is to the Google Billboard Challenge. I'm going to 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 licence.

Leave a Reply

Your email address will not be published. Required fields are marked *