The Google Billboard Puzzle

A recent Programming Praxis problem resurrected the famous Google billboard puzzle. Back in July of 2004, Google put up billboards all over the country reading

Those who solved the problem and followed the link found another puzzle whose answer was the password to a second site. The second site was an invitation to submit a CV to Google. All-in-all a pretty effective way of advertising for the type of engineers that Google was looking for.

The first puzzle (finding the 10-digit prime) isn’t hard in principle: generate the digits of e and check each consecutive group of 10 for primality. But consider for a moment how you would have gone about solving the problem. The first step is generating the digits of e. A recent Programming Praxis problem deals with this but the algorithm is complicated and given in terms of the code used to implement it. That’s neither interesting nor enlightening and in any event we only want the digits once so there’s no point in spending a lot of time writing code to generate them. Instead, we can go to this NASA site and get the first million digits of e already calculated for us. Of course, it may be that the first 10-digit prime is not in the first million digits but, in context, that seems unlikely and it is, in any event, easy enough to check that it’s worth using as a first attempt.

The second problem is checking for primality. A 10-digit number is small enough that we can simply try factoring them using, for example, the Unix factor command. But it just so happens that I have an implementation of the Miller-Rabin primality test lying around so let’s just use that.

;; In case you want to finish in this lifetime.
;; Using ash makes no appreciable difference.
;; (pushnew :use-ash *features*)
(defun modexp (b e n)
  "Modular exponentiation"
  (flet ((sqmod (x n) (mod (* x x) n)))
    (cond ((zerop e) 1)
#-use-ash ((evenp e) (modexp (sqmod b n) (/ e 2) n))
#-use-ash (t (mod (* b (modexp (sqmod b n) (/ (1- e) 2) n)) n))
#+use-ash ((evenp e) (modexp (sqmod b n) (ash e -1) n))
#+use-ash (t (mod (* b (modexp (sqmod b n) (ash e -1) n)) n)))))

(defun canonicalize (n)
  "Express n as (2^r)s + 1, where s is odd."
  (do ((r 0 (1+ r)) (s (1- n) (ash s -1)))
      ((oddp s) (values r s))))

(defun check (r s n)
  "Miller-Rabin primality check"
  (let* ((n-1 (1- n)) (a (1+ (random n-1))))
    (or (= (modexp a s n) 1)
        (dotimes (j (1+ r) nil)
          (if (= (modexp a (* (ash 1 j) s) n) n-1)
              (return t))))))

(defun primep (n)
  "Make 50 checks for primality of n. Probability of a false positive is
less than 8e-31."
  (if (or (and (/= n 2) (evenp n)) (< n 0))
      nil
      (multiple-value-bind (r s) (canonicalize n)
        (dotimes (k 50 t)
          (if (not (check r s n))
              (return nil))))))

The Miller-Rabin test is probabilistic so each number has 50 checks applied to it before it’s accepted as prime.

With those two parts of the solution in place, it’s easy to find the prime

(defparameter eo10  ;;digits truncated for display
  "271828182845904523536028747135266249775724709
369995957496696762772407663035354759457138217852
516642742746639193200305992181741359662904357290
033429526059563073813232862794349076323382988075
319525101901157383418793070215408914993488416750
92447614606680822648001684774...")

(defun search-for-prime ()
  (let ((end (- (length eo10) 10)))
    (do ((i 0 (1+ i)))
        ((> i end) nil)
      (with-input-from-string (s eo10 :start i :end (+ i 10))
        (if (miller-rabin:primep (read s))
            (return (subseq eo10 i (+ i 10))))))))

When we run this, we get the solution almost immediately

CL-USER> (search-for-prime)
"7427466391"

We can, if we like, check this using factor but a 50 iteration Miller-Rabin test is pretty definitive. In terms of this problem, we’ll know right away if we’re wrong because 7427466391.com won’t resolve.