## On General Palindromic Numbers

```Which tetrahedral numbers, i.e., numbers of the form (b*(b+1)*(b+2))/6, are
also palindromic, meaning their digits read the same forwards and backwards?
For example, Patrick De Geest noted that b=336 gives the decimal palindrome
6378736.  Of course, if we don't restrict ourselves to decimal representations
we can find many such numbers.  The base-9 representation of the tetrahedral
number k(k+1)(k+2)/6 is palindromic for the following values of k (shown in
decimal):

k        k(k+1)(k+2)/6  (in base 9)
------    -----------------------------
1                         1
2                         4
3                        11
4                        22
12                       444
13                       555
120                    488884
588                  71066017
1093                 505555505
88573           505055555550505

Needless to say, the "tetrahedral" numbers are just the binomial coefficients
C(k,3).  The base-3 representations of C(k,3) are palindromic for the following
values of k

k           C(k,3)  (in base 3)
------    -----------------------------
1                         1
2                        11
3                       101
4                       202
6                      2002
12                    111111
14                    202202
39                 112121211
120              112222222211
392           201000222000102
496          1102111111112011

Similarly we have

C(1105,3)  =   1534114351   in base 8

C(521,3)  =   1122123212211   in base 4

C(1166,3)  =   6364334636   in base 7

C(82332,3)  =   12 5 9 13 18 18 13 9 5 12    in base 27

There is also a tetrahedral number C(k,3) whose base-B representation
is palindromic where both k and B are perfect squares (k=441, B=16).

Of course, every positive integer has a palindromic representation in
SOME base.  If we let f(n) denote the smallest base relative to which
n is palindromic, then clearly f(n) is no greater than n-1, because
every number n has the palindromic form '11' in the base (n-1).

Interestingly, for almost all integers n the value of f(n) is actually
quite small, as can be gathered from the table below:

n  f(n)       n  f(n)       n  f(n)       n  f(n)       n  f(n)
--- ----      --- ----      --- ----      --- ----      --- ----
1   2        21   2        41   5        61   6        81   8
2   3        22  10        42   4        62   5        82   3
3   2        23   3        43   6        63   2        83   5
4   3        24   5        44  10        64   7        84  11
5   2        25   4        45   2        65   2        85   2
6   5        26   3        46   4        66  10        86   6
7   2        27   2        47  46        67   5        87  28
8   3        28   3        48   7        68   3        88   5
9   2        29   4        49   6        69  22        89   8
10   3        30   9        50   7        70   9        90  14
11  10        31   2        51   2        71   7        91   3
12   5        32   7        52   3        72   5        92   6
13   3        33   2        53  52        73   2        93   2
14   6        34   4        54   8        74   6        94  46
15   2        35   6        55   4        75  14        95  18
16   3        36   5        56   3        76  18        96  11
17   2        37   6        57   5        77  10        97   8
18   5        38   4        58  28        78   5        98   5
19  18        39  12        59   4        79  78        99   2
20   3        40   3        60   9        80   3       100   3

The numbers for which  f(n) = n-1  are

3,   4,   6,  11,  19,  47,  53, 103, 137, 139, 149, 163,
167, 179, 223, 263, 269, 283, 293, 311, 317, 347, 359, 367,
389, 439, 491, 563, 569, 593, 607, 659, 739, 827, 853, 877
977, 983,...

These might be called "the non-palindromic numbers" because they
are the only numbers n that are NOT palindromic in ANY base from
2 to n-2.

Proposition:  If  f(n) = n-1  for n > 6 then n is a prime.

Proof:  If n=ab with a < (b-1) and b > 2 we have n=a(b-1)+a,
so n has the palindromic form 'aa' when expressed in the base (b-1).
This covers all composites greater than 6 except for squared primes,
but for squares we have a^2 = (a-1)^2 + 2(a-1) + 1, so every square
n > 4 has the palindromic form 121 in the base sqrt(n)-1.  Done.

The ratio of non-palindromic primes to all primes drops as the
range increases.  For example, of the 1229 primes less than 10000
we find that 218 are non-palindromic, which is about 1 out of
every 5.6.  Of the 9295 primes less than 100000 we find only 1199
are non-palindromic, which is only about 1 out of every 7.75.

At the opposite extreme, there are primes that are already
palindromic in the base 2, although these are even more scarce
than non-palindromic primes.  The first few are

3, 5, 7, 17, 31, 73, 107, 127, 257, 313, 443, 1193, 1453, ...

Returning to the function f(n) for general values of n (not restricted
to primes), it's clear that f(n), n=1,2,3,... fluctuates between 2 and
n-1, but I think the average value of f(n) for all n from 1 to infinity
is polynomial in n.  Specifically it appears that

f(n)_average    =    n^(1/c)

where c is a constant approximately equal to 2.68.  In other words,
I conjecture that
1    n    ln(k)
lim          --- SUM   -------    =    c
n->inf        n   k=1  ln(f(k))

but I don't know how to prove that this limit actually exists.

Anyway, it's also interesting to observe the values of f(n) when n
is a prime power.  For example, powers of 2 have the following values
of f(n):

n   f(n)     representation of n in the base f(n)
---  ----     ------------------------------------
2    3      2
4    3      1  1
8    3      2  2
16    3      1  2  1
32    7      4  4
64    7      1  2  1
128    7      2  4  2
256   15      1  2  1
512    7      1  3  3  1
1024    7      2  6  6  2
2048   31      2  4  2
4096    7      1  4  6  4  1
8192   15      2  6  6  2
16384   15      4 12 12  4

In general it appears that the min-base palindromic representation
of 2^m is a multiple of a binomial expansion, i.e.,

2^m  =  2^r [(2^s -1) + 1]^t

Obviously we have m = st + r.  The values of r,s,t for the first
several m are tabulated below:

m  r s t        m  r s t        m  r s t
-  - - -        -  - - -        -  - - -
1  1 2 0       11  1 5 2       21  1 5 4
2  0 2 1       12  0 3 4       22  2 5 4
3  1 2 1       13  1 4 3       23  2 7 3
4  0 2 2       14  2 4 3       24  0 6 4
5  2 3 1       15  0 5 3       25  0 5 5
6  0 3 2       16  0 4 4       26  1 5 5
7  1 3 2       17  1 4 4       27  3 6 4
8  0 4 2       18  3 5 3       28  0 7 4
9  0 3 3       19  1 6 3       29  1 7 4
10  1 3 3       20  0 4 5       30  0 5 6

In each case the triple (r,s,t) is such that s is minimized under
the constraint that

/  (2^r) * C(t,t/2)        if t is even
2^s - 1   > (
\  (2^r) * C(t-1,(t-1)/2)  if t is odd

The min-base palindromic representation of other prime powers also
tend to be multiples of binomial expansions, but not always.  For
example, the min-base representation of 3^7 is [3 19 3] in the
base 24.  Also, the min-base representation of 7^6 is [1 2 3 2 1]
in the base 18.  This raises the question of whether the min-base
representation for powers of 2 is always of the binomial form.
Can anyone supply a proof or counter-example?
```

Return to MathPages Main Menu