Mathematics desk
< January 11	<< Dec \| January \| Feb >>	January 13 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 12

Computing whether a number N is a palindrome in any bases < N-1.

For a number N, I'd like to calculate if it is a palindrome in any base < N-1. N will always be a palindrome in base N-1, even numbers will be a palindrome in base 2N-2 and no numbers will be palindromes between 2N-2 and N-1. So for odd numbers is there any way to do it other than simply calculating the value in all bases up to 2N-1? (For example, 11 in base 10 isn't a palindrome for any number other than in base 10, but 13 in base 10 is a palindrome in base 3) (I went back and forth as to whether this belonged here or the Computer Ref Desk)Naraht (talk) 14:39, 12 January 2016 (UTC)[reply]

This is covered in our article at Strictly non-palindromic number - see the "properties" section, which gives a justification why all composite numbers over 6 are palindromic. It doesn't cover the case of primes where p>6 though. The OEIS page for the non-palindromic number sequence has some additional useful comments - since no prime is palindromic in base b>sqrt(p), you only need to examine bases up to sqrt(p) for prime numbers.

In summary: 5 is a palindromic number, and then all composite numbers (n=mp) over 6 are palindromic (in base m-1 if odd, or (n/2)-1 if even). Prime numbers must be tested separately, but only up to base sqrt(p). (also, your "2N-2" should be "N/2-1", since 2N-2>N, for all positive integers, so they are all trivially palindromic in base 2N-2). MChesterMC (talk) 16:41, 12 January 2016 (UTC)[reply]

Thank you! Strictly non-palindromic number may need to be tweeked, I'm uncomfortable with the phrase "The Reader can", which reads more like textbook than encyclopedia. And the OEIS info is even better....Naraht (talk) 17:17, 12 January 2016 (UTC)[reply]

Why do transcription errors yield a difference of a multiple of nine?

I have heard that a transcription error will yield a difference of a multiple of nine. For example, if you enter "63" by mistake, when you should have entered "36", the difference in the two numbers is 27 (a multiple of 9). That was a simple example. It also works for a more "complicated" example. So, similarly, if you enter "4215" by mistake, when you should have entered "2451", the difference in the two numbers is 1764 (again, a multiple of 9). So, does this work in every case? And why does this work at all? In other words, what does the value "9" have to do with anything? Thanks. Joseph A. Spadaro (talk) 17:11, 12 January 2016 (UTC)[reply]

Change it to just two digits being switched, and call them X in position Y (counting from the right) and P in position Q. call A the original number, B the number with the digits reversed and Z the number with both X and P replaced with zeros. A = Z+ X*10^Y + P*10^Q. B= P*10^Y+ X*10^Q. So A-B = X* (10^Y-10^Q) - P*(10^Q-10^Y). Since for any two numbers C&D 10^C-10^D is divisible by nine (the number looks like (+ or -)99999..999000...000) so A-B = X*(number divisible by 9)-y*(number divisible by 9), A-B is divisible by 9. If the number has more than two digits scrambled, this can simply be done by interchanging two numbers at a time and since every change causes a difference divisible by 9, the ultimate result is as well.Naraht (talk) 18:45, 12 January 2016 (UTC)[reply]

For a deeper explanation, read up on modular arithmetic. The point here is that 10≡1(mod 9), which implies that for any natural number n, you also have 10ⁿ≡1(mod 9).

So if you take any decimal representation of a natural number, you can get something that's the same mod 9 if you just add up the digits. Because mod 9, a digit in any place is just worth that digit times 1.

If you have a transposition error, it doesn't change the sum of the digits. So mod 9, the two numbers represented are the same. --Trovatore (talk) 18:59, 12 January 2016 (UTC)[reply]

Thanks. No offense, but I did not understand a word of the above two explanations. But it did make me think of another question. Would this also work for digits to the right of the decimal point? For example, 3.00129 versus 3.00912, etc.? And how about with digits both before and after the decimal point? For example, 7.21 versus 2.17 or such? My quick calculations tell me that those do not seem to work. Why not? Or, in such cases, is it going to be a multiple of one-ninth (1/9) as opposed to 9? Thanks. Joseph A. Spadaro (talk) 22:47, 12 January 2016 (UTC)[reply]

It will be a multiple of 9 of the "base unit". If your numbers are 3.00129 etc., your base unit is 0.00001, so the difference between the numbers will always be a multiple of 0.00009. In your first example, the difference is 0.00783 = 87 * 0.00009. In the second example, the difference is 5.04 = 56 * 0.09.

As for why this always works - I'm afraid you must have a good understanding of modular arithmetic to get it. So as suggested by Trovatore, read up on it. It's a fascinating topic. -- Meni Rosenfeld (talk) 00:26, 13 January 2016 (UTC)[reply]

Let me try another explanation of the original question. You say that a transposition error has been made. That means that instead of "ab" someone typed "ba". (That's positional notation, of course, not multiplication.) Your question is why does ab minus ba always equal a multiple of 9. Now, can we agree that ab = 10a+b, and ba = 10b+a. Thus, ab - ba = 9a-9b which is obviously a multiple of 9. If the number has more digits, the math is slightly more complicated but the result is the same. HOpe that helps. Newyorkbrad (talk) 22:58, 12 January 2016 (UTC)[reply]

@Newyorkbrad: Thanks. That's starting to make sense. Starting to sink in. Let me digest it for a bit. Thanks. Joseph A. Spadaro (talk) 02:27, 13 January 2016 (UTC)[reply]

@Newyorkbrad: That makes perfect sense. Yes, I get it now. And to add to what you had to say: 9a - 9b = 9 (a - b). So, in the case of two digits at least, the multiple of 9 is 9 times (a - b). Thanks. Joseph A. Spadaro (talk) 17:20, 16 January 2016 (UTC)[reply]

And a transposition of non-adjacent digits can be 'translated' to a sequence of adjacent transpositions. —Tamfang (talk) 03:01, 13 January 2016 (UTC)[reply]

See Casting out nines. Bubba73 ^{You talkin' to me?} 04:35, 13 January 2016 (UTC)[reply]

Thanks, all. Joseph A. Spadaro (talk) 17:20, 16 January 2016 (UTC)[reply]

Resolved