Six of the factors of 1221 are palindromes: {1,3,11,33,111,1221} but two are not: {37,407}
(A) What number under one million has the most palindrome factors?
Some numbers have only palindromes as factors. Examples include 88: {1,2,4,8,11,22,44,88} and any palindromic prime
(B) Find the smallest number with at least as many palindrome factors as part (A) but having only palindrome factors.
When I first tried this problem I used a brute force method which worked - slowly.
I made a new algorithm in which I made a list of palindromes up to a maximum size (N), threw out the ones who had any factors that were not themselves palindromes.
I made another function that takes a list of integers as input and then outputs a list of the product of i and j, for every combination of the elements in the input taken two at a time. But before outputting the result, any non-palindromes are thrown out and any number larger than an Upper Limit is thrown out.
This function is then run using the first list as the input.
The same function is then rerun several times using the output as the new input, until the number of elements in the list stops increasing. At this point the list contains "almost" every number less than Upper Limit which has only palindromes as factors. Next, loop through this list counting the number of factors of each element.
Running this with N = 1,000,000 and Upper Limit = 100,000,000,000 I found the same results as with the brute force method, but it ran much faster.
I say "almost" because I started with the first list only going up to N; and N might be much less than Upper Limit. So there might be suitable numbers larger than N that make a more robust final list to choose from.
|
Posted by Larry
on 2022-03-15 09:45:03 |