The first 20140 base ten positive integers are written in base 3. How many of these ternary representations are palindromes?
Bonus Question: How many ternary palindromes are there when the first 201400 base ten positive integers are written in base 3?
Decimal 20140 is 1000121221 in base 3. It has 10 digits, so 10-digit base-3 numbers up to this value will be eligible, as well as palindromes with fewer digits.
For palindromes with an odd number of digits, up to 9 digits, any base-3 number up to 22222 may be used as its LHS plus middle digit, which determines its RHS. The number of these is 3^5 - 1, as zero itself is not allowable.
Even length palindromes up to length 8 similarly consist of numbers up to and including 2222 for the LHS, thereby determining the RHS. That's another 3^4 -1 this time.
The limit for 10-digit base-3 palindromes for the LHS is 10001. It looks like we can forget about the preceding paragraph, as we'll incorporate those smaller even-length palindromes here: 3^4+1 - 1.
That makes 3^5 - 1 + 3^4+1 - 1 = 323 such palindromes.
Bonus:
Decimal 201400 is 101020021021 in base 3. It has 12 digits, so 12-digit base-3 numbers up to this value will be eligible, as well as all palindromes with fewer digits.
For palindromes with an odd number of digits, up to 11 digits, any base-3 number up to 222222 may be used as its LHS plus middle digit, which determines its RHS. The number of these is 3^6 - 1, as zero itself is not allowable.
Skipping over the unnecessary paragraph, we go right to:
The limit for 12-digit base-3 palindromes for the LHS is 101012. We get: 3^5+3^3+3+2 - 1.
The total is 3^5+3^3+3+2 - 1 + 3^6 - 1 = 1002.
|
|
Posted by Charlie
on 2014-08-04 13:09:37 |
solution
