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

Home > Numbers
Palindromic number counting (Posted on 2006-06-22) Difficulty: 3 of 5
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        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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information