Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

An Interesting Question

  1. Dec 2, 2007 #1
    I have been trying to see how it can be proven that a power of 3 minus a power of 2 (or a power of 2 minus a power of 3) can give you every number which is not a product of 2 or 3. I just don't see how to prove it. Does it have something to do with the fact that you can get 1 as 3 minus 2?

    By the way, hello, it's nice to join you all. Hope you can clarify my confusion, and thanks.

  2. jcsd
  3. Dec 2, 2007 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    approx, you triple-posted this "interesting question". You are not supposed to do this. You should have posted topic this once and once only. Moreover, this looks like homework. You didn't show any work. You are supposed to do this.

    Did you read our rules when you signed up? Here they are, https://www.physicsforums.com/showthread.php?t=5374
  4. Dec 2, 2007 #3

    sorry, i guess i didn't know you couldn't post in the different forums...
    Which forum should I leave it in, and how do i remove it?
    BTW, I'm teaching math at ivytech in muncie, IN. I don't have any classes or homework anymore, and won't ever again, unless I go for my pH.D. I've tried to solve this problem for a while, most recently I looked at one of the proofs that the smallest linear combination of a and b is the gcd of a and b, and tried to generalize it for exponentiation. I just wondered if anyone had a fresh outlook that could spark an idea. Sorry.
  5. Dec 2, 2007 #4
    I think you might be able to do an inductive proof of some kind. It doesn't seem totally easy, but my first idea is to assume it's true up to [tex]n[/tex], and then try to find a way to do it for [tex]n+1[/tex] (or the next non-multiple of 2 or 3, just call the number m) by subtracting all powers of 3 from it that are less than n+1. You'll have [tex]m - 3^k = 2^i(3^j - 2^l)[/tex] or the other way around, and then hopefully you can make sure that for at least one [tex]k[/tex], you'll have a value of [tex]i[/tex] and a sign that will allow you to get [tex]m[/tex] in the desired form.

    Anyway it's just an idea. This problem doesn't seem trivial.
  6. Dec 3, 2007 #5
    Ok, so if m is relatively prime to 6, then m-3^k will be even and relatively prime to 3, then we can divide out 2^i to get some number, smaller than m, which we can already represent as (3^j-2^l)? But then we get m = (2^i)(3^j)-(2^(i+l))+(3^k), and I don't see an easy way to change that to 3^a - 2^b. It's a good try, though, thank you. No, what I think will be required is something very, very clever, because I've worked on it for quite a while and I still just don't see it. My idea is to use the fact that all linear combinations of 3 and 2 are multiples of their gcd (which is one) so we can in principle use linear combinations to get all integers.... but the only coefficients to 3 we are allowing are powers of 3 and the only coefficients of 2 we use are powers of 2.... so from our list of results of linear combinations, we can automatically strike out any products of 2 or 3. IOW, 3a-2b=the integers, when a and b are integers; but now I'm restricting a and b to powers of 3 and of 2, respectively. Now I just have to show that restricting our coefficients didn't eliminate any other answers than the products of 2 or 3. Any ideas?
  7. Dec 3, 2007 #6
    If i = 1 and j=k you will have the right form. Or if the representation of the smaller number is 2^l - 3^j, you have 2^{l+i} - 2^i3^j + 3^k so if i = 2 and j+1 = k or i = 1 and j=k still works too.

    So what I was suggesting was trying to figure out if one of those three cases must happen if you do it for all values of k.

    Compare Putnam 2005 A1: http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pdf/2005.pdf" [Broken]
    (http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pdf/2005s.pdf" [Broken])

    Another option (which I didn't think about so I don't know if it has any potential) would be to allow a or b to also take values which are 0 or powers of the other number, so that you can make any integer again. Then try an inductive proof of that statement.

    By the way, do you know if this is actually true? Or is it your conjecture? Let's look for patterns:
    I can't figure out how to do 31. I'm having trouble with some of the ones after it too, actually.
    Last edited by a moderator: May 3, 2017
  8. Dec 3, 2007 #7

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

  9. Dec 3, 2007 #8
    Hehe, this reminds me of a story (possibly just rumor) of a grad student who was asked to factor the number 6 in [tex]Q(\sqrt{-5})[/tex] two different ways during a prelim. The idea was to start with very simple questions to get the student to be less nervous. The student was able to get:

    [tex]6 = (1+\sqrt{-5})(1-\sqrt{-5})[/tex]

    but was unable to find a second factorization. The story is probably just rumor, but I can imagine someone being nervous enough to overlook [tex]6 = 2\cdot 3[/tex]
  10. Dec 3, 2007 #9
    Sorry, I didn't realize we were allowing 0th powers too. (It seems to go against the OP's idea about generalization of GCD -- raising to a 0th power is like multiplying by 0 in $am + bn = c$. Then also we can obtain lots of multiples of 2 or 3: 3-1 = 2, 9-1 = 8, 4-1 = 3...)

    Even then, I don't think I can do 35 with reasonably small powers either, and that isn't trivialized by adding in 0th powers.
  11. Dec 3, 2007 #10
    well, we can fix the problem with 31 and 35 if we allow addition,
    and thanks for the link and idea, I've only got a minute, but I'll check it out a little later.
    Last edited: Dec 3, 2007
  12. Dec 3, 2007 #11
    I didn't say it's not possible to do 31 and 35 with subtraction only -- I'd be interested to see if powers of 2 and 3 continue to be close together sometimes even when the powers are high. For example, 13 = 16-3 but also 13 = 256 - 243. But up to the next several powers of 3 that I know, there aren't any that are very close to powers of 2.

    Here's a slightly more general version. Let $A = \{2^n3^m : n, m \in \mathbb{N}\}$. What is $A + A = \{a_1 + a_2 : a_1, a_2 \in A\}$? What about $A-A$? Here's a 'philosophical' reason for why we would expect those two sets to be big: by definition it's clear that $A * A = A$. There's a general idea in the field of arithmetic combinatorics that if $A*A$ is not much bigger than $A$, then $A + A$ must be big. You can see this, for example, in Lagrange's four squares theorem. The set $S$ of perfect squares is also closed under multiplication, and $S + S + S + S \supset \mathbb{N}$ (if you include 0). But our set $A$ is much less dense than the set of squares....

    edit: sorry, I forgot that this forum uses tex-tags instead of $. I am kinda too lazy to go replace them all...
  13. Dec 4, 2007 #12

    So let me see if I get this....


    BTW, using plus or minus was part of the original conjecture, but I am curious whether plus is needed.
  14. Dec 4, 2007 #13


    User Avatar
    Science Advisor
    Homework Helper

    Here's the part where I pop in with some numerical evidence.

    I have trouble with 53, 71, and 95. If the conjecture holds for these numbers, then the constituent powers are at least 10100,000. The other numbers = 1 and 5 mod 6 below 100 work.

    I found several dozen examples below 500, but have verified them to only to 1020,000.
  15. Dec 4, 2007 #14


    User Avatar
    Science Advisor
    Homework Helper

    My opinion, notwithstanding Xevarion's enlightened post, is that this is an example of Guy's strong law of small numbers. I don't think there are enough powers of 2 and 3 for this to work.

    Wait, that's an idea for a proof. There are more than n/3-2 numbers which are 1 or 5 mod 6 up to n, and less than (1 + log_2 n)(1 + log_3 n) pairs of powers of 2 and 3, respectively. Each pair may produce at most two distinct values, adding and subtracting. (There are three possibilities, a-b, b-a, and a+b, but one is nonpositive.) This sets a lower bound on the value of at least one set member. (1 + log_2 n)(1 + log_3 n) is bounded above by (log_2 n)^2 for n >= 32.

    Let's see... there are 2n numbers in the right residue classes up to 6n, so at least one of those must be greater than 2√2n. That at least shows how far you'd need to check. Using tighter bounds, to check up to 1000 at least one power must exceed 4,500,000; to check up to 5000 at least one power must exceed 1,000,000,000,000,000.

    Hmm, that's less impressive than I'd hoped.
  16. Dec 4, 2007 #15
    I haven't given this problem much though, but my initial reaction was:

    What about writing a number m (not divisible by 2 or 3) as an expansion of powers of 2, and then powers of 3?

    Every integer can be written as the sum of powers of 2, with coefficients being either 0 or 1; similarly, every integer can be written as the sum of powers of 3, with coefficients in {-1, 0, 1}.
  17. Dec 4, 2007 #16
    OK I think I have an idea for how to disprove this conjecture now. It could get a bit technical, though.

    CRGreathouse basically said that one must go to very large powers of 2 and 3 in order to make all of the numbers in a certain (relatively small) interval. We'd like to show that going to very large powers 'won't help'. So, let's consider the situation mod [tex]p[/tex], where [tex]p[/tex] is a very large prime number. Define [tex]A = \{2^m \pmod p | m \in \mathbb{N}\} \cup \{3^m \pmod p| m \in \mathbb{N}\}[/tex]. The objective would be to show that [tex]A-A[/tex] or [tex]A+A[/tex] or at least [tex]A + (A \cup -A)[/tex] (in the notation of my post above) is big (by which I mean [tex]cp[/tex] where [tex]c[/tex] is an absolute constant). But I don't think this can possibly be true every time...

    Basically all we need to show is that there exists some [tex]p[/tex] for which [tex]|A|[/tex] is not big, because [tex]|A+A| \le |A|^2[/tex]. In other words, we want that neither 2 nor 3 is a generator of the multiplicative group [tex](\mathbb{Z}/p\mathbb{Z})^\times[/tex]. Someone with a bit more NT knowledge want to help out here?

    I still think it may be possible for my arithmetic combinatorics techniques to apply here. My roommate wants me to go to lunch though so it'll have to wait for a bit... :P
  18. Dec 4, 2007 #17
    OK so it looks profitable to consider things mod 73. I found that
    [tex]A = \{1,2,4,8,16,32,64,55,37\}, B = \{1, 3, 9, 27, 8, 24, 72, 70, 64, 46, 65, 49\}[/tex]
    so [tex]A + B[/tex] is missing [tex]\{14, 20, 21, 22, 27, 30, 39, 42, 44, 49, 60, 70\}[/tex] and [tex](A-B) \cup (B-A)[/tex] is missing [tex]\{22, 51\}[/tex]. Thus [tex](A - B) \cup (B-A) \cup (A + B)[/tex] is missing 22, so it's impossible to make a number which is equivalent to 22 mod 73 as [tex]\epsilon_1 2^m + \epsilon_2 3^n, \epsilon_i = \pm 1[/tex]. The first example which is relevant (ie not divisible by 2 or 3) is of course 95.

    This agrees with CRGreathouse's numerical evidence (i.e. 95 was one of the ones that didn't have any solution with numbers less than [tex]10^{10^5}[/tex]).
    Last edited: Dec 4, 2007
  19. Dec 4, 2007 #18
    Some remarks:

    1) My observation about 'the general idea of arithmetic combinatorics' is not relevant in this case, because although [tex]A\cdot A = A[/tex] and [tex]B \cdot B = B[/tex], [tex]A \cdot B[/tex] is probably big so there's no reason to expect too much from [tex]A + B[/tex] or [tex]A-B[/tex].

    2) It's still possible to salvage the OP's idea in a couple of different ways.

    (i) One would be to ask what proportion of (1 and 5 mod 6) numbers can be made via the desired operation. I've shown that it's at most [tex]\frac{72}{73}[/tex] but I would guess it's actually much less than that. (I wouldn't even be surprised if the density of numbers which can be made in that way is [tex]o(N)[/tex].)

    (ii) Alternatively, one could try to use the idea I suggested (re: (1)) and see what happens if you add/subtract numbers of the form [tex]2^i3^j[/tex]. The Putnam problem I referred to earlier shows that even if you add an additional restriction on what sort of sums you're allowed to take, you can still get every number as a sum of some number of [tex]2^j3^j[/tex] (but the number required may be big, like to get all numbers up to [tex]N[/tex] you might need to do sums of about [tex]\log(N)[/tex] terms). Without the restriction from the Putnam problem, does the number of required terms go down? What's the optimal bound? Alternatively, what's the density of the set of numbers you can get by doing sums of just [tex]k[/tex] such terms?

    ps -- sorry for the triple post. :-p hopefully the fact that the posts all have actual useful content will redeem me? ;-)
  20. Dec 4, 2007 #19

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Since 2 is in A and 24 is in B, then (2-24)%73=51 is in A-B and 24-2=22 is in B-A. Those missing elements aren't missing.
  21. Dec 4, 2007 #20


    User Avatar
    Science Advisor
    Homework Helper

    Bravo, Xevarion! Excellent show, not too technical at all. I'm curious to see if anyone has a way to move forward on your suggestions for salvaging the conjecture, though I also suspect that the sequence is of density zero.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook