Strictly non-palindromic number

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Besides, the number 167 written in base b 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 ... 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 ... 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 OEIS) starts:

1, 2, 3, 4, 6, 11, 19, 47, 53, 79, 103, 137, 139, 149, 163, 167, 179, 223, 263, 269, 283, 293, …

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.

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

For example, 167 will be written as:

b 1 166 167 168+
167 will be written as: 111111111111......111111111111 (167 1's) 11 10 a single-digit number

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

Properties[edit]

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.

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

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

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.

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 ai of each palindrome are in the range 0 ≤ ai < 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[edit]