{"id":879,"date":"2012-07-02T07:10:53","date_gmt":"2012-07-02T11:10:53","guid":{"rendered":"http:\/\/irreal.org\/blog\/?p=879"},"modified":"2012-07-02T07:11:59","modified_gmt":"2012-07-02T11:11:59","slug":"the-google-billboard-puzzle","status":"publish","type":"post","link":"https:\/\/irreal.org\/blog\/?p=879","title":{"rendered":"The Google Billboard Puzzle"},"content":{"rendered":"

A recent Programming Praxis<\/a> problem resurrected the famous Google billboard puzzle<\/a>. Back in July of 2004, Google put up billboards all over the country reading<\/p>\n

\n

{FIRST 10-DIGIT PRIME IN CONSECUTIVE DIGITS OF E}.COM<\/code><\/p>\n<\/div>\n

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.<\/p>\n

The first puzzle (finding the 10-digit prime) isn’t hard in principle: generate the digits of e<\/code> 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<\/code>. A recent Programming Praxis problem<\/a> 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<\/a> and get the first million digits of e<\/code> 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.<\/p>\n

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<\/code> command. But it just so happens that I have an implementation of the Miller-Rabin primality test<\/a> lying around so let’s just use that.<\/p>\n

;; <\/span>In case you want to finish in this lifetime.<\/span>\r\n;; <\/span>Using ash makes no appreciable difference.<\/span>\r\n;; <\/span>(pushnew :use-ash *features*)<\/span>\r\n(defun<\/span> modexp<\/span> (b e n)\r\n  \"Modular exponentiation\"<\/span>\r\n  (flet<\/span> ((sqmod (x n) (mod (* x x) n)))\r\n    (cond<\/span> ((zerop e) 1)\r\n#-use-ash ((evenp e) (modexp (sqmod b n) (\/ e 2) n))\r\n#-use-ash (t (mod (* b (modexp (sqmod b n) (\/ (1- e) 2) n)) n))\r\n#+use-ash ((evenp e) (modexp (sqmod b n) (ash e -1) n))<\/span>\r\n#+use-ash (t (mod (* b (modexp (sqmod b n) (ash e -1) n)) n))<\/span>)))\r\n\r\n(defun<\/span> canonicalize<\/span> (n)\r\n  \"Express n as (2^r)s + 1, where s is odd.\"<\/span>\r\n  (do<\/span> ((r 0 (1+ r)) (s (1- n) (ash s -1)))\r\n      ((oddp s) (values r s))))\r\n\r\n(defun<\/span> check<\/span> (r s n)\r\n  \"Miller-Rabin primality check\"<\/span>\r\n  (let*<\/span> ((n-1 (1- n)) (a (1+ (random n-1))))\r\n    (or (= (modexp a s n) 1)\r\n        (dotimes<\/span> (j (1+ r) nil)\r\n          (if<\/span> (= (modexp a (* (ash 1 j) s) n) n-1)\r\n              (return<\/span> t))))))\r\n\r\n(defun<\/span> primep<\/span> (n)\r\n  \"Make 50 checks for primality of n. Probability of a false positive is<\/span>\r\nless than 8e-31.\"<\/span>\r\n  (if<\/span> (or (and (\/= n 2) (evenp n)) (< n 0))\r\n      nil\r\n      (multiple-value-bind<\/span> (r s) (canonicalize n)\r\n        (dotimes<\/span> (k 50 t)\r\n          (if<\/span> (not (check r s n))\r\n              (return<\/span> nil))))))<\/pre>\n
The Miller-Rabin test is probabilistic so each number has 50 checks applied to it before it’s accepted as prime.<\/p>\n
With those two parts of the solution in place, it’s easy to find the prime<\/p>\n
(defparameter<\/span> eo10<\/span>  ;;<\/span>digits truncated for display<\/span>\r\n  \"271828182845904523536028747135266249775724709<\/span>\r\n369995957496696762772407663035354759457138217852<\/span>\r\n516642742746639193200305992181741359662904357290<\/span>\r\n033429526059563073813232862794349076323382988075<\/span>\r\n319525101901157383418793070215408914993488416750<\/span>\r\n92447614606680822648001684774...\"<\/span>)\r\n\r\n(defun<\/span> search-for-prime<\/span> ()\r\n  (let<\/span> ((end (- (length eo10) 10)))\r\n    (do<\/span> ((i 0 (1+ i)))\r\n        ((> i end) nil)\r\n      (with-input-from-string<\/span> (s eo10 :start<\/span> i :end<\/span> (+ i 10))\r\n        (if<\/span> (miller-rabin:primep (read s))\r\n            (return<\/span> (subseq eo10 i (+ i 10))))))))<\/pre>\n
When we run this, we get the solution almost immediately<\/p>\n
CL-USER> (search-for-prime)\r\n\"7427466391\"<\/span><\/pre>\n
We can, if we like, check this using factor<\/code> 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<\/code> won’t resolve.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 {FIRST 10-DIGIT PRIME IN CONSECUTIVE DIGITS OF E}.COM Those who solved the problem and followed … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[14],"class_list":["post-879","post","type-post","status-publish","format-standard","hentry","category-programming","tag-lisp"],"_links":{"self":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/879","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=879"}],"version-history":[{"count":1,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/879\/revisions"}],"predecessor-version":[{"id":899,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/879\/revisions\/899"}],"wp:attachment":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=879"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=879"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=879"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}