Skip to content

Instantly share code, notes, and snippets.

@franksteinberg
Created July 30, 2018 16:32
Show Gist options
  • Save franksteinberg/df5e7bbf1eceaaa74a725cdef3af3177 to your computer and use it in GitHub Desktop.
Save franksteinberg/df5e7bbf1eceaaa74a725cdef3af3177 to your computer and use it in GitHub Desktop.
Finds the largest palindromic number that is the product of two 3-digit numbers
<?php
/**
* User: frank.steinberg
* Date: 7/30/18
* Time: 11:57 AM
*/
class FactorFinder
{
public function run()
{
$currentPalindromicNumber = 997799;
while ($currentPalindromicNumber >= 100001 ) {
$currentPalindromicNumber = $this->getNextPalindromicNumber($currentPalindromicNumber);
$factors = $this->getThreeDigitFactors($currentPalindromicNumber);
if ($factors) {
echo join(' x ', $factors) . ' = ' . $currentPalindromicNumber . PHP_EOL;
return $currentPalindromicNumber;
}
}
echo "Could not find 3-digit factors that created a palindromic number when multiplied." . PHP_EOL;
}
public function getNextPalindromicNumber($lastPalindromicNumber)
{
$convertToInt = function($value) {
return (int) $value;
};
$digits = array_map($convertToInt, str_split((string) $lastPalindromicNumber));;
if ($digits[2] > 0) {
$digits[2]--;
$digits[3]--;
return (int) (join('', $digits));
}
$digits[2] = 9;
$digits[3] = 9;
if ($digits[1] > 0) {
$digits[1]--;
$digits[4]--;
return (int) (join('', $digits));
}
$digits[1] = 9;
$digits[4] = 9;
if ($digits[0] > 0) {
$digits[0]--;
$digits[5]--;
return (int) (join('', $digits));
}
}
public function getThreeDigitFactors($n){
for ($factor1 = (int) sqrt(abs($n)); $factor1 >= 100 ; $factor1--)
{
if (
$n % $factor1 == 0
&& ($factor2 = $n / $factor1) <= 999
) {
return [
$factor1,
$factor2
];
}
}
return null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment