Palindromes by multiplication

[andreis]

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 (in decimal representation) divisible by n?

***

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

81* 12345679= 999999999

162*172839506=27999999972

 

Is there any simple proof for any integer?

Edited February 12, 2017 by andreis

[Sensei]

You should explicitly specify which numeral system you have in mind, f.e. "examples only in decimal system are allowed".
If we have f.e. binary number %11011 it's palindrome in binary system,
while the same number but in decimal system, 27, is not anymore.

[andreis]

Let's be more specific, palindromicity is checked in decimal system. Corrected above.

[Function]

I think the first step is to generalize "palindrome" into a universal formula. I gave it a try; would someone mind to check it?

 

Every palindrome P can be written down by using the next 2 formulas, the first one being for palindromes consisting of an even number of digits, and the second one for palindromes consisting of an odd number of digits:

 

[math]\forall \left(x_i\in\left(\mathbb{N}\wedge\left[0,9\right]\right)\wedge x_1\neq 0; n \in \mathbb{N}_0\wedge 2 \mid n\right) \exists\ P=\sum_{i=1}^{\frac{n}{2}}{x_i\cdot\left(10^{i-1}+10^{n-i}\right)}[/math]

 

[math]\forall \left(x_i\in\left(\mathbb{N}\wedge\left[0,9\right]\right)\wedge x_1\neq 0; n \in \mathbb{N}_0\wedge 2\nmid n\right) \exists\ P=\sum_{i=1}^{\frac{n+1}{2}}{x_i\cdot\left(10^{i-1}+10^{n-i}\right)}[/math]

 

Additionally:

 

[math]\forall\ p\in\mathbb{N}_0\ \exists\ P:\frac{P}{p}\in\mathbb{N}[/math]

 

Combined:

 

[math]\forall \left(p\in\mathbb{N}_{0}; x_i\in\left(\mathbb{N}\wedge\left[0,9\right]\right)\wedge x_1\neq 0; n \in \mathbb{N}_0\wedge 2 \mid n\right) \exists\ \frac{P}{p}=\frac{1}{p}\cdot\sum_{i=1}^{\frac{n}{2}}{x_i\cdot\left(10^{i-1}+10^{n-i}\right)}\in\mathbb{N}[/math]

 

[math]\forall \left(p\in\mathbb{N}_{0}; x_i\in\left(\mathbb{N}\wedge\left[0,9\right]\right)\wedge x_1\neq 0; n \in \mathbb{N}_0\wedge 2\nmid n\right) \exists\ \frac{P}{p}=\frac{1}{p}\cdot\sum_{i=1}^{\frac{n+1}{2}}{x_i\cdot\left(10^{i-1}+10^{n-i}\right)}\in\mathbb{N}[/math]

 

If I didn't make an error, that should be the two theorems you want to prove.

 

Can someone check this?

Edited February 12, 2017 by Function

[Sensei]

Let's be more specific, palindromicity is checked in decimal system. Corrected above.

 

That's pity, in binary system when you multiply

[math](2^n+1)*(2^n-1)[/math]

You will always end up with the all digits 1, which is binary system palindrome.

[math](2^n-1)[/math] is also palindrome.

Edited February 12, 2017 by Sensei

[andreis]

The Python code returns the smallest palindrome P given an integer p (num in the code).

 

import sys
def is_palindrome(num):
if (num % 10 == 0):
return False;
r = 0;
while (r < num) :
r = 10 * r + num % 10;
num /= 10;
return (num == r) or (num == r / 10);
num = input("Enter a positive integer:");
k=0;
multiple=12;#initialisation: any non-palindrome
while (not is_palindrome(multiple)):
k+=1;
multiple=k*num;
print(str(num)+"*"+str(k)+"="+str(multiple));

Hi Function,

 

Your formula doesn't work for odd numbers. The digit in the middle will have the number (n+1)/2, and you will have a sum member 2*x_i*10^{(n-1)/2} instead of x_i*10^{(n-1)/2}.

 

I made a similar decomposition, but could not get any conclusion from it.

Edited February 12, 2017 by andreis

[Sensei]

The Python code returns the smallest palindrome P given an integer p (num in the code).

 

import sys

def is_palindrome(num):

if (num % 10 == 0):

return False;

r = 0;

while (r < num) :

r = 10 * r + num % 10;

num /= 10;

return (num == r) or (num == r / 10);

I converted this function from Python to .NET Framework C++, and tried it in my code..

 

private: System::Boolean isPalindrome( int num )
{
   if (num % 10 == 0) return false;
   int r = 0;
   while (r < num)
   {
      r = 10 * r + num % 10;
      num /= 10;
   }
   return (num == r) || (num == r / 10);
}

And it's returning true for num between 1...9

but it's returning false for num 0.

 

In this article

https://en.wikipedia.org/wiki/Palindromic_number

the all numbers from 0...9 (decimal) are considered as palindromic numbers

 

I attached entire source code (.NET Framework C++) with compiled .exe

Palindrome.zip

Edited February 12, 2017 by Sensei

[imatfaal]

If you allow leading zeros then you can do away with the not divisible by ten proviso

[andreis]

Hm, still no solution. It's supposed to be a school problem.

[Function]

Hm, still no solution. It's supposed to be a school problem.

 

What kind of frickin' school do/did you attend

[uncool]

It's true for any positive integer. More specifically, every integer is a factor of some number of the form 10^m - 10^n, which is automatically a palindrome if you allow leading 0s. Proof isn't hard through the Pigeonhole Principle.

[imatfaal]

It's true for any positive integer. More specifically, every integer is a factor of some number of the form 10^m - 10^n, which is automatically a palindrome if you allow leading 0s. Proof isn't hard through the Pigeonhole Principle.

 

can you elaborate please? no need to get too technical - but that is kinda "and then a miracle occurs" without a bit more explanation.

[uncool]

can you elaborate please? no need to get too technical - but that is kinda "and then a miracle occurs" without a bit more explanation.

There are infinitely many numbers of the form 10^m, but only finitely many possible remainders/equivalence classes modulo k, so by Pigeonhole Principle, at least two (in fact, infinitely many) distinct numbers of the form 10^m must have the same remainder/be in the same equivalence class. Then their difference is divisible by k.

 

This is a palindrome because it's of the form 99.....9900...00, which can be turned into 00...0099...9900..00 with exactly as many leading as trailing 0s.

 

For example: 14. The remainders modulo 14 of the first few powers of 10 are: 1, 10, 2, 6, 4, 12, 8, 10, 2, 6, 4, ...

 

So 10^1 and 10^7 have the same remainders, so 10^7 - 10^1 is divisible by 7. 10^7 - 10^1 = 9999990 = 09999990, which is a palindrome with that leading 0.

Edited February 15, 2017 by uncool

[imatfaal]

There are infinitely many numbers of the form 10^m, but only finitely many possible remainders/equivalence classes modulo k, so by Pigeonhole Principle, at least two (in fact, infinitely many) distinct numbers of the form 10^m must have the same remainder/be in the same equivalence class. Then their difference is divisible by k.

 

This is a palindrome because it's of the form 99.....9900...00, which can be turned into 00...0099...9900..00 with exactly as many leading as trailing 0s.

 

For example: 14. The remainders modulo 14 of the first few powers of 10 are: 1, 10, 2, 6, 4, 12, 8, 10, 2, 6, 4, ...

 

So 10^1 and 10^7 have the same remainders, so 10^7 - 10^1 is divisible by 7. 10^7 - 10^1 = 9999990 = 09999990, which is a palindrome with that leading 0.

 

Brilliant - thanks

[Sensei]

If you allow leading zeros then you can do away with the not divisible by ten proviso

Well, writing my post, I was not thinking about allowing leading zeros at all. But 0 alone is palindrome as well. His code was excluding 0 from palindromes.

 

See the list of numbers on website

https://en.wikipedia.org/wiki/Palindromic_number

Quote

"The first 30 palindromic numbers (in decimal) are:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202,"

 

If leading zeros would be allowed, there would be also 10 (010), 20 (020), and so on, on the list..

 

So, isPalindrome() function code, used by OP, should looks like:

if ( ( num != 0 ) && ( num % 10 == 0 ) ) : return False;

instead of

if (num % 10 == 0): return False;

to exclude leading zeros, but treating 0 as palindrome.

 

New version of project:

Palindrome.zip

Edited February 18, 2017 by Sensei

[imatfaal]

That of course is true Sensei - I had forgotten that it was I who had introduced the idea of the the leading zero. So do we presume there is still a "school level" answer to the initial OP?

[Sensei]

That of course is true Sensei - I had forgotten that it was I who had introduced the idea of the the leading zero.

 

I found that his Python code fails with f.e. num=30..

 

My .NET Framework version of it, is showing "30*1=44".

after using 64 bit integers I got:

30 * 143165578 = 4294967340

 

2^32 = 4294967296

4294967340 - 4294967296 = 44...

The most significant bit set, is truncated, because of overflow of 32 bit integer..

 

After using long long everywhere in code ends up in infinite loop (2^64 numbers to check).

Could you prove that for any integer n (not divisible by 10) there is a palindrome (in decimal representation) divisible by n?

 

Divisibility test for 11 is the answer you're searching for?

 

According to

https://en.wikipedia.org/wiki/Palindromic_prime

"Except for 11, all palindromic primes have an odd number of digits, because the divisibility test for 11 tells us that every palindromic number with an even number of digits is a multiple of 11."

 

https://www.google.com/?#q=palindromic+number+divisible+by+11

 

Modified version of project. Instead of incrementing k by 1, it increments by 11.

Palindrome.zip

Edited February 20, 2017 by Sensei

[Sriman Dutta]

The OP wants to prove that for every palindrome there exists an integer n which divides the palindrome exactly. In other words, we need to prove that all palindromes are composite numbers.

[John Cuthber]

The OP wants to prove that for every palindrome there exists an integer n which divides the palindrome exactly. In other words, we need to prove that all palindromes are composite numbers.

No we don't.

11 is a palindrome, but not composite.

You are making the assumption that because all oranges are fruit , all fruit are oranges.

[Sriman Dutta]

Then the OP's question is therefore invalid, I think.

[John Cuthber]

Then the OP's question is therefore invalid, I think.

Nope,

It's possible that you can always find a multiple of an integer which is a palindrome. That palindrome will (obviously) be composite.

But that's not the same as saying that all palindromes are composite.

All it requires is that some palindromes are composite.

[Sriman Dutta]

I see the difference. Thanks John.

[Commander]

There is a formula to find the n^th Palindrome of Natural Numbers say to the Base 10.

 

But that n^th Palindrome need not be divisible by n.

 

If we can leave out all the Prime Palindromes occurring in between and find the n^th Palindrome which is a composite number and see whether that number is divisible by n & if not find a composite prime which has n as a factor !