Suppose you want to know how many palindromes are in the set of integers from 1 to N. Can you provide a formula for this? Otherwise, can you give an algorithm, as efficient as possible, to find the answer? And, are there special values of N for which there is a simple formula?
If n = 10^k the following formula can be used:
Sigma{i=1 to [log k]} (9 * 10^[(i-1)/2])
where log is the common log and [] indicate the floor (integer) function.
A table of this is:
10 9
100 18
1000 108
10000 198
100000 1098
1000000 1998
10000000 10998
100000000 19998
1000000000 109998
10000000000 199998
100000000000 1099998
1000000000000 1999998
10000000000000 10999998
100000000000000 19999998
1000000000000000 109999998
produced by:
DEFDBL A-Z
FOR pwr = 1 TO 15
n = 10 ^ pwr
t = 0
logn = LOG(n) / LOG(10)
FOR i = 1 TO INT(logn)
t = t + 9 * 10 ^ (INT((i - 1) / 2))
NEXT
PRINT USING "################"; n; t
NEXT
From the table, it looks like an appropriate formula
for even k is:
2 * 10^(k/2) - 2
or, 2 * sqrt(n) - 2
for odd k is:
1.1 * 10^((k+1)/2) - 2
or, (11/10) * sqrt(10*n) - 2
Other numbers get more complicated. You can do the above for the next lower power of 10, but then you need to add in the palindromes that have the same number of digits as n. You can account for those that start with a digit lower than the first digit of n by counting (n-1) times the number of palindromes of two fewer digits, but this time including those with leading (and trailing) zeros. But to account for palindromes beginning with the same digit as n, you'd have to take into consideration whether the last digit of n was greater than or equal to the first, and also for subpalindromes within the number under consideration.
|
|
Posted by Charlie
on 2006-06-22 09:41:13 |
special values (spoiler for that part)
