An Interesting Question

  • Thread starter approx
  • Start date
  • #26
CRGreathouse
Science Advisor
Homework Helper
2,820
0
Xevarion's technique seems to work with 683.
Funny, I was just about to post the same thing.

And yes, composites do seem to work better -- I'll check that one, Xev.
 
  • #27
76
0
Just for other readers -- the reason that composites work better is that the order of 2 and 3 tends to be smaller mod a composite. Basically, we want there to be very few possible residues for [tex]2^m[/tex] and [tex]3^m[/tex] mod N. The way I picked 91 was by going to the list of integer sequences and finding the lists for the multiplicative order of 2 mod N and the same for 3. Then I went along the two lists until I found an N where both numbers were small (in this case, 6 and 12). We know that we can't make much stuff if [tex]|A| = 12[/tex] and [tex]|B| = 6[/tex], because as I said before [tex]|A + B| \le |A||B|[/tex] (and similarly A-B and B-A). So A+B can't possibly hit everything -- even if there's no duplication, we can only make 72 different residues mod 91 by adding a power of 2 to a power of 3. For differences, we had to hope that there was a lot of overlap, but we'd expect the set of powers of 2 and 3 to be essentially random and independent mod a large number (from the perspective of how often you get repeated differences). In modern jargon, the additive energy of A and -B is about what you'd expect for random subsets of [tex]\mathbb{Z}/91\mathbb{Z}[/tex].
 
  • #28
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
Anyone who can program (DH?) want to check my work for me? I did this all by hand...
Ouch. By hand!?! You did fine this time.

I realized you could even look at multiples of 2 (or 3) as moduli (spelling?). In case of multiples of 2 (or 3), multiples of 2 (or 3) have to be removed from the complement of [itex](A - B) \cup (B-A) \cup (A + B)[/itex] because we don't care about these values. With that, the non-multiples of 2 or 3 less than 100 that are in the complement of the reachable numbers modulo some integer p<=999 (or p<=133, for that matter) are 53, 71, and 95.

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.
 
Last edited:

Related Threads on An Interesting Question

  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
890
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
15
Views
2K
  • Last Post
2
Replies
28
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
2
Views
25K
Replies
6
Views
477
Replies
6
Views
6K
Replies
1
Views
4K
Top