The Hidden Square - 24/04/2013

[showmyiq]

OK, I think I finally crack it!

\begin{equation}
2^m + 1 = 5^n
\end{equation}
I have applied my Bool-Fu in order to crack this problem.

Let’s analyze the left side of this equation represented in binary.

\begin{equation}
2^m + 1 = 1\underbrace {0...0}_m + 1 = 1\underbrace {0...0}_{m-1}1
\end{equation}
OK, so we need such 5^m that will be equal to some 100..0001 with variable count of the zeros.

\begin{equation}
1\underbrace {0...0}_{m-1}1 = binary(5^n) \\
1\underbrace {0...0}_{m-1}1 = binary(5)*binary(5^{n-1})\\
1\underbrace {0...0}_{m-1}1 = 101*binary(5^{n-1})\\
\end{equation}
If n=1 then our side right side is 5*1 = 5 and this fulfill the pattern applied from the left side. So n=1 is one possible solution. Now the interesting part – what if n>1 ?
We can divide the numbers in some subsets. I was thinking to attack the problem like that – dividing the set of all natural numbers in binary format into several subsets – subset of digits ending with 0000, subset of digits ending with 0001, … , subset of digits ending with 1111. If we take all the sets manually and multiply them with 101 (our 5), and if we receive unfitting results to the pattern on the left side of the equation – then Eureka! – there are no other solutions!

So I made this tiny script using C# and I happily awaited the results:

using System;

class Program
{
static void Main()
{
long temp = 0L;
for (long i = 1; i < 40000000; i++)
{
temp = i * 5;
Console.WriteLine("i={0}",i);
Console.WriteLine("Binary I = {0}",Convert.ToString(i, 2));
Console.WriteLine("Binary T = {0}",Convert.ToString(temp, 2));
}
}
}

Then I outputted the results to a text file (believe it or not – this script generated me 10 MB results per second). I used this regular expression in order to find the matching results: T = [1][0]{R}[1][^0+^1], where R is the count of the zeros in the left side of the equation.
Ok, first came the bad news. Such numbers applied and unfortunately I was not able to crack the problem like that. But there were some good news too. A pattern emerged! If a solution exists – it should ends with *1101 represented in binary format. Let me show you the good results:

[1][0]{1}[1][^0+^1], for R=1
i=1
Binary I = 1
Binary T = 101

As you can see this is the case we already looked into (n=1). So the hope was still alive.
R=2 – no match, R=3 – no match, R=4 – no match, but R=5 – match…

[1][0]{5}[1][^0+^1], for R=5
i=13
Binary I = 1101
Binary T = 1000001

Of course 13 is not dividable by 5^(n-1), but how can be sure that such i will not emerge sooner or later?
Let’s continue! The next R’s are again not matching ones. But R=9 is a good match:

i=205
Binary I = 11001101
Binary T = 10000000001

This is the first time I can feel the pattern here. The R’s are going 1,5,9 – rising with iteration 4.
I continued and as I guessed the next successful R was 13.

i=3277
Binary I = 110011001101
Binary T = 100000000000001
Now the things are getting really brighter, next successful R was 17, and next R was 21:

i=52429
Binary I = 1100110011001101
Binary T = 1000000000000000001

i=838861
Binary I = 11001100110011001101
Binary T = 10000000000000000000001
So, I write down those results and analyzed them. I just look at them as some crazy number sequences puzzle:

1,13,205,3277,52429,838861,?

Which is next? And most importantly – can be equal to some power of 5?

Look at the last digits only: 1,3,5,7,9,1 – can you feel the pattern?
I don’t care which number is the next one, but I did care about the last digit only (later in the topic we are going to discover the pattern of the generated numbers too).
Anyway, two patterns emerged!
1. The last digit of the number on this sequences is rising with 2
2. The binary representations of those numbers are in this format:
\begin{equation}
\underbrace {1100}_{x}1101 = binary(5^n) \\
\end{equation}
The block 1100 is repeated x times. The most important observation here to notice is the left side of this equation can’t be dividable by 5 if the last digits is different from 5. We can see that we need exactly 5 iteration steps to reach from one number with last digit 5 – to another number with fast digit 5. Let’s construct the first numbers suitable for our left side.

\begin{equation}
\underbrace {1100}_{1}1101 = binary(5^{n_1}) \\
\underbrace {1100}_{6}1101 = binary(5^{n_2}) \\
\underbrace {1100}_{11}1101 = binary(5^{n_3}) \\
\text{and so on ..}
\end{equation}
If another pair (m,n) exists, then some of those numbers should be equal to 5^(ni) for some i.
Let’s now simplify the results:

\begin{equation}
\underbrace {1100}_{1}1000 + 101 = binary(5^{n_1}) \\
\underbrace {1100}_{6}1000 + 101 = binary(5^{n_2}) \\
\underbrace {1100}_{11}1000 + 101 = binary(5^{n_3}) \\
\text{let's translate 101 from binary to decimal} \\
\underbrace {1100}_{1}1000 + 5 = binary(5^{n_1}) \\
\underbrace {1100}_{6}1000 + 5 = binary(5^{n_2}) \\
\underbrace {1100}_{11}1000 + 5 = binary(5^{n_3}) \\
\text{now let's translate the binary string to decimal too.} \\
2^3 + 2^6 + 2^7 + 5 = 5^{n_1} \\
2^3 + (2^6 + 2^7) + (2^{10} + 2^{11}) + (2^{14} + 2^{15}) + ... + (2^{26} + 2^{27}) + 5 = 5^{n_2} \\
2^3 + (2^6 + 2^7) + (2^{10} + 2^{11}) + (2^{14} + 2^{15}) + ... + (2^{46} + 2^{47}) + 5 = 5^{n_3} \\
\text{let's simplify} \\
2^3 + 2^6(1+2) + 5 = 5^{n_1} \\
2^3 + 2^6(1+2)+ 2^{10}(1+2) + 2^{14}(1+2) + ... + 2^{26}(1+2) + 5 = 5^{n_2} \\
2^3 + 2^6(1+2)+ 2^{10}(1+2) + 2^{14}(1+2) + ... + 2^{46}(1+2) + 5 = 5^{n_3} \\
\text{simplify again} \\
3*2^6 + 13 = 5^{n_1} \\
3*(2^6 + 2^{10} + 2^{14} + ... + 2^{26}) + 13 = 5^{n_2} \\
3*(2^6 + 2^{10} + 2^{14} + ... + 2^{46}) + 13 = 5^{n_3} \\
\text{ 3*2^6 = 3*64 = 192 , so let's substitute it} \\
205 = 5^{n_1} \\
3*2^6(2^4 + 2^{8} + 2^{12} + ... + 2^{20}) + 205 = 5^{n_2} \\
3*2^6(2^4 + 2^{8} + 2^{12} + ... + 2^{40}) + 205 = 5^{n_3} \\
\end{equation}
Now we can see that we have manually discovered the first number ending with 5, which we already discovered before – 205. Of course it’s not a square number so we can leave it, such n1 doesn’t exist!
But what about the others? This series continue to the infinity and the numbers get bigger and bigger, out of compute memory and power. It’s impossible to solve it like that.

Let’s simplify it little bit more and I will make one substitution so I can make the things more comfortable to work with.

\begin{equation}
192(2^4 + 2^{8} + 2^{12} + ... + 2^{20}) + 205 = 5^{n_2} \\
192(2^4 + 2^{8} + 2^{12} + ... + 2^{40}) + 205 = 5^{n_3} \\
\text{let's define this substitution:} \\
\Omega = 2^4 + 2^{8} + 2^{12} + ... + 2^{20} \\
192*\Omega + 205 = 5^{n_2} \\
192(2^4 + 2^{8} + 2^{12} + . + 2^{20} + 2^{24} + .. + 2^{40}) + 205 = 5^{n_3} \\
192(2^4 + 2^{8} + 2^{12} + . + 2^{20}) + 192(2^{24} + .. + 2^{40}) + 205 = 5^{n_3} \\
192 * \Omega + 192*2^{20}(2^4 + 2^{8} + 2^{12} + . + 2^{20}) + 205 = 5^{n_3} \\
192 * \Omega + 192*2^{20}* \Omega + 205 = 5^{n_3} \\
192 *\Omega * (1 + 2^{20}) + 205 = 5^{n_3} \\
\text{we can construct some of the other n's so you can feel the pattern} \\
192 *\Omega * (1 + 2^{20} + 2^{40}) + 205 = 5^{n_4} \\
192 *\Omega * (1 + 2^{20} + 2^{40} + 2^{60}) + 205 = 5^{n_5} \\
....\\
192 *\Omega * (1 + 2^{20} + 2^{40} + ... + 2^{20*(j-2)}) + 205 = 5^{n_j} \\
\end{equation}
Here is the pattern in our last equation. So we are going to use only the last pattern from now on.
OK, let’s divide to 5.

\begin{equation}
192 *\Omega * (1 + 2^{20} + 2^{40} + ... + 2^{20*(j-2)}) + 205 = 5^{n_j} \\
192 * \frac {\Omega} {5} * (1 + 2^{20} + 2^{40} + ... + 2^{20*(j-2)}) + 41 = 5^{n_j - 1} \\
\text{let's calculate }\Omega \text{ now} \\
\Omega = 2^4 + 2^{8} + 2^{12} + 2^{16} + 2^{20} \\
\Omega = 16 + 256 + 4096 + 65536 + 1048576 \\
\Omega = 1118480 \\
\frac {\Omega} {5} = \frac {1118480} {5} = 223696 \\
\text{now let's substitute the result} \\
192 * 223696 * (1 + 2^{20} + 2^{40} + ... + 2^{20*(j-2)}) + 41 = 5^{n_j - 1} \\
\text{now the thing that shocked me! 223696 is dividable by 41. Mad!}
\end{equation}

The whole left side of the equation is dividable by 41. The right side of the equation is dividable only to 1 prime number – 5. There is no place for another. Right now we can say the (2,1) is the only pair of this equation and because of the beauty and coincidence 223696 to be dividable by 41, I want to name this Theorem after me – Miro Theorem (or I should call it Paradox 41?).

Miro Theorem:

\begin{equation}
2^m + 1 = 5^r + 0 \\
\text{has only one solution m=2 and r=1} \\
\text{p.s. the format is strange, but I wanted to add "m 1 r 0" = miro}
\end{equation}