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