Google Answers Logo
View Question
Q: Number game ( Answered 5 out of 5 stars,   0 Comments )
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:5 out of 5 stars
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:

          /   \
         /     \
        /       \
       /         \
      /           \
     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.


jiajia-ga rated this answer:5 out of 5 stars
Thank you so much for a great answer!

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy