33^m - 7^n
If m and n are positive integers, what is the smallest absolute difference of 33^m - 7^n ?
Labels: mathschallenge
posted by Chris at
9:18 AM
Thursday, February 25, 2010
Links
Search
Share
- Tom Chrome Extension
- ToM @ Twitter
- MeeT ToM
- Daily Tricks Widget
- Vista Gadget 1.5
- iPhone Widget
- Windows XP Widget
- Google Toolbar Button
- Suggestions
Favorite Links
- Vista Sidebar Gadgets
- Widgets for Web 2.0
- C Sharp Tricks
- Interview Information
- Illustrator - Elar Alexander
Bookmark Us
Previous Posts
- The Bus Conversation
- Missing Digit
- Chris's English Comprehension Test
- How many trains?
- An Elusive Idea
- Iron chain
- Queue height
- Tavern Games
- Where's the Fifty?
- How old!!!???
26 Comments:
If M and N are both 1 the diff is 26
They can't be the same, right? Then they'd be M and M not M and N.
Will try figure this one out :P
ok, if m=2 and n=3 then the diff is 746
That's true. But can you get an even smaller difference than that?
e.g. If m = 4, then, it looks like n ≈ 7.2 (so n = 7 or 8) might give a smaller difference.
---
I'm out for the next 5 hours, so won't be posting before then.
Wow. A load of posts have just appeared. I only saw Ragknot's when I started replying.
You might be right Pingy, but I don't see why they must be different, but would say 26 is the minimum. If they are different the 746 is the minimum. But that seems to easy, there's probably a trick here.
Yep, It doesn't say the diff is an integer.
I have no problem with m = n (= 1). But can you do better?
But if M and N are integers, then the diff is an integer, right?
Last post until later. In principle, it might be that for some (possibly very) large m,n that you could do better than 26.
If m = n = 1 is the best combination, prove it.
I thought about both being zero, and diff =1, but is zero a Positive integer? I don't this so
Mmm, say if M is the Latin numeral M, which equals 1000.
Then, 33^1000 - 7^n > 0
log on both sides, n < 1000 log33/log7
So, with n = 1796 one should get the minimal difference.
I am just trying to do it out of the box...
Otherwise that, I'd go with m=2, and n=3, in case m doesn't equal n, or m = n = 1 otherwise.
If m and n are integers, then the difference is an integer. Any integer raised to the power of a positive integer is an integer. And the difference of any two integers is an integer.
33^0 - 7^0 = 1 - 1 = 0. But I want m,n > 0
Here's a very fuzzy argument that m=n=1 is the minimum:
define f(m,n) = 33^m-7^n
log(33)/log(7) is about 1.7968.
So pick n = floor(m*1.7968). I.e. if m is 100, n is 179. Then 7^n < 33^m < 7^(n+1).
In base 7, 33^m and 7^n both have n digits, and 7^(n+1) has one more. 7^n is all zeroes except for the first digit which is a one. Unless every digit of 33^m other than the first, next-to-last, and last are also zero, then 33^m-7^n is going to have more than 2 digits.
33^1-7^1 has 2 digits. Hence it is the minimum.
I think we can prove that m=n=1 is the minimal as follows.
Put 33 as 7^(log33/log7)
So, we've 7^m^(log33/log7) - 7^n > 0
mlog33/log7 > n
1.79m > n
Hence, n = m --->(1)
So, we want to minimize 33^m - 7^m. Diff. with respect to m, we get 33^m-1 = 7^m-1, which has a single solution of m = 1, as m is a positive integer.
Sub. into (1), we get m = n = 1.
Hmmm. I've got to put my thinking on on for both of you. I'll be back. I've read enough to make me think that Ross is at least very close. Mohamed, you seem to have made a crucial mistake. I don't follow your jump to "Hence, n = m --->(1)", it only follows that 1.79m ≈ n, not m = n.
I've just edited the question very slightly as it has caused a minor misunderstanding.
Mohamed. I first started off on that path, but realised that we ideally want to choose n/m = log[33]/log[7]. log[33]/log[7] is irrational (see below). We now have the problem of how to find an (extremely) good approximation to it by the rational number n/m. I'm not familiar with the techniques of finding these super close m,n pairs; my guts tell me that those techniques are not appropriate for resolving our problem.
Ross. Phew! that took a while to crack. The flaw in your argument is that n [floor of 1.79m] might be such that you are closer than 26. You are right in that increasing n to the ceiling (n+1) will be substantially different, 6*7^n in fact, that it couldn't possibly match if n very nearly matched. So it is possible that you might have got a lucky m,n pair.
It can be proven that log[33]/log[7] is irrational. I'll tweak a nice proof that Cam gave a while back.
let log[b]/log[a] = n/m, then b = a^(n/m) => b^m = a^n. In our case, a = 7,b = 33 = 3*11. So we have (3*11)^m = 7^n. But by the fundamental theorem of arithmetic, only m = n = 0 can satisfy that equation. However, that's largely an aside, but it does show that 33^m ≠ 7^n for any natural numbers m,n.
A related aside is that 22/7 is an extra good rational approximation to π. It is only 0.04% in error. I think the next extra good approximation is 355/113 with a 0.00001% error.
Do you want a small hint?
I'm probably wrong but I get 16.
Chris ...
I don't have a clue :) but a nice puzzle.
Thanks Zaux. I'm going to give a fairly big clue, because I think there is one too many steps to guess it all. Consider the problem in both mod 3 and mod 16 arithmetic. Even with that clue, you should still feel pleased with yourselves if/when you finish the job. I don't know if other modulo systems could be used instead.
LAst Anonymous. What values of m and n gave you 16?
Thanks for the big hint. Here's what I get right away from that:
OK, consider it in mod 3 arithmetic.
33, being a multiple of 3, is 0 mod 3. So is any power of 33.
7 is 1 mod 3. so is any power of 7.
So, (33^m - 7^n) = 0 - 1 = 2 mod 3.
Now consider it in mod 16.
33 = 1 mod 16. 33^m = 1 mod 16.
7 = 7 mod 16. 7^n = 7 mod 16 if n odd, 1 mod 16 if n even.
So 33^m - 7^n = 0 mod 16 if n even
or 10 mod 16 if n odd.
On a whim, let's try mod 8 arithmetic.
33 = 1 mod 8. 33^m = 1 mod 8.
7 = 7 mod 8. 7^n = 7 mod 8 if n odd, 1 mod 8 if n even.
So 33^m - 7^n = 0 mod 8 if n even, 2 mod 8 if n odd.
Let's examine the numbers from 1 to 26 in mod 3, mod 8, and mod 16. We're looking for lines that go "2,0,0", "2,0,10", "2,2,0" or "2,2,10".
1: 1, 1, 1
2: 2, 2, 2
3: 0, 3, 3
4: 1, 4, 4
5: 2, 5, 5
6: 0, 6, 6
7: 1, 7, 7
8: 2, 0, 8
9: 0, 1, 9
10: 1, 2, 10
11: 2, 3, 11
12: 0, 4, 12
13: 1, 5, 13
14: 2, 6, 14
15: 0, 7, 15
16: 1, 0, 0
17: 2, 1, 1
18: 0, 2, 2
19: 1, 3, 3
20: 2, 4, 4
21: 0, 5, 5
22: 1, 6, 6
23: 2, 7, 7
24: 0, 0, 8
25: 1, 1, 9
26: 2, 2, 10
Proven: 26 is the lowest possible difference.
Mod 8 didn't actually help, though. Mod 3 + mod 16 would have been sufficient.
This does not prove that m=n=1 is the only solution that comes up with 26, though. But it would make a search MUCH easier.
This also proves that 16 is NOT a possible difference, since it is 1 mod 3, not 2 mod 3.
Hi Ross. Well done. I hope that the big hint didn't spoil the
problem too much for you. I messed things up. I should have
stuck with 33^m - 7^n ≥ 0 => 26.
Let D = 33^m - 7^n
33^m = 1 and 7^n = 1 or 7 (mod 16) => D = 0, 10 (mod 16)
=> D = -32, -22, -16, -6, 0, 10, 16, 26, 32, ...
33^m = 0 and 7^n = 1 (mod 3) => D = 2 (mod 3) => D = -28,-25,-22,
-19,-16,-13,-10,-7,-4,-1,2,5,8,11,14,17,20,23,26,29,...
The smallest common number > 0 is 26. But we know that m=n=1
gives D = 26, so 26 is the smallest possible +ve value.
Interestingly tough, -16 is possible (based on the above).
I don't if an m,n pair can be found that gives that, or if
examination in a different modulo system, excludes that.
Frustratingly, I've go to go out to a customer. When I get
back I'll try a few other modulo systems to see if we can
reject -16. Otherwise, hat's off to Anonymous 7:28 PM.
Thanks Chris for that nice puzzle!
Following your hint, I got the following:
33 % 3 = 0
7 % 3 = 1
And so 33^m and 7^n.
33 % 16 = 33^m = 1
7 % 16 = 7
7^n % 16 = 7 where n is odd or 1 where n i s even.
So we've:
|33^m - 7^n| % 3 = 1 ---->(1)
|33^m - 7^n| % 16 = 0 ;n even --->(2)
|33^m - 7^n| % 16 = 6 ;n odd ---->(3)
To get the minimum difference, we're looking for the smallest quantity that satisfy (1) and (2), which is 16. And that can be obtained by setting m = 1, and n = 2.
Is that anyway close?
Hi Mohamed. I was just about to post that m=1,n=2 => 33-49 = -16.
That's only allowed because I goofed the question when editing it.
So yes, your (-)16 is as close as is possible LOL.
Note that, in principle, although the mod 3 and 16 examinations
allowed -16 and +26, they might have been excluded when tried
with another modulo system. However as m = n = 1 => +26 and
m = 1, n = 2 => -16, you'll find that it isn't possible to find a
modulo system that excludes those.
So I'm kinda pleased that I goofed, otherwise I would never
have known that -16 was possible.
And thank for the "thank you"'s. They're much apppreciated.
Just for your info, that was a Harvard grade problem.
Post a Comment
Links to this post:
Create a Link
<< Home