Velocity Reviews > Test if an integer is a palindrome in c language

# Test if an integer is a palindrome in c language

Dik T. Winter
Guest
Posts: n/a

 08-16-2007
In article <(E-Mail Removed) om> user923005 <(E-Mail Removed)> writes:
....
> It might be interesting to try every base from 2 to 36.
> Given that condition, what percentage of integers are palindromes?

It decreases fast when the numbers increase. A random number with
k base-b digits is a palindrome with probability:
1/(b ** (k/2))
and as k is floor(b_log(n) + 1), we see that it decreases fast for
all b. (To get the probablility that a number is *not* a palindrome
we multiply all factors (1 - 1/(b ** (k/2))).)

Much more interesting is that 41 is the smallest number that is not
a palindrome for any of those bases.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Ben Bacarisse
Guest
Posts: n/a

 08-16-2007
"Dik T. Winter" <(E-Mail Removed)> writes:

> In article <(E-Mail Removed) om> user923005 <(E-Mail Removed)> writes:
> ...
> > It might be interesting to try every base from 2 to 36.
> > Given that condition, what percentage of integers are palindromes?

>
> It decreases fast when the numbers increase. A random number with
> k base-b digits is a palindrome with probability:
> 1/(b ** (k/2))
> and as k is floor(b_log(n) + 1), we see that it decreases fast for
> all b. (To get the probablility that a number is *not* a palindrome
> we multiply all factors (1 - 1/(b ** (k/2))).)
>
> Much more interesting is that 41 is the smallest number that is not
> a palindrome for any of those bases.

This got me interested... By observing that

(1) all numbers, n, are palindromic in base n - 1 (n is written "11")
(2) none are palindromic in base n (n is written "10")
(3) all are palindromic in bases b > n (n is the single digit "n")

we can arrive at the idea of a number being "non-palindromic"[1] in a
more general way: a number n is non-palindromic if it is a palindrome
only when written in the "trivial" bases b >= n-1.

The first few are 3, 4, 6, 11, 19, 47 and 53.[2] They seem to be common
(though not as common as primes).

There are also numbers that are multi-palindromic (being palindromic
in more that their fair share of bases). For example, 21 (in bases 2,
4, and 6), 36, (in 5, 8, 11 and 17) and 60 (9, 11, 14, 19 and 29).

You might also be interested to know (I did not until yesterday) that
some bases provoke palindromism much more than others. In a quick
count for the numbers between 3 100000, it turns out that 47 makes
more of these numbers palindromic than any other base. There is a
little cluster around 47:

B Number of numbers in 3..99999 that are palindromic in base B
47 2125
46 2116
48 2081
49 2038

This "most palindromic base" creeps upwards (very slowly) as more
numbers are considered, but the presence of a cluster made me think it
might be worth plotting. Think it was. The curve is curious and
unexpected (at least to me).[3]

Cross-posted (with followups set) to comp-programming. I hope that is
the right thing to do. We are certainly off topic now!

[1] An invented term, as far as I know.
[2] One must decide about 0, 1 and 2 simply by definition, I think.
[3] http://www.bsb.me.uk/palindrome/

--
Ben.