Math Question (logarithms)

Let X be the number you are looking for and Y be the full integer it becomes.

y = x log2(10) = log2 (10^x)
2^y = 10^x = (2^x)(5^x)

That (5^x) kills you. A power of two will never go into a power of five evenly. The only way that is possible is if x = 0, so there is no positive integer that works.

I think I'm trying to solve this question in the wrong way.

how do I solve this puzzle:

Find all natural numbers n not exceeding 13 and representable in the form
(2^L - 2^m)/10^k
for some positive integers L; m and k.


For example, if L = 7; m = 3; and k =1. you will produce the number 12

Someone really doesn't like you to give you these types of questions.

Start with

(2^L - 2^m)/10^k = n
(2^L - 2^m) = n(10^k)
2^m [ 2^(L-m) - 1] = n(10^k)

Since 10 is 5x2, and the 2^m is never going to produce a factor of 5, the
[ 2^(L-m) - 1] term is going to have to be divisible by five. Every fourth power of two (multiple of 16) ends in 6 and will be divisible by five when you subtract one.

16 - 1 = 15 where L-m = 4
256 - 1 = 255 where L-m = 8
...

Now you have to find ways to make that number divisible by 10.
15 x 2 = 30 which is divisible by 10, so n=3, k=1, m=1, L=5
15x4 = 60, so n=6, k=1, m=2, L=6
15x6 = 90, so n=9, k=1, m=3, L=7
15x8 you already have.

I don't think 255 pays off for you, but you can try it looking for higher values of k.

To finish up what engineer so nicely started...

L-m must be a multiple of 4.
Therefore, you're looking for solutions to:
2^m(16^x - 1) = n*10^k, 1 <= n <= 13

Let's eliminate all powers of 2 from both sides:
16^x - 1 = n*5^k, n = 1, 3, 5, 7, 9, 11, 13

16^x = (4^x)^2; so we have:
(4^x)^2 - 1 = n*5^k, n = 1, 3, 5, 7, 9, 11, 13

The expression on the left is the difference of two squares. Therefore, it can be rewritten as:
(4^x - 1)(4^x + 1) = n*5^k, n = 1, 3, 5, 7, 9, 11, 13

4^x - 1 and 4^x + 1 can't both be multiples of 5 since they differ by 2. Therefore, the left side contains a factor that is not a multiple of 5 and is at least 4^x - 1.

The problem requires that that factor be no greater than 13, which means x must be less than 2 (since 4^2 - 1 = 15).

The bottom line is that your search is over. You don't need to consider differences (L-m) greater than 4.

Thank you both.

I had a hunch from playing with the numbers that there were only three possible integers the equation could produce (3, 6, & 12). Engineer did a fantastic job of showing the line of logic to break down the problem and form deductions. 9 wasn't a possible solution given the numbers 7 and 3, but it's only a minor slip up.

I didn't quite understand markr's logic (no offence). I didn't understand how he removed the powers of two from both sides when they had different exponential values (I'm likely just new to the technique).

I have a hunch that (2^y - 1) can never be divisible by 125 or any other power of 5 greater than 5^1 (in terms of positive integers anyway). If I'm right, this would mean k must equal 1; and this would prove that only 3, 6, and 12 are valid answers. Is there any way to prove it?

Thank you again for your help

For the left side to equal the right side, the exponents of 2 must be equal. Therefore, any candidate for a solution allows us to remove the 2's from both sides.

Hunch is false. For any positive x, there are an infinite number of y's such that 2^y - 1 = 0 mod 5^x.

Example:
2^20 - 1 = 25 * 41943
2^40 - 1 = 25 * 43980465111

By the way, this is why you need some way to prove that there are no solutions for larger differences (L-m).

When you're remove 2^m and 2^k from either side, this is to say that m = k. I'm curious how you got to that step. I can see how the difference between m and L can't be greater than 4, but I think I need a more thorough explanation for how you came to that (I mainly lose track around the point you say k=m)

Thanks again

Okay, I get this because as engineer explained, the power of two has to end with 6 in order to be divisible by 5. So the exponent has to be a multiple of 4.



By making 2^(L-m) into 16^x, this is to say (L-m) is a multiple of 4. So L-m = 4x.

So 2^(4x) = 16^x. I'm still following you.



This is where I don't follow. I have a hunch that m is going to always going to be equal to, or greater than k, so I'll divide both sides by 2^k

2^m (16^x - 1) = n (5^k) (2^k)
2^m/2^k (16^x - 1) = n (5^k) (2^k)/(2^k)
2^[m-k] * (16^x - 1) = n (5^k)

From there, you eliminated 2^[m-k], so you are claiming that m=k. But, even with the example m=3; L=7; k=1, we know that isn't true. But then I noticed that you removed the result "12" from the range of n, I'm just not sure why this was done. I can see you're onto something, I'm just not clicking with how you figured out "k=m if n is odd"



I get that, you're breaking it down and showing that 4^x - 1 must be divisible by five. Even if 2^[m-k] where still there, this would still be the case. So I'm guessing we can reopen the range of n to even numbers again.



I think out of everything, this is where I was genuinely confused.

x<2
4x = L-m

Ergo, (L-m)/4 = 1

But how do we know x must equal less than 2?

First, notice in engineer's example that he fixed L-m at 4. He then varied m to produce different solutions. The value of m is irrelevant with respect to producing powers of 5 on the left.

Second, for the equation to be true, the exponents of 2 must be equal on both sides. Note that this includes any 2's that appear in n - which is why I limited n to odd numbers after removing the 2's. I should have pointed out that because of this, my n is not necessarily the same as engineer's n. Let's call my n p from here on. Then n = p * 2^j, where j is the number of 2's removed from engineer's n.

For a solution to exist to engineer's equation, a solution must exist to my (2's removed) equation. Any solutions to my equation that are found can then be transformed into solutions to engineer's equation by adjusting m and p (multiplying p by powers of 2).

My result ( leads to a single family of solutions:
(4-1)(4+1) = p*5, p=3

Going back to engineer's equation, we have:
2^m * 15 = (3 * 2^j) * 10^k, k=1
or:
2^m * 15 = (3 * 2^j) * 10

Note that the parenthetical expression represents engineer's n, and it must be less than or equal to 13. Therefore, 0 <= j <= 2 which means 1 <= m <= 3.

These are your three solutions.

I was typing my last post when your last post was entered.

Hopefully, my last post explains eliminating the 2's, and that I'm not assuming that m=k. Perhaps eliminating the 2's was an unnecessary step.

I think that leaves the question of why x < 2 after we've gotten to this:
(4^x - 1)(4^x + 1) = n*5^k, n = 1, 3, 5, 7, 9, 11, 13

4^x - 1 is not necessarily divisible by 5, but for a solution to exist either 4^x - 1 or 4^x + 1 must be divisible by 5. They can't both be divisible by 5 because they differ by only 2.

Whichever is not divisible by 5 must be a factor of p (which I introduced in my previous post). Assuming that the smaller of the two (4^x - 1) is not divisible by 5 implies that p >= 4^x - 1. Since n, and therefore p, must not exceed 13, 4^x - 1 must not exceed 13. That limits x to 1.

It took me a bit to understand what you were getting at, but I finally got it.

The equation breaks into:
2^[m-k] (4^x - 1) (4^x + 1)
5^k

Since 4^x-1 and 4^x+1 alternate between being divisible by 5, we have to look at the other one to determine what is the lowest possible number.

Since x = 1 will produce this: 2^j * 3 * 1
we can say j (aka "m-k") can be changed to produce the final output of 3, 6, and 12

If x = 2, the factor that isn't divisible by 5 will be 17, meaning no matter how many times the other factor is divided, it will be over. So x must equal 1, and therefore k must equal 1.

Thank you, you fixed my problem.