On General Palindromic Numbers

Patrick De Geest asked for tetrahedral numbers, i.e., numbers of the
form (b*(b+1)*(b+2))/6, that are also palindromic (digits read the
same forwards and backwards).  He 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.  For example, 
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
Сайт управляется системой uCoz