🚀 go-pugleaf

On Fri, 10 Jan 1997 02:05:41 +0100, Patrick De Geest
<Patrick.DeGeest@ping.be> wrote:
>I'm always looking for all sorts of information about palindromic
>numbers...
>
>Record_nr(?) for palindromic tetrahedrals; Function = (b*(b+1)*(b+2))/6
>
>        Function( 336 ) =
>        6.378.736 [length 7]
>
>If you happen to know of similar basenumbers that are larger than the
>ones above, please let me know your source.

If you don't restrict yourself to decimal representations you 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

Of course 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?
  ____________________________________________________________
 |              /*\                                           |
 |   MathPages /   \     http://www.seanet.com/~ksbrown/      |
 |____________/_____\_________________________________________|