Strictly non-palindromic number

A strictly non-palindromic number is an integer n that is not palindromic in any numeral system with a base b in the range 2 ≤ b ≤ n − 2. For example, the number six is written as 110 in base 2, 20 in base 3 and 12 in base 4, none of which is a palindrome—so 6 is strictly non-palindromic.

For another example, the number 167 written in base b (2 ≤ b ≤ 165) is:

b	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	...	162	163	164	165
167 will be written as:	10100111	20012	2213	1132	435	326	247	205	167	142	11B	CB	BD	B2	A7	9E	95	8F	87	7K	7D	76	6N	6H	...	15	14	13	12

and none of which is a palindrome, so 167 is also a strictly non-palindromic number.

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, ...

To test whether a number n is strictly non-palindromic, it must be verified that n is non-palindromic in all bases up to n − 2. The reasons for this upper limit are:

• any n ≥ 2 is written 11 in base n − 1, so n is palindromic in base n − 1;
• any n ≥ 2 is written 10 in base n, so any n is non-palindromic in base n;
• any n ≥ 1 is a single-digit number in any base b > n, so any n is palindromic in all such bases.

For example, 167 will be written as: (if b > 165)

b	166	167	>167
167 will be written as:	11	10	a single-digit number

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.

Properties

All strictly non-palindromic numbers beyond 6 are prime. To see why composite n > 6 cannot be strictly non-palindromic, for each such n a base b can be shown to exist where n is palindromic.

• If n is even, then n is written 22 (a palindrome) in base b = n/2 − 1. (Since n > 6, so n/2 − 1 > 2)

Otherwise n is odd. Write n = p · m, where p is the smallest prime factor of n. Then clearly p ≤ m. (Since n is composite)

• If p = m = 3, then n = 9 is written 1001 (a palindrome) in base b = 2.
• If p = m > 3, then n is written 121 (a palindrome) in base b = p − 1. (Since p > 3, so p − 1 > 2)

Otherwise p < m − 1. The case p = m − 1 cannot occur because both p and m are odd.

• Then n is written pp (the two-digit number with each digit equal to p, a palindrome) in base b = m − 1. (Since p < m − 1)

The reader can easily verify that in each case (1) the base b is in the range 2 ≤ b ≤ n − 2, and (2) the digits a_i of each palindrome are in the range 0 ≤ a_i < b, given that n > 6. These conditions may fail if n ≤ 6, which explains why the non-prime numbers 1, 4 and 6 are strictly non-palindromic nevertheless.

Therefore, all strictly non-palindromic n > 6 are prime.

References

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