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?

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

Thank you so much for a great answer!