Nope, I've no idea how to formalize a proof. That half-baked algorithm is the best I can do. Anyone want to help?
Couple of random thoughts... Does the process produce the same solution if 2 and 3 are swapped? In the form given, all b_n must decrease but a_n must simply be > 0 for n > 1. Can we show that if a_n = 0 for n > 1 there is an alternate form that allows for a_n > 0?
So? All that is required is that the number in interest, call it n, be expressed as a sum of terms each of which is of the form 2[sup]a[/sup]3[sup]b[/sup] such that none of the terms in the sum divides another. The result is not necessarily unique. For example 19=16+3=9+6+4. The challenge is to prove that every positive integer can be expressed in this way. Hint: Start with 1=2[sup]0[/sup]3[sup]0[/sup].
Pete and I were both pointing out that his methodology would not produce 57=2*27+3. In order to fit the criteria that none of the terms divide any others, Pete correctly identified that the exponents of one factor must increase with each term while the exponents of the other factor must decrease with each term.
Your algorithm appears to work ... but can you prove it? If you use induction, even numbers are easy. Assume a solution exists for all integers between 1 and n, inclusive. If n is odd, n+1 is even. Dividing n+1 by two yields a number between 1 and n inclusive, so solution exist for (n+1)/2 by virtue of the induction assumption. Multiply each term of that solution by 2 and done. So all that remains is the case when n+1 odd. How does your post #117 help?
Swapping 2 and 3 in the attack not only produces different results (9+2 vs 8+3=11), it doesn't always work! (27+2 vs 16+8+4+1=29) This is surprising to me. Anyway I like your induction thoughts DH. I'm trying to shake off the cobwebs, I haven't dealt with math problems for a long time...
You are double-counting the $2 that the waiter is holding by saying that the friends paid it on their bill AND the waiter is holding it. $70 was paid on the bill, $2 is in the waiter's pocket, and $3 is in the friends' pockets which accounts for the full $75.
I hadn't thought of doing induction like that. I was trying to start from "assume a solution exists for n..." So. Here's the odd case. Apologies in advance for the awkward and amateurish exposition. Summary of proof: Assume solutions exists for all even integers between 1 and n inclusive. Select \(3^k\) to be a term in the solution of odd n+1, such that \(3^{k+1} \ > \ n+1 \ >= \ 3^k\), yielding a subsolution by induction. None of the terms in the subsolution divide \(3^k\). \(3^k\) doesn't divide any term in the subsolution. Therefore, a solution exists for odd n+1 More details of proof: Assume a solution exists for all even integers between 1 and n, inclusive, such that all terms in the solution are even. (This follows from the inductive proof for even numbers. It is also trivial to prove that any solution for an even numbers must have all even terms.) . Note that all terms in the solution of any n are less than or equal to n. . If n+1 is odd, then select \(3^k\) to be a term in the solution, such that \(3^{k+1} \ > \ n+1 \ >= \ 3^k\) . Subtracting this term from n+1 yields \(n+1 - 3^k\), an even number between 1 and n inclusive, for which a solution exists with all even terms (1). . Since all the terms in the solution of \(n+1 - 3^k\) are even (1), none divide \(3^k\), which is odd. . If an (even) term in the solution of \(n+1 - 3^k\) is a multiple of \(3^k\), it must be at least \(2 \times 3^k\) (1). . But, we chose k such that \(n+1 < 3^{k+1}\). (3) . Rearranging (7), we find \(n+1-3^k \ < \ 2 \times 3^k\) . Combining (2 and 8), we find that all terms in the solution of \(n+1-3^k\) are less than \(2 \times 3^k\) . (9) contradicts the conclusion of (6), implying by absurdity that the premise of (6) is false, i.e. that no term in the solution of \(n+1 - 3^k\) is a multiple of \(3^k\). . No term in the subsolution divides the new term (5). The new term does not divide any term in the subsolution (10). The new term is in the required form of \(2^a3^b\). (3) . QED!
I think that reversing the attack would mean first dividing by three as much as you can before subtracting powers of two, so it still works for 27. But, it doesn't work for 23 (16+4+3). This is because subtracting a power of 2 from a non-multiple of 3 isn't guaranteed to give you a multiple of 3, unlike the reverse case.
Longish, but correct enough. Erdős' solution: Assume a solution exists for all integers (1,2,... n-1). Split n into three cases: n is even. Then m=n/2 is an integer between 1 and n-1 inclusive. Since m is in (1,2,... n-1), a solution exists for m. Picking any of these solutions and doubling each term will yield a solution for n. n is of the form 3[sup]k[/sup]. This is a single term solution for n. n is odd and is not of the form 3[sup]k[/sup]. Find k such that 3[sup]k[/sup]<n<3[sup]k+1[/sup]. Since n and 3[sup]k[/sup] are odd, n-3[sup]k[/sup] is even. Let m=(n-3[sup]k[/sup])/2. Then 0<m<3[sup]k[/sup]<n, so m is in (1,2,... n-1): A solution exists for m. Pick any of these solutions, double each term, and add 3[sup]k[/sup] as a final term. This series will sum to n. None of the terms resulting from doubling the terms in the solution for m will divide one another, and since all are even, none will divide 3[sup]k[/sup]. Since 3[sup]k[/sup]>m, 3[sup]k[/sup] cannot divide any of the terms in the solution for m. Thus the constructed series is a solution for n. Since 1=2[sup]0[/sup]3[sup]0[/sup], a solution exists for n=1. By induction a solution exists for all positive integers.
I'm bumping old threads today. I got asked this in an interview yesterday: How many 6 digit numbers are there that contain the digits 24? The 2 and the 4 have to be consecutive. Hint: Spoiler There is 1 two digit number that contain the digits 24. There are 20 3 digit numbers that contain the digits 24. A similar and slightly harder question is, how many numbers that contain the digits 24 are there between 100000 and 999999.
Were they asking for an exact number or a quick, rough estimate? Off the top of my head, I'd say 50000: XXXX24 XXX24X XX24XX X24XXX 24XXXX Edit: I'm sorry, is it bad form to post my reasoning?
