Skip to content

Instantly share code, notes, and snippets.

@Buggytheclown
Last active September 15, 2018 06:36
Show Gist options
  • Save Buggytheclown/f6220389980bb6365d43fa6a6c2b6837 to your computer and use it in GitHub Desktop.
Save Buggytheclown/f6220389980bb6365d43fa6a6c2b6837 to your computer and use it in GitHub Desktop.
Largest palindrome that is product of 2 prime 5 digit number
const MAX_DIVISOR = 99999;
const MIN_DIVISOR = 10000;
function isPalindrome(number) {
let rebmun = 0;
let remainder = number;
while (remainder !== 0) {
let lastDigit = remainder % 10;
rebmun = rebmun * 10 + lastDigit;
remainder = (remainder - lastDigit) / 10;
}
return number === rebmun;
}
function getPrimeDivisors(oddNumber) {
if (oddNumber % 2 === 0) return [];
for (let i = 3; i <= Math.sqrt(oddNumber); i += 2) {
if (oddNumber % i === 0) {
if (i < MIN_DIVISOR) {
return [];
} else {
return [i, oddNumber / i];
}
}
}
return [];
}
function getMaxPalindrome(fromOdd) {
while (!isPalindrome(fromOdd)) {
fromOdd -= 2;
}
return fromOdd;
}
function getPrevPalindrome(palindrome) {
function digitsCount(number) {
let count = 0;
while (number !== 0) {
count++;
number = ~~(number / 10);
}
return count;
}
function calcPalindrome(num, count) {
let partToMerge = count % 2 ? ~~(num / 10) : num;
while (partToMerge) {
let lastDigit = partToMerge % 10;
num = num * 10 + lastDigit;
partToMerge = (partToMerge - lastDigit) / 10;
}
return num;
}
const palindromeLength = digitsCount(palindrome);
const newFirstPart = ~~(palindrome / Math.pow(10, ~~(palindromeLength / 2))) - 1;
const prevPalindrome = calcPalindrome(newFirstPart, palindromeLength);
return palindromeLength > digitsCount(prevPalindrome) ? (prevPalindrome * 10 + 9) : prevPalindrome;
}
function main() {
let palindrome = getMaxPalindrome(MAX_DIVISOR * MAX_DIVISOR);
let divisors = getPrimeDivisors(palindrome);
while (divisors.length !== 2) {
palindrome = getPrevPalindrome(palindrome);
divisors = getPrimeDivisors(palindrome);
}
return {palindrome, divisors};
}
// ********** another file.js **********
console.time('main');
eq(main(), {palindrome: 999949999, divisors: [30109, 33211]});
// console.log(main());
console.timeEnd('main');
// runTests();
function eq(obj1, obj2, txt = 'Eq fail') {
const isEq = JSON.stringify(obj1) === JSON.stringify(obj2);
if (isEq) {
return true;
} else {
console.log('expect eq: ');
if (Array.isArray(obj1) && Array.isArray(obj2)) {
for (let i = 0; i < obj1.length; i++) {
if (obj1[i] !== obj2[i]) {
console.log(`${obj1[i]} !== ${obj2[i]}`);
}
}
} else {
console.log(obj1);
console.log(obj2);
}
throw new Error(txt);
}
}
function runTests() {
(function () {
console.log('__isPolindrome__: START');
const truthy = [997799, 996699, 995599, 994499, 993399, 992299, 991199, 990099, 989989, 988889, 987789, 986689, 985589, 984489, 983389, 982289, 981189, 980089, 979979, 978879];
const falsy = [9799, 9916699, 1995599, 9944991, 9923399, 9922919, 9901199, 9090099, 9189989, 988189, 97789, 981689, 9815589, 1984489, 9833891, 1982289, 9081189, 9089, 11110000, 11100];
truthy.forEach(el => eq(isPalindrome(el), true, `must be a isPolindrome: ${el}`));
falsy.forEach(el => eq(isPalindrome(el), false, `must not be a isPolindrome: ${el}`));
console.log('__isPolindrome__: COMPLETED');
})();
(function () {
console.log('__getPrimeDivisors__: START');
let mock = [
{divisors: [65327, 153073], num: 9999799871},
{divisors: [34429, 290447], num: 9999799763},
{divisors: [31513, 317323], num: 9999799699},
{divisors: [15679, 637783], num: 9999799657},
{divisors: [87433, 114371], num: 9999799643},
{divisors: [39323, 254299], num: 9999799577},
{divisors: [16301, 613447], num: 9999799547},
{divisors: [15359, 651071], num: 9999799489},
{divisors: [11503, 869321], num: 9999799463},
{divisors: [11527, 867511], num: 9999799297},
{divisors: [79349, 126023], num: 9999799027}
];
mock.forEach(({divisors, num}) => eq(getPrimeDivisors(num), divisors));
console.log('__getPrimeDivisors__: COMPLETED');
})();
(function () {
console.log('__getPalindromes__: START');
const palindroms = [];
const from = 999 * 999;
const to = 101 * 101;
for (let i = from; i > to; i -= 1) {
if (isPalindrome(i)) palindroms.push(i);
}
const palindroms2 = [];
for (let i = getMaxPalindrome(from); i > to; i = getPrevPalindrome(i)) {
palindroms2.push(i);
}
eq(palindroms, palindroms2, 'getPrevPalindrome err');
console.log('__getPalindromes__: COMPLETED');
})();
console.log('!!__SUCESS__!!');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment