An Interesting Question

[CRGreathouse]

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.

 

[Xevarion]

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 $$2^m$$ and $$3^m$$ 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 $$|A| = 12$$ and $$|B| = 6$$, because as I said before $$|A + B| \le |A||B|$$ (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 $$\mathbb{Z}/91\mathbb{Z}$$.

 

[D H]

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 $(A - B) \cup (B-A) \cup (A + B)$ 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 10^100,000. The other numbers = 1 and 5 mod 6 below 100 work.