Strictly non-palindromic number

A representation of a number n in base b, where b > 1 and n > 0, is a sequence of k+1 digits a_i (0 ≤ i ≤ k) such that

${\displaystyle n=\sum _{i=0}^{k}a_{i}b^{i}}$

and 0 ≤ a_i < b for all i and a_k ≠ 0.

Such a representation is defined as palindromic if a_i = a_k−i for all i.

A number n is defined as strictly non-palindromic if the representation of n is not palindromic any base b where 2 ≤ b ≤ n-2.

The sequence of strictly non-palindromic numbers (sequence A016038 in the OEIS) starts:

0, 1, 2, 3, 4, 6, 11, 19, 47, 53, 79, 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, 997, ...

For example, the number 19 written in base 2 through 17 is:

b	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
19 in base b	10011	201	103	34	31	25	23	21	19	18	17	16	15	14	13	12

None of these is a palindrome, so 19 is a strictly non-palindromic number.

The reason for the upper limit of n − 2 on the base is that all numbers are trivially palindromic in large bases:

• In base b = n − 1, n ≥ 3 is written "11".
• In any base b > n, n is a single digit, so is palindromic in all such bases.

Thus it can be seen that the upper limit of n − 2 is necessary to obtain a mathematically "interesting" definition.

For n < 4 the range of bases is empty, so these numbers are strictly non-palindromic in a trivial way.

All strictly non-palindromic numbers larger than 6 are prime. One can prove that a composite n > 6 cannot be strictly non-palindromic as follows. For each such n a base is shown to exist in which n is palindromic.

1. If n is even and greater than 6, then n is written "22" (a palindrome) in base n/2 − 1. (Note that if n less than or equal to 6, the base n/2 − 1 would be less than 3, so the digit "2" could not occur in the representation of n.)
2. If n is odd and greater than 1, write n = p · m, where p is the smallest prime factor of n. Clearly p ≤ m (since n is composite).
   1. If p = m (that is, n = p²), there are two cases:
      1. If p = 3, then n = 9 is written "1001" (a palindrome) in base 2.
      2. If p > 3, then n is written "121" (a palindrome) in base p − 1.
   2. p cannot equal m - 1 because both p and m are odd, so p < m − 1. Then n can be written as the two-digit number pp in base m − 1.

• Sequence A016038 from the On-Line Encyclopedia of Integer Sequences