This problem was given at https://www.codechef.com/COOK61.
Problem link: DUALPAL
Problem statement:
A number is called a Dual Palindrome if it's representation in bases B1 and B2 are both palindromes. e.g. Let B1 = 3, B2 = 4, then number 130 (in base 10) will be called a Dual Palindrome, as it is palindrome in base 3 (11211) as well as in base 4 (2002). However, it is not a Dual Palindrome for B1 = 3 and B2 = 5 as it's not a palindrome in base 5(1010). Given two integers B1 and B2, Chef wants to find Dual Palindromes less than 260. If there are more than 1000 Dual Palindromes, then output the first 1000 only (these numbers should be in base 10).
Input:
The fine line of the input contains an integer T denoting the number of test cases. Each test case consists of a single line containing two space separated integers: B1 and B2, respectively.
Output:
For each test case, output a list of space separated integers which are Dual Palindromes less than 2^60 for the input bases. If there are more than 1000 Dual Palindromes, then output the first 1000 only. The numbers should be printed in an ascending order.
Constraints:
1 ≤ T ≤ 5
2 ≤ B1 < B2 ≤ 16
Any idea how to approach the problem?
Given two integers B1 and B2, Chef wants to find Dual Palindromes less than 260.Maybe : Given two integers B1 and B2, Chef wants to find Dual Palindromes less than 2^60.I was looking at the post for like good 5min wondering why is that easy problem troubling everyone. Then I realised it's supposed to be 2^60 :D
Just thinking. The number of n-ary palindromes from 0 to 2^60 is roughly n^(1/2*log2^60/logn)=n^30log2/logn=2^30 ~ 10^9
We could generate all B2-nary palindromes till 2^60 and check if each one is also a B1-ary palindrome.
C++ can do as much as 10^8 operations per second. If we can implement palindrome generation and checking quick enough, we can potentially fit this calculation loop into 10 seconds.
Also note that the number of possible B1, B2 combinations is very small (about 100). We could try calculating all combinations on a local machine and try storing some of the results in an array. But I'm not sure if the solution size limitation (8000 bytes) allow us to do that.
There are roughly 2^30 binary palindromes, but for any base other than 2, the number of palindromes fall quickly, note that there are about 2^19 ~ 5*10^5 palindromes in base 3 (using your formula). So, generating all B2-ary palindromes till 2^60 and then check for those that are B1-ary palindromes too would be fast enough, and the number of operations is below 10^8
My formula shows that the number of palindromes for any n is almost the same. How many 10-ary palindromes are there from 0 to 2^60 ~ 10^18? about 10^9, right?
Oops, I think you are right. It should be 3^19 instead of 2^19, that is about 10^9 as you said. And your formula works very well, I wasn't looking close enough.