I want to calculate how many numbers are palindrome in large interval data say 10^15
My simple code (python) snippet is:
def count_palindromes(start, end):
count = 0
for i in range(start, end + 1):
if str(i) == str(i)[::-1]:
count += 1
return count
start = 1000 #some initial number
end = 10000000000000 #some other large number
if __name__ == "__main__":
print count_palindromes(start, end)
Its a simple program which checks each number one by one. Its vary time consuming and takes a lot of computer resources.
Is there any other method/technique by which we can count Palindrome numbers? Any Algorithm to use for this?
I want to minimize time taken in producing the output.
When you want to count the numbers having some given property between two limits, it is often useful to solve the somewhat simpler problem
How many numbers with the given property are there between
0andn?
Keeping one limit fixed can make the problem significantly simpler to tackle. When the simpler problem is solved, you can get the solution to the original problem with a simple subtraction:
countBetween(a,b) = countTo(b) - countTo(a)
or countTo(b ± 1) - countTo(a ± 1), depending on whether the limit is included in countTo and which limits shall be included in countBetween.
If negative limits can occur (not for palindromes, I presume), countTo(n) should be <= 0 for negative n (one can regard the function as an integral with respect to the counting measure).
So let us determine
palindromes_below(n) = #{ k : 0 <= k < n, k is a palindrome }
We get more uniform formulae for the first part if we pretend that 0 is not a palindrome, so for the first part, we do that.
Part 1: How many palindromes with a given number d of digits are there?
The first digit cannot be 0, otherwise it's unrestricted, hence there are 9 possible choices (b-1 for palindromes in an arbitrary base b).
The last digit is equal to the first by the fact that it shall be a palindrome.
The second digit - if d >= 3 - can be chosen arbitrarily and independently from the first. That also determines the penultimate digit.
If d >= 5, one can also freely choose the third digit, and so on.
A moment's thought shows that for d = 2*k + 1 or d = 2*k + 2, there are k digits that can be chosen without restriction, and one digit (the first) that is subject to the restriction that it be non-zero. So there are
9 * 10**k
d-digit palindromes then ((b-1) * b**k for base b).
That's a nice and simple formula. From that, using the formula for a geometric sum, we can easily obtain the number of palindromes smaller than 10n (that is, with at most n digits):
if n is even, the number is
n/2-1 n/2-1
2 * ∑ 9*10**k = 18 * ∑ 10**k = 18 * (10**(n/2) - 1) / (10 - 1) = 2 * (10**(n/2) - 1)
k=0 k=0
if n is odd, the number is
2 * (10**((n-1)/2) - 1) + 9 * 10**((n-1)/2) = 11 * (10**((n-1)/2) - 2
(for general base b, the numbers are 2 * (b**(n/2) - 1) resp. (b+1) * b**((n-1)/2) - 2).
That's not quite as uniform anymore, but still simple enough:
def palindromes_up_to_n_digits(n):
if n < 1:
return 0
if n % 2 == 0:
return 2*10**(n//2) - 2
else:
return 11*10**(n//2) - 2
(remember, we don't count 0 yet).
Now for the remaining part. Given n > 0 with k digits, the palindromes < n are either
k digits, there are palindromes_up_to_n_digits(k-1) of them, ork digits that are smaller than n.So it remains to count the latter.
Part 2:
Letm = (k-1)//2 and
d[1] d[2] ... d[m] d[m+1] ... d[k]
the decimal representation of n (the whole thing works with the same principle for other bases, but I don't explicitly mention that in the following), so
k
n = ∑ d[j]*10**(k-j)
j=1
For each 1 <= c[1] < d[1], we can choose the m digits c[2], ..., c[m+1] freely to obtain a palindrome
p = c[1] c[2] ... c[m+1] {c[m+1]} c[m] ... c[2] c[1]
(the digit c[m+1] appears once for odd k and twice for even k). Now,
c[1]*(10**(k-1) + 1) <= p < (c[1] + 1)*10**(k-1) <= d[1]*10**(k-1) <= n,
so all these 10**m palindromes (for a given choice of c[1]!) are smaller than n.
Thus there are (d[1] - 1) * 10**m k-digit palindromes whose first digit is smaller than the first digit of n.
Now let us consider the k-digit palindromes with first digit d[1] that are smaller than n.
If k == 2, there is one if d[1] < d[2] and none otherwise. If k >= 3, for each 0 <= c[2] < d[2], we can freely choose the m-1 digits c[3] ... c[m+1] to obtain a palindrome
p = d[1] c[2] c[3] ... c[m] c[m+1] {c[m+1]} c[m] ... c[3] c[2] d[1]
We see p < n:
d[1]*(10**(k-1) + 1) + c[2]*(10**(k-2) + 10)
<= p < d[1]*(10**(k-1) + 1) + (c[2] + 1)*(10**(k-2) + 10)
<= d[1]*(10**(k-1) + 1) + d[2]*(10**(k-2) + 10) <= n
(assuming k > 3, for k == 3 replace 10**(k-2) + 10 with 10).
So that makes d[2]*10**(m-1) k-digit palindromes with first digit d[1] and second digit smaller than d[2].
Continuing, for 1 <= r <= m, there are
d[m+1]*10**(m-r)
k-digit palindromes whose first r digits are d[1] ... d[r] and whose r+1st digit is smaller than d[r+1].
Summing up, there are
(d[1]-1])*10**m + d[2]*10**(m-1) + ... + d[m]*10 + d[m+1]
k-digit palindromes that have one of the first m+1 digits smaller than the corresponding digit of n and all preceding digits equal to the corresponding digit of n. Obviously, these are all smaller than n.
There is one k-digit palindrome p whose first m+1 digits are d[1] .. d[m+1], we must count that too if p < n.
So, wrapping up, and now incorporating 0 too, we get
def palindromes_below(n):
if n < 1:
return 0
if n < 10:
return n # 0, 1, ..., n-1
# General case
dec = str(n)
digits = len(dec)
count = palindromes_up_to_n_digits(digits-1) + 1 # + 1 for 0
half_length = (digits-1) // 2
front_part = dec[0:half_length + 1]
count += int(front_part) - 10**half_length
i, j = half_length, half_length+1
if digits % 2 == 1:
i -= 1
while i >= 0 and dec[i] == dec[j]:
i -= 1
j += 1
if i >= 0 and dec[i] < dec[j]:
count += 1
return count
Since the limits are both to be included in the count for the given problem (unless the OP misunderstood), we then have
def count_palindromes(start, end):
return palindromes_below(end+1) - palindromes_below(start)
for a fast solution:
>>> bench(10**100,10**101-1)
900000000000000000000000000000000000000000000000000 palindromes between
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
and
99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
in 0.000186920166016 seconds