## 49^m – 33^n

Posted by Chris on February 29, 2012 – 8:35 pm

I can’t stand the lack of activity, so here’s a semi-rubbish problem.

1. If x = 49^m – 33^n, where m and n are positive integers, what is the smallest (in magnitude) positive and negative value of x, and what are the corresponding values of m and n? Prove your answer.

2. The above is easy. The next might be very difficult or impossible to do. Are there any other values of m and n that produce the minimal x’s?

3. What’s the second smallest values of x and the associated m and n?

4. Again might be difficult/impossible, are there other values for m and n in part 3?

March 1st, 2012 at 7:00 am

Why is the title like it is? No “n”.

But the second m is changed to n below the title.

March 1st, 2012 at 7:31 am

Hi Ragknot. I goofed – now fixed.

I have only worked on the first problem. So I have no idea how difficult parts 2, 3 and 4 are – except that I’m pretty sure that parts 2 and 4 might be intractible. A computer may prove useful at finding some of the m and n’s.

March 1st, 2012 at 1:16 pm

1 – Smallest positive value of x is 16 (m and n both = 1) if you exclude 0 as being a positive integer.

Smallest negative value of x is -infinity (m = 1, n = infinity. Substitute the higest number you can think of for infinity if you don’t like using infinity).

March 1st, 2012 at 2:38 pm

Hi Eketahuna. You haven’t read the question I said the smallest negative value “in magnitude”.

16 is the smallest positive value and m = n = 1 does the trick. But you haven’t proven that there isn’t a value between 0 and 16.

I didn’t allow for the possibility of the difference being 0. In fact, that special case isn’t possible. There is a “simple” proof of that.

March 1st, 2012 at 3:00 pm

When I looked at the original title, 49^m-33^m, I saw 16 would be the lowest X would be 16… Changing the title, did not change the X=16.

The other questions? I don’t see a decent path, but I assume there must be someway.

March 1st, 2012 at 3:35 pm

Hi Ragknot. Your typo is worse than mine was

Yep, it just so happens that m = n = 1 does give the minimum 16.

But the (not so) hard part is proving that 16 is the smallest positive value of x.

I have no idea what the smallest value (in magnitude) of the negative value of x is and so I’ve no idea what the coresponding m and n values are either.

March 1st, 2012 at 4:36 pm

Oops, -1040

There can’t be a value between 0 and 16. As m increases, n also needs to increase to compensate for the larger result, but as it’s operating on a smaller number to start, the difference between the two becomes greater. Therefore they both need to be as small as possible. If n is < m then it becomes a negative number with the same properties, but in the opposite direction.

I can't explain that in quadratic type equations though.

March 1st, 2012 at 8:48 pm

Hi Eketahuna. Your explanation is not even close to a proof In principle, it may be that for some (very) large m and n, you get lucky.

I’ll give a hint: modulo arithmetic methods are easily able to show that 0 through 15 isn’t possible. That 0 isn’t allowed can also be shown by using the fundamental theorem of arithmetic (AKA the unique prime factorization theorem).

March 8th, 2012 at 7:52 pm

Here’s a part of the solution to part 1. I hope I get a chance to go further. And ooops, the -ve value part of part 1 isn’t easy.

Let k = 49^m – 33^n

So k = 1^m – 1^n = 0 (mod 16)

=> k = …, -48, -32, -16, 0, 16, 32, 48,…

k = 1^m – 9^n = 4 (mod 12)

=> k = -46, -32, -20, -8 ,4, 16, 28, 40, …

NB generally 12 is a nice modulo base as CarmichaelLamda(12) = 2

-32 and 16 are the smallest magnitude numbers common to both lists and so are possibly the solutions. We can safely say that there cannot be a solution between -32 and 16. Note that we can only eliminate possible solutions. It may be that trying another modulo base, that we could also eliminate -32.

It is simple to see that for m = n = 1, that we get the 16 and so this is in fact the smallest positive difference.

Because of the commonality, so far, the possible negative values are

-32, -80, -128, -176,… The step is LCM(12, 16) = 48.

Let’s try mod 11. We get k = 5^m – 0 (mod 11)

Unfortunately that’s not too helpful because we could have (as m is tweaked from 1 to 10) we get k = 5, 3, 4, 9, 1 plus multiples of 11. That’s also sad because LCM(11, 12, 16) = 528 is quite big. However, the 1 => 1 – 3*11 = -32 is still a candidate. So I’m beginning to suspect that -32 is the smallest negative difference.

March 8th, 2012 at 8:06 pm

I forgot to say that the way of eliminating k = 0 is that, if k = 0 then we’d have 49^m = 33^n. But 49 = 7*7 and 33 = 3*11.

So we’d have x = 7

^{2m}= 3^{n}* 11^{n}. The fundamental theorem of arithmetic says that it is only possible to have a unique (up to order) prime factor representation of an integer. So that x isn’t possible.March 11th, 2012 at 10:58 am

@Chris : How did you choose 16 and 12 (except for the fact that you get convenient values for modulo arithmetic)? You said something about CarmichaelLambda for 12 being low (=2), I looked it up and will try to get the meaning of this.

March 11th, 2012 at 4:09 pm

Hi Karys. You’ve answered your own question – the convenient resulting equations were the reason. I had initially designed the problem to make modulo 3 and 16 be “obvious” It was luck that 12 works better than 3.

As you’ll find out, the Carmichael Lambda function is really sweet. It’s intimately associated with the most general extension (that I know of) of Fermat’s little theorem (FLT). It doesn’t always produce the smallest result, but it is never bigger than Euler’s totient function (which in turn has the advantage of being easier to calculate).

Quickie: If p is prime and a is coprime to p (i.e. gcd(a,p) =1) then FLT says

a

^{p-1}= 1 (mod p). Euler generalised this using his totient function, φ, to get:if gcd(a,m) = 1, then a

^{φ(m)}= 1 (mod m). Note that m can be composite. As far as I’m aware Euler didn’t invent the totient function for that purpose. φ(m) doesn’t produce the smallest result. e.g. φ(12) = 4. But it turns out that we only need 2. e.g. 5^{2}= 7^{2}= 11^{2}= … = ∞^{2}= 1 (mod 12) – which I think is amazing. Carmichael’s lambda function is such that λ(m) ≤ φ(m). It is also the best universal function i.e. it always works, but for some values of a and m, a value smaller than λ(m) will do.I was hoping to provide a proof that the m and n values were unique, but I failed. However, I suspect that it is the case that there is only one m, n pair for a given difference (including sign). If that is true, and if e.g. -32 is the smallest negative value, finding m and n may prove hopeless as m and n might be enormous. Searching for a needle in a haystack may well be trivial in comparison.

Aside (which may prove useful later): if m and n are so large that 49

^{m}and 33^{n}are both much greater than k, then we have that 49^{m}≈ 33^{n}. Taking logs (arbitrary base) => m log49 ≈ n log33 => n/m ≈ log49/log33 ≈ 1.11306March 11th, 2012 at 7:15 pm

Hi Karys. I didn’t answer your main query properly. The last part of my post 9 shows that some modulo bases (11 in the post) don’t really help eliminate possible solutions. Of course you could make observations about solutions for m odd/even and n odd/even.

March 12th, 2012 at 8:55 pm

I’ve been reduced to number crunching (with Mathematica).

In letting m go up to 400 000, using 33^n – 49^m = k > 0, the smallest k’s I’ve found are: k = 1040 with n =2 and m = 1, and k = 33536 and that’s for m = 2, n = 3.

March 17th, 2012 at 1:27 pm

Continuing Chris’s solution :

I brute forced first potentially small values for k(m,n)=49^m-33^n.

1) Biggest negative value : 32 right in plain sight yet I saw it only afterwards : 32 = 33-1.

The sequence seems to explode as expected…

March 17th, 2012 at 5:21 pm

Hi Karys. Nice try, but you’ve used m = 0, n = 1. I had disallowed that in the problem. Otherwise m = n = 0 => k = 0.

I accept (and always knew) that most best guesses would produce very large results. But just getting large (and larger) results, doesn’t mean that you won’t get the odd special value that is very small (relatively).

Unfortuntely my attempted proof of the uniqueness of k(m,n) involves math that seems to be harder than that required for Maths Challenge 4

I will write up some more stuff. But I’d really like to get to grips with the techniques for finding a good rational approximation to an irrational number – even if only to demonstrate that form some m,n values you will get a relatively small k. But as to finding e.g. -32, I doubt it’s feasible (or your solution has possibly knocked a further solution out of the running).

March 18th, 2012 at 12:01 pm

Oh right I misread that. (As an excuse I could say that here in France “positive” means “positive OR zero”…)

March 19th, 2012 at 7:49 pm

The search for the smallest magnitude negative solution (with m,n > 0) is almost certainly an excercise in futility. The reason is that for a given k, there is probably only one possible m, n pair. Unfortunately the proof of that is beyond me. But here’s my failed attempt of a proof by contradiction.

Let 49

^{m}– 33^{n}= k be a solution, where m and n is the smallest pair for the given k. Let M > m and N > n and 49^{M}– 33^{N}= k, where M, N are the next smallest pair. Subtracting and rearranging gives 49^{m}(49^{M-m}– 1) = 33^{n}(33^{N-n}– 1). By the fundamental theorem of arithmetic no factors of 33^{n}can be common to 49^{m}. Therefore 33^{N-n}– 1 must have a factor 49^{m}and 49^{M-m}– 1 must have a factor 33^{n}. So, let 33^{N-n}– 1 = u 49^{m}and 49^{M-m}– 1 = v 33^{n}. On substituting back into the equation we see that u = v. However, that u = v is irrelevant for my purposes.Because 49

^{m}divides 33^{N-n}-1 we have 33^{N-n}– 1 = 0 (mod 49). A quick check shows that N-n must be a multiple of 42 (the answer to everything). So N must be a multiple of 42 more than n. In fact if m = 2, then 33^{N-n}– 1 = 0 (mod 49^{2}) => N-n must be a multiple of 2058. For each unit increase in m, the multiple increases by a factor of 49.Because 33

^{n}divides 49^{M-m}– 1 we have 49^{M-m}– 1 = 16^{M-m}– 1 = 0 (mod 33). On checking we find that M-m needs to be a multiple of 5, so M must be a multiple of 5 more than m. Each increment of 1 in n (cf 33^{n}) increases that factor by 33. So altogether we would typically expect M and N to be quite large compared to m and n.Sadly, I don’t know what to do next, so here endeth my “proof”.

Referring to the last part of my post 12, it is clear that if 49

^{m}and 33^{n}are >> k, that the ratio of those two numbers must be close to 1 and n/m → log49/log33. What we’d like is to find good rational approximations to log49/log33. Luckily for me, Mathematica has a function (Convergents) that rattles them out.Here are the first 21 “best” rational approximations to log49/log33:

1, 9/8, 10/9, 59/53, 128/115, 571/513, 1841/1654, 9776/8783,

11617/10437, 33010/29657, 143657/129065, 176667/158722,

673658/605231, 850325/763953, 2374308/2133137, 7973249/7163364,

26294055/23623229, 34267304/30786593, 94828663/85196415,

129095967/115983008, 223924630/201179423

Mathematica can only handle up to the 20th one, and that gives

49

^{115983008}– 33^{129095967}≈ -3.86943 * 10^{196034017}That difference is about 1 part in 10

^{8}of the main terms. So it’s a good approximation, but the associated k value is humongous.Unless Slavy comes along with some clever maths, I reckon the posted problem has been taken about as far as I can take it. I’m sparing you the rather dull calculus that I’d done for it.

March 20th, 2012 at 5:38 am

Just for amusement, here are the first 30 convergents for pi.

3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, 208341/66317,

312689/99532, 833719/265381, 1146408/364913, 4272943/1360120,

5419351/1725033, 80143857/25510582, 165707065/52746197,

245850922/78256779, 411557987/131002976, 1068966896/340262731,

2549491779/811528438, 6167950454/1963319607, 14885392687/4738167652,

21053343141/6701487259, 1783366216531/567663097408,

3587785776203/1142027682075, 5371151992734/1709690779483,

8958937768937/2851718461558, 139755218526789/44485467702853, 428224593349304/136308121570117, 5706674932067741/1816491048114374,

6134899525417045/1952799169684491, 30246273033735921/9627687726852338

22/7 and 355/113 are well known. A sort of mnemonic is “113355″

March 24th, 2012 at 11:55 am

Having seen the large numbers in the Little 6 problem, I now wonder if there is yet hope for solving the problem. I suspect that the required m and n values are enormous.

I think that Karys’s solution for -32 probably rules out another way of getting it. So -80 is now my next best guess.

September 2nd, 2012 at 7:04 am

i know that is old problem, but i think that 1st problem you can solve with shortcut formulas.