Jump to content
BrainDen.com - Brain Teasers
  • 0
andrei

Palindromes by multiplication

Question

A palindrome is a number which reads the same backward or forward (e.g. 434, 87678, etc.). Could you prove that for any integer n (not divisible by 10) there is a palindrome divisible by n?

***

I've checked for all numbers up to 162, it's true:

81* 12345679= 999999999

172839506*162=27999999972

 

Is there any simple proof for any integer?

Share this post


Link to post
Share on other sites

2 answers to this question

  • 1

Yes, this can be proven.

The proof is relatively simple but it does require knowledge of Euler's theorem and Euler's totient function (See https://en.wikipedia.org/wiki/Euler's_theorem

The proof consists of 3 steps and  constructs an explicit palindrome for every number n that is not divisible by 10. This will be a possible solution, but by no means the smallest palindrome divisible by n. In fact the constructed palindrome get very large.

1) Find a solution for n=2k or n=5k for every integer k=1,2,3,....

Spoiler

We need a function r(n) that reverses the order of digits of the number n. Since we only allow numbers that are not divisible by 10 we can ignore the problem of zero's at the begin or end of a number and what it implies for the function r(n)   

Example: r(12345) = 54321

The number: r(2k)*10k+2k = r(2k)*2k*5k+2k = {r(2k)*5k+1}2k is divisible by 2k and is also a palindrome for any value of k

The number: r(5k)*10k+5k = r(5k)*2k*5k+5k = {r(5k)*2k+1}5k is divisible by 5k and is also a palindrome for any value of k

Example: n=26=64 would give r(64)*106+ 64 = 46*10000 + 64 = 46000064

This is significantly larger than the smallest palindrome 2112 that is a multiple of 64

We could reduce the solution a little bit by adjusting the power of 10, because for instance 4600064 is also a multiple of 64. Whether this can be done or not depends on the digital representation of the number 2k.

If we consider n=25=32 we get 2300032, but 230032 would not be divisible by 32.

2) Find a solution for any value of n that does not contain a factor 2 or 5

Spoiler

Here we need Euler's theorem, which states that for every pair of integers a and n that have no common factor, there is a number f(n) such that af(n) when divided by n has the remainder 1.

If anyone want to know more see the Wikipedia https://en.wikipedia.org/wiki/Euler's_theorem for a proof of the theorem. In order to compute f(n) you need to find all prime factors of the number n (See https://en.wikipedia.org/wiki/Euler's_totient_function).

If we use this for the case a=10 and we restrict to numbers not divisible by 2 and 5 we get that 10f(n)-1 is divisible by n and since this number is written as a sequence of f(n) digits of 9 this is a palindrome as well. 

Example: for n=7 we would have f(7)=6 and therefore 106-1=999999 is divisible by 7

So for any number n that is not divisible by 2 or 5 there is a palindrome that is a sequence of f(n) digits of 9 and that is divisible by n

This can be extended, because any multiple of f(n) would also be fine. We also have 1012-1=999999999999, 1018-1=999999999999999999, ... which are also divisible by 7.

Note that f(n) is guaranteed to work but is not necessarily the smallest power that is required. For instance for n=21 we get f(21)=12 and 1012-1 is divisible by 21, but so is the number 106-1.

3) Find a solution for any value of n that does contain a factor 2 or 5

Spoiler

The only numbers that are left to do are of the form n=2k*m or n=5k*m, where m does not contain a factor 2 or 5.

For this we need to construct a palindrome that combines both of the previous solutions with a small variation. It can generally be proven, but I will sketch here just the strategy to construct a possible solution for the palindrome by using the example of n=5k*7. 

For m=7 we have f(7)=6 and hence 106 has a remainder 1 when divided by 7. The same is true for 1012, 1018,1024,.... So a different (much bigger) palindrome that we could have constructed would have been the sum of m=7 such terms that each would have a remainder 1 and hence their sum would be divisible by 7 as well.

1 + 106 + 1012 + 1018+ 1024 + 1030+ 1036 = 1000001000001000001000001000001000001

If we now have a palindrome that is a multiple of 5and multiply it with the one above we get exactly what we want, because multiplying a short palindrome with a palindrome of the type above is again a palindrome.

k=1 gives a pre-factor 5 and has the palindrome 55 with the method above (of course 5 is already a palindrome and would also work), multiplying we get 55000055000055000055000055000055000055.

k   5k     palindrome

1   5        55                55000055000055000055000055000055000055

2   25      5225            5225005225005225005225005225005225005225

3   125    521125        521125521125521125521125521125521125521125

This works as long as the palindrome that is a multiple of m is shorter than 10f(m). For larger values of k we just need to increase the gaps in between the digits 1, which is easy enough because we could also have used: 

1 + 1012 + 1024 + 1036+ 1048 + 1060+ 1072 = 1000000000001000000000001000000000001000000000001000000000001000000000001

or 

1 + 1018 + 1036 + 1054+ 1072 + 1090+ 10108 = ......

1 + 1024 + 1048 + 1072+ 1096 + 10120+ 10144 = ......

and make the gap of digits 0 as large as we would like.

Since the final palindrome we obtain is formed by multiplying a short palindrome that is a multiple of 5k and a long palindrome that is a multiple of m the resulting palindrome is divisible by n.

The same approach work for al numbers of the form n=2k*m or n=5k*m, they just tend to get very large in this particular construction.

PS. If one would allow for zero's at the beginning of a digit representation of a number it can be extended to any number n.

 

Share this post


Link to post
Share on other sites
  • 0
On 12/2/2017 at 8:14 PM, andrei said:

A palindrome is a number which reads the same backward or forward (e.g. 434, 87678, etc.). Could you prove that for any integer n (not divisible by 10) there is a palindrome divisible by n?

***

I've checked for all numbers up to 162, it's true:

81* 12345679= 999999999

172839506*162=27999999972

 

Is there any simple proof for any integer?

Indeed, 81 is the first number that requires a long divisor its palindrome is very long. I didn't have the patience to go up to nine digits, as you did. I stopped when the quest for a palindrome reached 8 digits (It took alreadt 32 secs!). In a PC  I checked all numbers 1-1000 and, here are the numbers with >=8-digit result (not sulution!): 81, 162, 243, 324, 405, 486, 567, 648, 655, 729, 891, 972. There are no many and may there is a reason for that. For one thing they are multiples of 81, with 1-11 as multipliers ... So, it happens that 81 is the "mystery" number!
Now, it seems there's indeed a palindrome for every number. But how indeed can it be prooven (if it can)? 

On 12/2/2017 at 8:14 PM, andrei said:

 

(My comment has been posted twice - See previous one

Edited by Alkis
It has been posted twice!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

×