mersenneforum.org Integers = sums of 2s and 3s.
 Register FAQ Search Today's Posts Mark Forums Read

 2010-07-20, 14:49 #1 3.14159     May 2010 Prime hunting commission. 24·3·5·7 Posts Integers = sums of 2s and 3s. I stumbled upon this one a while ago, as I posted elsewhere: Initially, I thought it was only the primes that could be decomposed into 2s and 3s. Then, I realized I could generalize this to all integers greater than 3. Here are some examples: 47 = 2(19) + 3(3) 79 = 3(17) + 2(14) 106 = 3(20) + 2(23) 189 = 2(60) + 3(23) Etc. Proving it might be an easy task. Tips? Also: Congrats to me on a Fermat prime post. (257) --> 2^(2^3)+1. Last fiddled with by 3.14159 on 2010-07-20 at 14:49
2010-07-20, 14:54   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

749610 Posts

Quote:
 Originally Posted by 3.14159 I stumbled upon this one a while ago, as I posted elsewhere: Initially, I thought it was only the primes that could be decomposed into 2s and 3s. Then, I realized I could generalize this to all integers greater than 3. Here are some examples: 47 = 2(19) + 3(3) 79 = 3(17) + 2(14) 106 = 3(20) + 2(23) 189 = 2(60) + 3(23) Etc. Proving it might be an easy task. Tips? Also: Congrats to me on a Fermat prime post. (257) --> 2^(2^3)+1.
Generalize:

Let m and n be elements of Z+ such that (m,n) = 1.

Ask yourself: What is the smallest integer M that is not
representable as mx + ny???

 2010-07-20, 15:06 #3 CRGreathouse     Aug 2006 5,987 Posts Searchbait: Sylvester, Frobenius, "happy meal"
2010-07-20, 15:17   #4
3.14159

May 2010
Prime hunting commission.

110100100002 Posts

Quote:
 Ask yourself: What is the smallest integer M that is not representable as mx + ny???
For x = 2; y = 3; I doubt that there are any counterexamples.

The only counterexample I've found is 1.

A probable counterexample is 4: 2+2, since there are no 3s in that decomposition.

It's looking like the counterexamples are powers of 2:
Let's test a few:
8 = 3(2) + 2
16 = 3(4) + 2(2).

Powers of 3:
9: 2(3) + 3
27: 3(5) + 2(6).

The only counterexamples I've found are {1, 4}.

However, when using larger integer pairs, it fails horrendously:
Let's use 6 and 7:
8 can't be represented as 6a + 7b
4 and 5:
10: 5+5
11: Cannot be expressed as 4a + 5b.

The only pair for which it works so well is 2 and 3 (Also 1 and 2, the best pair of all.)

2010-07-20, 15:21   #5
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by 3.14159 However, when using larger integer pairs, it fails horrendously: Let's use 6 and 7: 8 can't be represented as 6a + 7b
29 can't be represented, either. What about larger numbers?

2010-07-20, 15:22   #6
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2×7×461 Posts

Quote:
 Originally Posted by 3.14159 I stumbled upon this one a while ago, as I posted elsewhere: Initially, I thought it was only the primes that could be decomposed into 2s and 3s. Then, I realized I could generalize this to all integers greater than 3.
If it's even, it's a multiple of two; if you feel you need to have some threes in the mix, n-6 is a multiple of two plus 2*3

If it's greater than three and odd, then n-3 is a multiple of two.

This is not hard problem.

2010-07-20, 15:25   #7
3.14159

May 2010
Prime hunting commission.

24·3·5·7 Posts

Quote:
 If it's even, it's a multiple of two; if you feel you need to have some threes in the mix, n-6 is a multiple of two plus 2*3 If it's greater than three and odd, then n-3 is a multiple of two. This is not hard problem.
I wasn't stating that it was difficult. I was curious to know whether or not it was proven. It seemed interesting, is all.

2010-07-20, 15:26   #8
3.14159

May 2010
Prime hunting commission.

110100100002 Posts

Quote:
 29 can't be represented, either. What about larger numbers?
108: 7(12) + 6(4)
109: 7(7) + 6(10)
110: 6(2) + 7(14)
111: 6(15) + 7(3)
112: 6(14) + 7(4)
113: 7(5) + 6(13)

Etc. What's the final counterexample here?

Last fiddled with by 3.14159 on 2010-07-20 at 15:34

2010-07-20, 15:45   #9
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by 3.14159 What's the final counterexample here?
29.

Last fiddled with by CRGreathouse on 2010-07-20 at 15:45

2010-07-20, 16:18   #10
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts

Quote:
 Originally Posted by 3.14159 I wasn't stating that it was difficult. I was curious to know whether or not it was proven. .

But clearly not sufficiently curious to have done some work yourself
by using Google. You were given hints.

2010-07-20, 16:27   #11
3.14159

May 2010
Prime hunting commission.

110100100002 Posts

Quote:
 But clearly not sufficiently curious to have done some work yourself by using Google. You were given hints.
I actually did find it. Stop making false assumptions:
Here it is.

A better source.

Last fiddled with by 3.14159 on 2010-07-20 at 16:36

 Similar Threads Thread Thread Starter Forum Replies Last Post davar55 Puzzles 183 2019-12-12 22:31 TheMawn Other Mathematical Topics 4 2014-12-19 12:42 Microraptor Homework Help 10 2011-02-25 08:12 CRGreathouse Math 6 2009-11-06 19:20 TTn Math 2 2002-10-25 21:47

All times are UTC. The time now is 18:18.

Tue Nov 29 18:18:31 UTC 2022 up 103 days, 15:47, 0 users, load averages: 0.52, 0.87, 0.98