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 * *is to check if the number is divisible by any number from 1 to . 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 is some prime number then:

In layman's terms, this means that for some prime number and any integer less than , is always divisible by .

For example: let's choose a prime number to be 23 and to be 3.

so is prime.

Now, let equal 24 (not prime) and let's see what happens:

so 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 equal 15 and let equal 4 and let's check if 15 is prime (it isn't):

so is prime (false positive).

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

This begs the question: is there any number such that every from 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 being a Carmichael number is:

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 iterations. In reality, it takes a long time to run because the exponentials that need to be calculated when 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.