Subscribe via feed.

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?


This post is under “MathsChallenge” and has 21 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

21 Responds so far- Add one»

  1. 1. ragknot Said:

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

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

  2. 2. Chris Said:

    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.

  3. 3. Eketahuna Said:

    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).

  4. 4. Chris Said:

    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.

  5. 5. ragknot Said:

    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.

  6. 6. Chris Said:

    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.

  7. 7. Eketahuna Said:

    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.

  8. 8. Chris Said:

    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).

  9. 9. Chris Said:

    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.

  10. 10. Chris Said:

    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 = 72m = 3n * 11n. 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.

  11. 11. Karys Said:

    @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.

  12. 12. Chris Said:

    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
    ap-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. 52 = 72 = 112 = … = ∞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 49m and 33n are both much greater than k, then we have that 49m ≈ 33n. Taking logs (arbitrary base) => m log49 ≈ n log33 => n/m ≈ log49/log33 ≈ 1.11306

  13. 13. Chris Said:

    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.

  14. 14. Chris Said:

    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.

  15. 15. Karys Said:

    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…

  16. 16. Chris Said:

    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).

  17. 17. Karys Said:

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

  18. 18. Chris Said:

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

    Because 49m divides 33N-n -1 we have 33N-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 33N-n – 1 = 0 (mod 492) => N-n must be a multiple of 2058. For each unit increase in m, the multiple increases by a factor of 49.

    Because 33n divides 49M-m – 1 we have 49M-m – 1 = 16M-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 33n) 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 49m and 33n 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
    49115983008 – 33129095967 ≈ -3.86943 * 10196034017
    That difference is about 1 part in 108 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.

  19. 19. Chris Said:

    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″

    22/7    = 3.1428571...
    Pi      = 3.14159265...
    355/113 = 3.14159292...
    
  20. 20. Chris Said:

    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.

  21. 21. piter Said:

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

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0