Project Euler Problem 10

Project Euler Problem 10: Calculate the sum of all the primes below two million.

Brute force (optimized to only look at 6n±1)...

<?php

function is_prime($n)
{
  if ($n < 5) return ($n == 2 || $n == 3);
  for ($p = 2; $p <= 3; $p++)
    if (!($n%$p)) return (($n /= $p) == 1);
  for ($p = 5, $r = floor(sqrt($n)); $p <= $r; $p += 6)
  {
    if (!($n%$p)) return false;
    if (!($n%($p+2))) return false;
  }
  return true;
}

function sum_primes($l)
{
  if ($l < 2) return 0;
  if ($l < 3) return 2;
  if ($l < 5) return 5;
  for ($s = $p = 5; $p <= $l; $p += 6)
  {
    if (is_prime($p)) $s += $p;
    if (is_prime($p+2) && $p+2 <= $l)
      $s += $p+2;
  }
  return $s;
}

echo sum_primes(2000000); // time 6.126s

?>

Since we know the upper limit, we can sieve...

<?php

function prime_sieve($l)
{
  $b = ($l-1)/2;
  $p = array_fill(1, $b, 0);
  $c = (floor(sqrt($l))-1)/2;
  for ($i = 1; $i <= $c; $i++)
    if (!$p[$i])
      for ($j = 2*$i*($i+1); $j <= $b; $j += 2*$i+1)
        $p[$j] = 1;
  return $p;
}

function sum_prime_sieve($l)
{
  $b = count($p = prime_sieve($l));
  for ($i = 1, $s = 2; $i <= $b; $i++)
    if (!$p[$i]) $s += (2*$i+1);
  return $s;
}

echo sum_prime_sieve(2000000); // time 1.042s

?>

Project Euler Problem 9

Project Euler Problem 9: Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

<?php


for ($m = 2 ; ; $m++)
{
  for ($n = 1 ; $n < $m; $n++)
  {
    $a = pow($m, 2)-pow($n, 2);
    $b = 2*$m*$n;
    $c = pow($m, 2)+pow($n, 2);
    if ($a+$b+$c == 1000) break 2;
  }
}
echo $a*$b*$c;

?>

Project Euler Problem 8

Project Euler Problem 8: Discover the largest product of five consecutive digits in the 1000-digit number.

<?php

$n = "73167176531330624919225119674426574742355349194934"
    ."96983520312774506326239578318016984801869478851843"
    ."85861560789112949495459501737958331952853208805511"
    ."12540698747158523863050715693290963295227443043557"
    ."66896648950445244523161731856403098711121722383113"
    ."62229893423380308135336276614282806444486645238749"
    ."30358907296290491560440772390713810515859307960866"
    ."70172427121883998797908792274921901699720888093776"
    ."65727333001053367881220235421809751254540594752243"
    ."52584907711670556013604839586446706324415722155397"
    ."53697817977846174064955149290862569321978468622482"
    ."83972241375657056057490261407972968652414535100474"
    ."82166370484403199890008895243450658541227588666881"
    ."16427171479924442928230863465674813919123162824586"
    ."17866458359124566529476545682848912883142607690042"
    ."24219022671055626321111109370544217506941658960408"
    ."07198403850962455444362981230987879927244284909188"
    ."84580156166097919133875499200524063689912560717606"
    ."05886116467109405077541002256983155200055935729725"
    ."71636269561882670428252483600823257530420752963450";

for ($i = $p = 0, $q = 1; $i < strlen($n)-4; $i++, $q = 1)
  for ($j = 0; $j < 5; $j++)
    $p = max($p, ($q *= $n[$i+$j]));
echo $p;

?>

Project Euler Problem 7

Project Euler Problem 7: Find the 10001st prime.

<?php

function is_prime($n)
{
  if ($n < 5) return ($n == 2 || $n == 3);
  for ($p = 2; $p <= 3; $p++)
    if (!($n%$p)) return (($n /= $p) == 1);
  for ($p = 5, $r = floor(sqrt($n)); $p <= $r; $p += 6)
  {
    if (!($n%$p)) return false;
    if (!($n%($p+2))) return false;
  }
  return true;
}

function nth_prime($n)
{
  if ($n < 1) return false;
  if ($n < 3) return $n+1;
  for ($n -= 2, $p = 5 ; ; $p += 6)
  {
    if (is_prime($p) && !--$n) break;
    if (is_prime($p+2) && !--$n)
    {
      $p += 2;
      break;
    }
  }
  return $p;
}

echo nth_prime(10001);

?>

Project Euler Problem 6

Project Euler Problem 6: What is the difference between the sum of the squares and the square of the sums?

<?php

function diff_sumsqrs_sqrsums($n)
{
 for ($i = $s1 = $s2 = 1; $i < $n; 
   $i++, $s1 += $i, $s2 += pow($i, 2));
 return pow($s1, 2)-$s2;
}

echo diff_sumsqrs_sqrsums(100);

?>

Project Euler Problem 5

Project Euler Problem 5: What is the smallest number divisible by each of the numbers 1 to 20?

<?php

for ($n = 20; ; $n += 20)
{
 for($i = 20; $i > 10; $i--)
   if ($n%$i) continue 2;
 break;
}
echo $n;

?>

Project Euler Problem 4

Project Euler Problem 4: Find the largest palindrome made from the product of two 3-digit numbers.

<?php

$p = 0;
for ($i = 999; $i > 99; $i--)
 for ($j = $i; $j > 99; $j--)
  if (($n = $i*$j) == strrev($n))
   $p = max($n, $p);
echo $p;

?>

Project Euler Problem 3

Project Euler Problem 3: Find the largest prime factor of a composite number.

<?php

function lpf($n)
{
  if ($n < 2) return false;
  for ($p = 2; $p <= 3; $p++) 
    while (!($n%$p))
      if (($n /= $p) == 1) return $p;
  for ($p = 5, $d = 1; pow($p, 2) <= $n; 
    $p += 3-$d, $d *= -1)  
    while (!($n%$p))
      if (($n /= $p) == 1) return $p;
  return $n;
}

echo lpf(600851475143);

?>

Project Euler Problem 2

Project Euler Problem 2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

<?php

$s = $t = 2;
while (($t = round($t * pow((sqrt(5)/2)+0.5, 3))) 
  < 4000001) $s += $t; 
echo $s;

?>

Project Euler Problem 1

Project Euler Problem 1: Add all the natural numbers below one thousand that are multiples of 3 or 5.

<?php

$s = 0;
for ($i = 3; $i < 1000; $i++) 
  if (!($i%3) || !($i%5)) $s += $i;
echo $s;

?>

The Lost Symbol: 1 of 33

A week before publication, Knoph Doubleday released an online promotional game called Symbol Quest for its soon to be published Dan Brown book, The Lost Symbol. If you answered all the questions right, which involved selecting a symbol to match a given clue, and you got all 33 symbols right without missing any, you heard the following recorded message:

"This is Dan Brown. Congratulations on playing Symbol Quest and reaching the 33rd degree with a perfect score. I’ve just finished signing 33 first editions of the lost symbol which are locked in the vault, waiting to be sent out to the 33 different winners. The 33 first winning code breakers who call the secret phone numbers, encrypted on the book jacket, will receive this reward. Good luck."

High resolution images of the front cover (and later the spine) had been available since earlier in the month, so a lot of people were starting to look for that phone number. Given what was available in the images, and presuming that the number was most likely in the block of numbers used by Random House (Knoph Doubleday's parent company)... 10 numbers were most likely.

I apologize to the seven or so employees who have real work extensions at one of these 10 numbers. I hope you have been able to change your number and for the week of annoying phone calls.

Turns out that the actual phone number was just answering with "Leave a message..." until late afternoon on September 14th. At 4:30 pm MDT I called the number which instructed all those that called to send an email to a randomhouse.com email address with "Robert Langdon's favorite symbol" as the subject and contact info as the body.

Then the wait...

Around October 2nd, first reports of people having received a signed book started appearing on Twitter... seemed that people closest to the Manhattan Offices of Random House were reporting first. I held my breath everyday I checked my box, but nothing. Then on October 5th, someone in the Midwest got theirs and I was sure that it was the day. Nothing. And nothing the next day (I live in New Mexico).

I had all but given up hope. It was the first Tuesday, Lodge night. I was getting ready to head over to the Lodge when a ring sounded on the doorbell. My wife answered and found the UPS package there... stiff yellow envelope... one of the seams had split and you could see the spine of The Lost Symbol through it. I ran around the house a little more than I'd like to admit.

Congratulations! You are 1 of 33 winners of Symbol Quest.

By the way... finishing Symbol Quest now, give you the following message:

"This is Dan Brown. Congratulations on completing the symbol quest, in reaching the 33rd degree with no errors. As you may have noticed the book jacket in the US is covered with symbols and icons. Encoded within them, are five hidden messages for you to find and decrypt. Best of luck and i hope you enjoyed the novel."

As far as I know, only 4 of the hidden messages have been discovered. Also if you call the phone number now, the message has changed to what can only be described as some sort of chant... speculations abound.

The Lost Symbol: ALL GREAT TRUTHS

The back cover of Dan Brown's The Lost Symbol contains a classic Masonic cipher that decodes to the following...

"ALL GREAT TRUTHS BEGIN AS BLASPHEMIES"

...a quote from George Bernard Shaw's Annajanska (1919)

The Lost Symbol: POPES PANTHEON

The Lost Symbol cover has these two number sequences:

"22-65-22-97-27"

"22-23-44-1-133-97-65-44"

which can be decoded (using substitution) to "POPES PANTHEON" perhaps referring to the Jefferson Memorial which was designed by John Russell Pope, but more likely refers to the House of the Temple, Home of The Supreme Council, 33°, Ancient & Accepted Scottish Rite of Freemasonry, Southern Jurisdiction.



UPDATE: It appears that a gentleman named Billy Gates notified (or was working in conjunction with) with the Secrets of the Lost Symbol blog on August 26 at 4:22 p.m. even though they didn't publish the find until Sunday September 13. I'm glad that there is now confirmation of this find and that it appears to be on the right track... to what is still anyone's guess. At least one other gentleman named "Ted" came up with the same independently, his comment is at the Cryptex.

UPDATE 2: Whereas, There are people, including myself, that were working on this code before the book was released; and whereas, Billy Gates has also tried explaining the same to the commenters here; and whereas, Most people working on these codes presumed they were page or chapter numbers and could therefore use mono/poly-alphabetic substitution; and whereas, The book having been published, we can all see now that the numbers refer to chapters; and whereas, We all know that this is the same strategy Dan Brown used in Digital Fortress; and Whereas, People have called my cell phone to personally tell me that I'm "making this all too complicated" and such; NOW, BE IT THEREFORE Resolved, that any post published before September 15, 2009 is most likely referring to efforts to decode clues on the cover without physically having the book.

Open Letter to Zend

Dear Zend Technologies Ltd.:

We want a 64-bit Zend Debugger for Mac x86_64. I think it's about time.

Sincerely,

Benjamin Morin (and every Zend PHP developer who's bought a Mac since Early 2008)

UPDATE: A hardy round of applause to Zend for releasing a Debugger for Mac x86_64. It is available here.