 View Question
Q: Number game ( Answered ,   0 Comments ) Question
 Subject: Number game Category: Science > Math Asked by: jiajia-ga List Price: \$3.00 Posted: 10 Jul 2006 14:40 PDT Expires: 09 Aug 2006 14:40 PDT Question ID: 745073
 ```How many positive integers less than 20 are equal to the sum of a positive multiple of 3 and a positive multiple of 4? I know the answer is 7, 10, 11, 13, 14, 15, 16, 17, 18, 19. So there are 10 of them. I got this result by calculating all the positive integers less than 20 one by one. What I want to know is if there is a faster or smarter algorithm to solve this problem rather than calculating the number one by one?``` Subject: Re: Number game Answered By: efn-ga on 10 Jul 2006 23:19 PDT Rated: ```Hi jiajia, Yes, it is possible to improve on brute force with this problem. You can consider the solution numbers as forming a tree you can search. In this case, the tree would look like this: 7 / \ / \ / \ / \ / \ 10 11 / \ / \ 13 14 14 15 / \ / \ / \ / \ 16 17 17 18 17 18 18 19 By the problem statement, the lowest number must be 7, and all other numbers can be derived by adding some number of 3s and 4s. So at each node of the tree, the left branch has the number you get by adding 3 and the right branch has the number you get by adding 4. 3 + 4 = 4 + 3, so starting at the third level of the tree, where there have been two additions, you get duplicate numbers. You could improve the tree searching algorithm to avoid generating those duplicate numbers. Furthermore, you can prove that when a level contains a continuous sequence of integers and the difference between the first number x and the last number y in the level is at least 2, the next row will contain all the numbers from (y + 1) to (y + 4). This makes it unnecessary to search the fourth level of the tree at all. Because the third row contains 13, 14, and 15 and 15 - 13 >= 2, the fourth row must contain 16 through 19, and by extension, all positive integers greater than 15 can be expressed as the sum of some number of 3s and some number of 4s. I hope this explanation is helpful. If you need more details, please ask for a clarification and I will explain further. Regards, --efn```
 jiajia-ga rated this answer: `Thank you so much for a great answer!`  