## Pages

Showing posts with label algorithms. Show all posts
Showing posts with label algorithms. Show all posts

## Thursday, April 24, 2008

### Box multiplication

The box multiplication technique is suitable for people that has problem with numbers, since it will organized all the number in place.

Example 1:

13 × 23 = 299 First, draw a box for each number. Divide each box diagonally, with a straight line. Then multiply diagonally to the right. For example, 3 × 2 = 6. Put 0 inside the left triangle and 6 inside the right triangle, and so on.

After we have fill in all the numbers inside the triangle, add all the numbers diagonally to the left. For example 6 + 0 + 3 = 9, 0 + 2 + 0 = 2. Write the addition at the end. Follow the arrow.

Example 2:

79 × 85 = 6715 In this example, when we add 2, 4 and 5, we get 11. So, we write 1 and carry 1 (just write it in bracket). Next, when we want to add 7, 6 and 3, add the carry number as well. So, it will become 7 + 6 + 3 + 1 = 17. The same thing goes here. Write 7 and carry 1. The last one is 5 + 1 = 6.

note: The box multiplication technique could also be applied to the numbers that are more than two digits, such as 234 × 346 and 342 × 34.

## Wednesday, April 16, 2008

### Problem #1 of Project Euler

Add all the natural numbers below 1000 that are multiples of 3 or 5.

### Analysis:

Sequence of multiple of 3: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ..., 999

Sequence of multiple of 5: 5, 10, 15, 20, 25, 30, ..., 995 So, the sum is 3 + 5 + 6 + 9 + 10 + 12 + 15 + 18 + ... + 999.

Take note that we have to remove the duplicate of 15, 30, 45, ..., 990

### Method # 1: using Python

All the natural numbers below 1000 that are multiples of 3 or 5, are divisible by either 3 or 5. Hence, we need to add the numbers that are only divisible by 3 or 5. That is very easy in Python. Using the % operator will give use the remainder of the division.

For example, 4%2 = 0, 4%3 = 1. Therefore, in order to ad the number that is divisible by 3 or 5, we have to check for the remainder. We will only add the numbers that give zero for the remainder.
total = 0
for i in range(1000):
if not (i % 3 and i % 5):
total += i

### Method # 2: using Arithmetic sequence

To add all natural numbers from 1 to 10.

Notice that the sum will always gives 11, if we write it this way. 11 occurs 10 times, so, 11 x 10 = 110. However, that is the sum of 1 to 10 twice. So, we divide 110 by 2, we get the answer, which is 55.

The formula: Sum = n (a1 + a2) / 2 where n is the number of occurrence of the sequence from a1 to a2.

Back to our problem, the sum of 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ..., 999. Adding the first and last numbers gives us 3 + 999 = 1002. 1002 occurs 333 times, so 1002 * 333 = 333666. Divide it by 2, we get 166883.

Repeat the same procedure for the second sequence of 5s. Then, add the answers. However, as I mentioned previously, remember that we also have to remove the duplicates of 15, 30, 45, ..., 990.

The formula would be like this:

sum of multiple of 3 + sum of multiple of 5 - sum of multiple of 15