- #1

- 42

- 0

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

Approx

- Thread starter approx
- Start date

- #1

- 42

- 0

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

Approx

- #2

- 15,393

- 685

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

- #3

- 42

- 0

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.

- #4

- 76

- 0

Anyway it's just an idea. This problem doesn't seem trivial.

- #5

- 42

- 0

- #6

- 76

- 0

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:

3-2=1

9-4=5

9-2=7

27-16=11

16-3=13

81-64=17

27-8=19

27-4=23

27-2=25

32-3=29

I can't figure out how to do 31. I'm having trouble with some of the ones after it too, actually.

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:

3-2=1

9-4=5

9-2=7

27-16=11

16-3=13

81-64=17

27-8=19

27-4=23

27-2=25

32-3=29

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:

- #7

- 15,393

- 685

[tex]31=2^5-3^0[/tex]I can't figure out how to do 31. I'm having trouble with some of the ones after it too, actually.

- #8

- 179

- 2

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]31=2^5-3^0[/tex]

[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]

- #9

- 76

- 0

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.

- #10

- 42

- 0

well, we can fix the problem with 31 and 35 if we allow addition,

27+4

27+8

and thanks for the link and idea, I've only got a minute, but I'll check it out a little later.

27+4

27+8

and thanks for the link and idea, I've only got a minute, but I'll check it out a little later.

Last edited:

- #11

- 76

- 0

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

- #12

- 42

- 0

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

....Huh?

BTW, using plus or minus was part of the original conjecture, but I am curious whether plus is needed.

- #13

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

I have trouble with 53, 71, and 95. If the conjecture holds for these numbers, then the constituent powers are at least 10

I found several dozen examples below 500, but have verified them to only to 10

- #14

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

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

Hmm, that's less impressive than I'd hoped.

- #15

- 179

- 2

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

- #16

- 76

- 0

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

- #17

- 76

- 0

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

[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:

- #18

- 76

- 0

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. hopefully the fact that the posts all have actual useful content will redeem me? ;-)

- #19

- 15,393

- 685

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.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) \cup (B-A)[/tex] is missing [tex]\{22, 51\}[/tex].

- #20

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

Absolutely.hopefully the fact that the posts all have actual useful content will redeem me? ;-)

- #21

- 76

- 0

- #22

- 15,393

- 685

Xevarion's technique seems to work with 683. The "missing" numbers modulo 683 are {20, 32, 34, 46, 58, 70, 86, 87, 93, 117, 124, 133, 138, 147, 150, 151, 153, 157, 159, 160, 163, 166, 167, 171, 173, 178, 181, 182, 190, 206, 207, 213, 214, 215, 216, 223, 250, 278, 287, 298, 299, 306, 322, 330, 353, 361, 377, 384, 385, 396, 405, 433, 460, 467, 468, 469, 470, 476, 477, 493, 501, 502, 505, 510, 512, 516, 517, 520, 523, 524, 526, 530, 532, 533, 536, 545, 550, 559, 566, 590, 596, 597, 613, 625, 637, 649, 651, 663}. 133 is the first that is neither a multiple of 2 or 3.

Edit:

Now it might be my turn to be speaking too soon. My little perl script coughed up something completely different for 1093 and 1181.

Edit:

Now it might be my turn to be speaking too soon. My little perl script coughed up something completely different for 1093 and 1181.

Last edited:

- #23

- 15,393

- 685

Now, 133 mod 73 is 60. If I understand Xevarion's technique correctly, just because 60 is not in the (empty) "not represented" list for 73 does not mean that a solution exists for 133. It just means a solution might exist. On the other hand, because 133 and 151 and ... are in the "not represented" list for 683 means that there is no solution of the desired form for 133 (or 151, or ...). So that fact that 133 (or 151, or ...) do not turn up in the "not represented" lists for 1093 and 1181 does not mean that a solution exists for 133.

- #24

- 42

- 0

Thanks so much for all the help, I haven't time to read it all right now, but I'll look it over as soon as possible. It looks promising. Meanwhile, I have a more general conjecture which might avoid some of the problems of not having enough low exponents to account for all primes, by giving us more equations to work with. As it is a separate conjecture, I am going to put it into its own thread. See what you think.

approx

- #25

- 76

- 0

[tex]A = \{1, 2, 4, 8, 16, 23, 32, 37, 46, 57, 64, 74\}[/tex]

[tex]B = \{1, 3, 9, 27, 61, 81\}[/tex]

So [tex](A - B) \cup (B - A)[/tex] is missing [tex]\{6, 9, 16, 21, 27, 39, 40, 41, 50, 51, 52, 64, 70, 75, 82, 85\}[/tex]. It's possible I have arithmetic errors again and some of this isn't right, but there are so many that I can't believe all of them are wrong...

And [tex]A + B[/tex] is missing a lot, I got [tex]\{1, 8, 12, 14, 15, 18, 20, 21, 23, 30, 37, 39, 42, 45, 48, 51, 52, 53, 56, 57, 61, 68, 70, 71, 72, 74, 76, 78, 79, 80, 81, 86, 87, 88, 90\}[/tex].

In all, it appears we can never make any number equivalent to 21, 39, 51, 52, or 70 mod 91 by adding or subtracting powers of 2 and 3. So the smallest number (1 or 5 mod 6) that we can't make (according to this computation, not the smallest possible overall) is 143.

Anyone who can program (DH?) want to check my work for me? I did this all by hand...

- Last Post

- Replies
- 7

- Views
- 3K

- Last Post

- Replies
- 1

- Views
- 891

- Last Post

- Replies
- 8

- Views
- 2K

- Last Post

- Replies
- 15

- Views
- 2K

- Last Post

- Replies
- 28

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 2K

- Replies
- 2

- Views
- 25K

- Last Post

- Replies
- 6

- Views
- 478

- Replies
- 6

- Views
- 6K

- Replies
- 1

- Views
- 4K