Author |
Topic: As a sum of 2^a 3^b (Read 2043 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
As a sum of 2^a 3^b
« on: Jan 6th, 2012, 3:19pm » |
 Quote  Modify
|
Can you express the numbers 2011 and 2012 (separately) as a sum of 2^a 3^b, where a => 0 and b => 0 so that none of the summands divides another?
|
| « Last Edit: Jan 7th, 2012, 12:36am by Benny » |
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
playful
Junior Member
meet me at the second fork in the road
Gender:
Posts: 100
|
|
Re: As a sum of 2^a 3^b
« Reply #1 on: Jan 6th, 2012, 5:43pm » |
Quote Modify
|
Code:
Translating for those who don't have a table of html codes at their fingertips: a is superior or equal to zero (same for b).
Unless the code is part of the puzzle. 
|
|
IP Logged |
my favorite puzzles
|
|
|
playful
Junior Member
meet me at the second fork in the road
Gender:
Posts: 100
|
|
Re: As a sum of 2^a 3^b
« Reply #2 on: Jan 6th, 2012, 6:11pm » |
Quote Modify
|
I would say no.
| hidden: |
a and b are integers?
We are summing any number of numbers of the form 2^a or 3^b?
Unless I have misunderstood, I would say no.
1. Neither 2011 nor 2012 is a power of 2 or 3, so there must be more than one summand.
2. Suppose there are more than two summands. Then either two are of the form 2^x, and they necessarily divide each other; or two are of the form 3^x, and they necessarily divide each other. So there are two summands at the most, ie, 2 exactly.
3. Let's look at the two summands case. For the reason in (2) above, only a 3^a + 2^b scenario can work. For 3^a, there are only 7 possibilities for a: 0 through 6, because 3^6 is 729 and 3^7 is 2187.
Taking 2011 (or 2012) and subtracting each of these six 3^a candidates, we find numbers that are not of the form 2^x. This case fails. Hence my answer of no.
|
|
|
IP Logged |
my favorite puzzles
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: As a sum of 2^a 3^b
« Reply #3 on: Jan 7th, 2012, 12:38am » |
Quote Modify
|
2011 and 2012 as a sum of product 2^a 3^b, where a => 0 and b => 0
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
playful
Junior Member
meet me at the second fork in the road
Gender:
Posts: 100
|
|
Re: As a sum of 2^a 3^b
« Reply #4 on: Jan 7th, 2012, 4:45am » |
Quote Modify
|
Okay, let's start with 2011.
| hidden: |
We are summing elements of the form 2^a * 3^b.
1. a and b can never be zero together, as other summands will be divisible by 1.
2. Suppose a is zero at least once but b is never zero. Then each summand is a multiple of 3. 2011 is not a multiple of 3. That's out.
3. Suppose b is zero at least once but a is never zero. Then each summand is a multiple of two. 2011 is not divisible by 2. That's out.
So the answer for 2011 is no.
|
|
|
IP Logged |
my favorite puzzles
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: As a sum of 2^a 3^b
« Reply #5 on: Jan 7th, 2012, 12:19pm » |
Quote Modify
|
on Jan 7th, 2012, 4:45am, playful wrote:| So the answer for 2011 is no. |
|
Yet, by brute force:
20 36 + 21 35 + 22 34 + 23 33 + 28 30 = 729 + 486 + 324 + 216 + 256 = 2011
20 36 + 21 34 + 25 33 + 28 30 = 729 + 162 + 864 + 256 = 2011
20 36 + 21 34 + 25 31 + 210 30 = 729 + 162 + 96 + 1024 = 2011
20 35 + 23 33 + 24 32 + 27 31 + 210 30 = 243 + 216 + 144 + 384 + 1024 = 2011
20 35 + 23 34 + 25 33 + 28 30 = 243 + 648 + 864 + 256 = 2011
20 35 + 23 34 + 25 31 + 210 30 = 243 + 648 + 96 + 1024 = 2011
20 33 + 26 32 + 27 31 + 210 30 = 27 + 576 + 384 + 1024 = 2011
|
|
IP Logged |
|
|
|
playful
Junior Member
meet me at the second fork in the road
Gender:
Posts: 100
|
|
Re: As a sum of 2^a 3^b
« Reply #6 on: Jan 7th, 2012, 12:47pm » |
Quote Modify
|
Yep, my reasoning was completely wrong! 
|
| « Last Edit: Jan 7th, 2012, 12:51pm by playful » |
IP Logged |
my favorite puzzles
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: As a sum of 2^a 3^b
« Reply #7 on: Jan 7th, 2012, 1:19pm » |
Quote Modify
|
We can find
2012 = a*b - ac
E.g. 2012 = 2^2 * (2^9 - 3^2)
|
| « Last Edit: Jan 7th, 2012, 9:31pm by Benny » |
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: As a sum of 2^a 3^b
« Reply #8 on: Jan 7th, 2012, 1:20pm » |
Quote Modify
|
on Jan 7th, 2012, 12:19pm, pex wrote:
Yet, by brute force:
20 36 + 21 35 + 22 34 + 23 33 + 28 30 = 729 + 486 + 324 + 216 + 256 = 2011
20 36 + 21 34 + 25 33 + 28 30 = 729 + 162 + 864 + 256 = 2011
20 36 + 21 34 + 25 31 + 210 30 = 729 + 162 + 96 + 1024 = 2011
20 35 + 23 33 + 24 32 + 27 31 + 210 30 = 243 + 216 + 144 + 384 + 1024 = 2011
20 35 + 23 34 + 25 33 + 28 30 = 243 + 648 + 864 + 256 = 2011
20 35 + 23 34 + 25 31 + 210 30 = 243 + 648 + 96 + 1024 = 2011
20 33 + 26 32 + 27 31 + 210 30 = 27 + 576 + 384 + 1024 = 2011
|
|
Yep, this is what I had in mind
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: As a sum of 2^a 3^b
« Reply #9 on: Jan 7th, 2012, 1:30pm » |
Quote Modify
|
Here's another puzzle I found on another forum
http://perplexus.info/show.php?pid=7533
F(1) = 1, F(2) = 1 - 2, F(3) = 1 - 2 + 3, F(4) = 1 - 2 + 3 - 4,
F(5) = 1 - 2 + 3 - 4 + 5, F(6) = 1 - 2 + 3 - 4 + 5 - 6, etc.
If I do as follows
F(n) is (sum of n odd numbers) - (sum of even numbers)
I don't get what is required ??
|
| « Last Edit: Jan 7th, 2012, 9:30pm by Benny » |
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: As a sum of 2^a 3^b
« Reply #10 on: Jan 7th, 2012, 1:56pm » |
Quote Modify
|
on Jan 7th, 2012, 1:20pm, BenVitale wrote:| Yep, this is what I had in mind |
|
For what it's worth:
22 34 + 23 33 + 26 32 + 27 31 + 29 30 = 324 + 216 + 576 + 384 + 512 = 2012
22 35 + 24 33 + 25 32 + 26 31 + 27 30 = 972 + 432 + 288 + 192 + 128 = 2012
22 35 + 24 33 + 25 31 + 29 30 = 972 + 432 + 96 + 512 = 2012
22 35 + 24 32 + 27 31 + 29 30 = 972 + 144 + 384 + 512 = 2012
BenVitale, did you have a more elegant way of finding these solutions?
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: As a sum of 2^a 3^b
« Reply #11 on: Jan 7th, 2012, 2:17pm » |
Quote Modify
|
on Jan 7th, 2012, 1:56pm, pex wrote:
For what it's worth:
22 34 + 23 33 + 26 32 + 27 31 + 29 30 = 324 + 216 + 576 + 384 + 512 = 2012
22 35 + 24 33 + 25 32 + 26 31 + 27 30 = 972 + 432 + 288 + 192 + 128 = 2012
22 35 + 24 33 + 25 31 + 29 30 = 972 + 432 + 96 + 512 = 2012
22 35 + 24 32 + 27 31 + 29 30 = 972 + 144 + 384 + 512 = 2012
BenVitale, did you have a more elegant way of finding these solutions? |
|
More elegant? No.
I forgot to check your result to see if they satisfy the second condition, that is, the summands do not divide each other other.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
playful
Junior Member
meet me at the second fork in the road
Gender:
Posts: 100
|
|
Re: As a sum of 2^a 3^b
« Reply #12 on: Jan 7th, 2012, 2:25pm » |
Quote Modify
|
Quote:
Then imo this is more of a cs prob than a riddle... It could even be tagged [brute force] at the outset... but what do I know, you've been around a long time. It gave me pleasure anyway, so thanks for the problem.
|
| « Last Edit: Jan 7th, 2012, 2:26pm by playful » |
IP Logged |
my favorite puzzles
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: As a sum of 2^a 3^b
« Reply #13 on: Jan 7th, 2012, 2:38pm » |
Quote Modify
|
on Jan 7th, 2012, 2:17pm, BenVitale wrote:| I forgot to check your result to see if they satisfy the second condition, that is, the summands do not divide each other other. |
|
Don't worry  If you look at my solutions carefully, I ordered the summands with strictly increasing exponent of 2 and strictly decreasing exponent of 3. So, divisibility cannot occur.
on Jan 7th, 2012, 2:25pm, playful wrote:| Then imo this is more of a cs prob than a riddle... It could even be tagged [brute force] at the outset... but what do I know, you've been around a long time. It gave me pleasure anyway, so thanks for the problem. |
|
I agree.
|
|
IP Logged |
|
|
|
playful
Junior Member
meet me at the second fork in the road
Gender:
Posts: 100
|
|
Re: As a sum of 2^a 3^b
« Reply #14 on: Jan 7th, 2012, 2:49pm » |
Quote Modify
|
Quote:
For me, I just like having an expectation of what I'm diving into. If I feel like writing code, I'll head over to the cs board. (Not that all cs threads are about code.) If it's in the riddle board, then I assume there's a non computationally heavy answer, and I sharpen my pencil. That allows me to pass on types of problems I don't feel like investing time in. Everyone's different, though, and I don't mean to make a big deal out of it. Just wanting to share my perspective as a "riddle recipient".
|
|
IP Logged |
my favorite puzzles
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: As a sum of 2^a 3^b
« Reply #15 on: Jan 7th, 2012, 2:52pm » |
Quote Modify
|
on Jan 6th, 2012, 3:19pm, BenVitale wrote:| Can you express the numbers 2011 and 2012 (separately) as a sum of 2^a 3^b, where a => 0 and b => 0 so that none of the summands divides another? |
|
Actually --- are there any numbers that cannot be expressed in this way?
I don't know the answer to this question, but at least my brute force search led to solutions for every number up to 211 - 1 = 2047. (And 2048 is trivial, of course )
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: As a sum of 2^a 3^b
« Reply #16 on: Jan 7th, 2012, 6:47pm » |
Quote Modify
|
on Jan 7th, 2012, 1:30pm, BenVitale wrote:Here's another puzzle I found on another forum
http://perplexus.info/show.php?pid=7533
F(1) = 1, F(2) = 1 - 2, F(3) = 1 - 2 - 3, F(4) = 1 - 2 + 3 - 4,
F(5) = 1 - 2 + 3 - 4 + 5, F(6) = 1 - 2 + 3 - 4 + 5 - 6, etc.
If I do as follows
F(n) is (sum of n odd numbers) - (sum of even numbers)
I don't get what is required ??
|
|
a) your definition of F(3) appears to be wrong - it should be +3 rather than -3
b) you appear to have left out the actual question:
i) Solve (as generally as possible) for integers x,y so that: F(x)+F(y)+F(x+y)=2012
ii) Explain why no x,y satisfy: F(x)+F(y)+F(x+y)=2011
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: As a sum of 2^a 3^b
« Reply #17 on: Jan 7th, 2012, 7:31pm » |
Quote Modify
|
Given an integer write it in the form P+6*Q, where P is of the form: 2^N, 3^M, or 2^N+3^M. First try for the largest N you can, then the largest M that you can. Then express Q similarly, and so on until Q=0.
2^0=1 mod 6, and other even powers of 2 are 4 mod 6. Odd powers of 2 are 2 mod 6. All non-zero powers of 3 are 3 mod 6.
2011=1 mod 6, and largest N therefore needs to be an even number to make P=1 mod 6, so N=10. The largest M keeping 2^N+3^M <= 2011 is M=6. Thus,
2011 = 2^10 + 3^6 + 6*(43)
43 is 1 mod 6, so need an even power of 2, resulting in 43=2^4+3^3, giving
2011 = 20^10 + 3^6 + 2^5*3 + 2*3^4
2012=2 mod 6, so need an odd power of 2:
2012 = 2^9 + 6*250
250=2^6+6*31
31=2^2+3^3
resulting in 2012= 2^9 + 2^7*3 + 2^4*3^2 + 2^2*3^5
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: As a sum of 2^a 3^b
« Reply #18 on: Jan 7th, 2012, 9:33pm » |
Quote Modify
|
on Jan 7th, 2012, 6:47pm, rmsgrey wrote:
a) your definition of F(3) appears to be wrong - it should be +3 rather than -3
b) you appear to have left out the actual question:
i) Solve (as generally as possible) for integers x,y so that: F(x)+F(y)+F(x+y)=2012
ii) Explain why no x,y satisfy: F(x)+F(y)+F(x+y)=2011 |
|
A typo.
http://perplexus.info/show.php?pid=7533
F(1) = 1, F(2) = 1 - 2, F(3) = 1 - 2 + 3, F(4) = 1 - 2 + 3 - 4,
F(5) = 1 - 2 + 3 - 4 + 5, F(6) = 1 - 2 + 3 - 4 + 5 - 6, etc.
If I do as follows
F(n) is (sum of n odd numbers) - (sum of even numbers)
I don't get what is required ??
The questions:
(1) Determine the general form of two positive integers x and y that satisfy:
F(x) + F(y) + F(x+y) = 2012
(2) Can you explain why no positive integer solution exists whenever F(x) + F(y) + F(x+y) = 2011?
|
| « Last Edit: Jan 7th, 2012, 9:35pm by Benny » |
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: As a sum of 2^a 3^b
« Reply #19 on: Jan 9th, 2012, 6:57am » |
Quote Modify
|
Lemma
| hidden: | F(2n-1) = n
F(2n) = -n |
(proof, by induction, is trivial)
Writing G(x,y) = F(x) + F(y) + F(x+y):
| hidden: | G(2n-1,2m-1) = n + m - (n+m-1) = 1
G(2n,2m) = - n - m - (n+m) = -2(n+m)
G(2n-1,2m) = n - m + (n+m) = 2n
G(2n,2m-1) = 2m by symmetry |
G(x,y) = 2012 iff x=2011 and y is even or vice versa.
G(x,y) is never 2011 because it's either even or 1, while 2011 is odd and not 1
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print