<?php

$num = gmp_init(2, 10);     // 2 in base 10
$bases = range(6, 3, -1);   // Bases, descending order

$iteration = 0;
$update_interval = 1000;

$skip_base = -1;
$last_iter_time = microtime(true);

// Until we find an answer...
while (true) {
    $pass = true;

    foreach ($bases as $b) {
        if ($b == $skip_base) { continue; }

        // Convert to base $b
        $result = gmp_strval($num, $b);

        if ( next_candidate($result) ) {
            $pass = false;
            $num = gmp_init($result, $b);

            // The number is known to be binary in base $b, skip it next iteration
            $skip_base = $b;
            break;
        }
    }

    // Display progress every $update_interval attempts
    $iteration++;
    if ($iteration % $update_interval == 0) {
        $iter_per_sec = $update_interval / (microtime(true) - $last_iter_time);

        printf("Iteration %s; Value ~10^%s; Iter/sec %.1f" . PHP_EOL,
            number_format($iteration),
            number_format( strlen(gmp_strval($num, 10)) - 1 ),
            $iter_per_sec
        );

        $last_iter_time = microtime(true);
    }

    if ($pass) { break; }
}


$result = gmp_strval($num, 10);
$result_len = strlen($result);

printf("Result found after %s iterations, result is %s digits long\n",
    number_format($iteration),
    number_format($result_len)
);

if ($result_len <= 100) {
    echo $result . "\n";
}

file_put_contents("result.num", $result);
exit(0);





// Returns TRUE if the number was changed, FALSE otherwise
function next_candidate(&$num) {
    $num_len = strlen($num);
    $last_zero  = -1;
    $reject_pos = -1;

    // Find the first non-binary character and its location or return if there isn't one
    if ( preg_match('/[^01]/', $num, $hits, PREG_OFFSET_CAPTURE) ) {
        $reject_pos = $hits[0][1];

    } else {
        return false;
    }


    // Find the last zero before the reject character
    $last_zero = strrpos( $num, "0", -1*($num_len - $reject_pos) );


    if ($last_zero == false) {
        // If there were no zeroes before the reject, the next candidate is a one followed by N zeros,
        //   where N is the length of the original number
        // e.g. "111" => "1000"
        $num = "1" . str_repeat("0", $num_len);

    } else {
        // If there was a zero before the reject, replace it with a 1 and everything after with a zero.
        $num = substr($num, 0, $last_zero) . "1" . str_repeat("0", $num_len - $last_zero - 1);
    }

    return true;
}

?>