All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Palindromic number counting (Posted on 2006-06-22)
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?

 No Solution Yet Submitted by Sir Percivale Rating: 3.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 special values (spoiler for that part) | Comment 1 of 3

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        199999981000000000000000       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

 Search: Search body:
Forums (0)