Approximating e in PHP and finding unique consecutive digits

Student assistants at the school have been getting interviewed with the following question when applying for a programming job:

"Please write an application to find the first 10 consecutive digits of the mathematical constant e for which every digit from 0-9 is present only once. You can use the programming language of your choice." (e.g., 1984263570)

Now, given that I'll be working with these guys, I figure I should brush up a bit and do the challenge myself. The natural choice would have been to do this in C, however I don't have a C environment handy on the ship I'm working on. I opted to try PHP since I already have an environment ready to go for it. The first part of this problem basically comes down to approximating large values of e. This means we have to move beyond just using floats or doubles into larger integer territory. Fortunately, PHP has the gmp and bc library. For some reason, I was unable to get the conversions correct with gmp, so I opted to use bc. The bc functions are slower, but they did work. The bc library is enabled by default on Windows installations of PHP.

Once using large values is no longer an issue, the next part is calculating the approximations of e. I learned that one can use a Taylor Series, such that (forgive the bad formatting), e = 1/0! + 1/1! + ... 1/n! as n approaches infinity. For accuracy, one should should subtract 3 from the decimal, and that is what I did. For more info on the math side of approximating e, one can visit the Wolfram Alpha e page. Also, nice is this question on StackOverflow. Granted, I didn't get the chance to implement a binary splitting method how they suggest, so my computation runs very slow. The goal would be for me to speed this up in with a better implementation. That said, this was just a learning and refresh exercise. I didn't have Google available at the time, though I did have a copy of Wikipedia with the page on Euler's constant e available, which made things much easier to figure out. Feel free to make suggestions on how we could improve the code below.

The last part of the problem is to find the 10 consecutive unique digits in e where no digit is repeated. The function array_unique in PHP makes this quite easy, although again there are probably more optimal ways to accomplish this. The code is marked and commented below, but you will find the answer is: 0719425863 found at digit 1730-1740. If you use the below code, you might need to increase your PHP script execution time limit as it will take about 1 minute to run depending on your setup. Hope someone finds this useful and perhaps so feedback on how to make it more efficient. Of course, having Gamma: Exploring Euler's Constant (Princeton Science Library) would have made life a bit easier and more interesting.

<?php
find_e();

function find_e() {
  $decimal_places = 2500; // number of decimal places to use
  bcscale($decimal_places); // unfortunately seems we can only set bcscale once in PHP
  $count = 0;
  // we approximate e using Taylor Series 1/0!, 1/1!, 1/2! ... 1/n! as n -> infinity
  while($count < $decimal_places) { // Iterate forward till run out of decimals or found
    if ($count < 2) {
      $factorial = 1; // 1/0! = 1 and 1/1! = 1
    }
    else {
      $factorial = bcmul($count, $factorial);
    }
    $e = bcadd($e, bcdiv(1, $factorial));
    $unique_or_not = determine_unique($e, $count, $decimal_places);
    if($unique_or_not) {
      print 'Found the unique consecutive 10 digits of e: '. implode('',$unique_or_not) . '<br>';
      print 'At location ' . $count;
      exit;
    }
    $count++;
  }
}

function determine_unique($e, $count, $max) {
  $start = 3;
  if($count < 14) {
    return FALSE; // Need a least 10 digits
  }
  while($start < ($count - 10)) {
    $real_e = substr($e, $start, 10); // we only want to use n - 3 decimal digits for accuracy
    $ten = str_split($real_e); // Cast the split out string to an array
    $is_there = count(array_unique($ten, SORT_NUMERIC)); // use array_unique to filter out duplicates, use SORT_NUMERIC for a speed increase
    if ($is_there > 9) {
      return $ten; // if there are 10 then we have a match
    }
    $start++;
  }
  return FALSE; // if not found then we return
}

Add new comment

  • No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.

Comment using an existing account (Google, Twitter, etc.)