Lattice Multiplication Method

In the Lattice Multiplication Method, a student is able to complete a multiplication problem of two large numbers by arranging numbers in a lattice grid.  For example, to multiply 48 x 12, the student would start out by creating a 2 x 2 lattice grid with the digits of 48 along the top as column headers, and the digits of 12 along the right side as row headers (Step 1).   The student would then multiply the digits in each column and row header and place each product in its corresponding position (using leading zeroes for single digit products), so in this case 4 x 1 = 04 (Step 2), 8 x 1 = 08 (Step 3), 4 x 2 = 08 (Step 4), and 8 x 2 = 16 (Step 5). 

Lattice Multiplication of 48 x 12

Finally, the student would add the digits along each diagonal, from the rightmost diagonal to the leftmost diagonal, and place each sum at the bottom left of each diagonal (carrying when necessary), so in this case 6 = 6 (Step 6), 8 + 1 + 8 = 17 which breaks down to 7 and a carried 1 (Step 7), 1 + 0 + 4 + 0 = 5 (Step 8), and 0 = 0 (Step 9).  The final answer can be determined by the right side column digits and the bottom row digits, in this case a final and correct answer of 576.  The Lattice Multiplication Method can also be extended to handle more digits by creating a larger lattice.

Lattice Multiplication Tutorial Video

The Lattice Multiplication Method is also known as Gelusia Multiplication, Sieve Multiplication, Shabakh, Venetian Squares, and the Chinese Lattice.  It is not known whether the method originated in Europe, the Middle East, or China, but it has been known since at least the 13^th century.

Validation

When it comes to multiplying two numbers of multiple digits, most people use the traditional Vertical Multiplication Method that is taught in most elementary schools.  For example, to multiply 48 x 12, the numbers are placed vertically, and the last digit of the top number is multiplied by the last digit of the second number to obtain 8 x 2 = 16, which is breaks down as 6 and a carried 1 (Step 1). 

Step 1	Step 2	Step 3	Step 4	Step 5
148         x 12               6	148         x 12            96	48         x 12            96            80	48         x 12            96          480	48         x 12            96     + 1480          576

Vertical Multiplication of 48 x 12

Then the first digit of the top number 4 is multiplied by the last digit of the second number 2 to obtain 4 x 2 = 8, plus the carried 1 makes 8 + 1 = 9, and so the first product is 96 (Step 2).  Then the last digit of the first number 8 is multiplied by the first digit of the second number 1 to obtain 8 x 1 = 8 and placed beside a place holder of 0 (Step 3).  Then the first digit of the first number 4 is multiplied by the first digit of the second number 1 to obtain 4 x 1 = 4, so the second product is 480 (Step 4).  The two products 96 and 480 are then added together to obtain the final answer of 96 + 480 = 576 (Step 5).

The Lattice Multiplication Method is simply a rearrangement of the same numbers in the Vertical Multiplication Method.  In the Lattice Multiplication Method, the digits of 48 and 12 are found in the top row and right column, and the digits in 96 and 480 are found inside the lattice (recall that the 9 was actually 8 and 1), and the digits of 576 are found in the left column and bottom row.

The Lattice Multiplication Method and the Vertical Multiplication Method both work for the same reason – the distributive property.  In both methods, the student multiplies 40 x 10, 40 x 2, 8 x 10, and 8 x 2 in some order and adds all the results together.  This is the algebraic equivalent of (40 + 8)(10 + 2) = 40·10 + 40·2 + 8·10 + 8·2 = 400 + 80 + 80 + 16 = 576, which is the same order as the popular FOIL method (first, outer, inner, last) taught in most algebra classes to show the distributive property.  In other words, the integrity of the multiplication is maintained because each digit of the first number is multiplied by each digit of the second number (with appropriate positioning to preserve place value) and then added all together.

Conclusion

The Lattice Multiplication Method is an algorithm for multiplying two large numbers by arranging numbers in a lattice grid.  Each digit of the two numbers are separated and placed as column and row headers, then the product of each column and row header is found and positioned inside the grid, and then the sum of each diagonal is found placed at the bottom left of each diagonal, and finally these sums can be read to obtain the solution.  Because each digit of the first number is multiplied by each digit of the second number (with appropriate positioning to preserve place value) and then added all together, it is a valid algorithm for multiplying two numbers.  The Lattice Multiplication Method is both organized and visually appealing, making it an ideal algorithm for multiplying two large numbers.

Japanese Multiplication Method

In the Japanese Multiplication Method, a student is able to complete a multiplication problem of two large numbers by merely drawing a few lines and counting the points of intersections.  For example, to multiply 21 x 23, the student first represents 21 by 2 diagonals lines that are drawn up and to the right followed by 1 diagonal line that is drawn in the same direction just underneath this, and then 23 by 2 diagonal lines that are drawn down and to the right followed by 3 diagonals lines that are drawn in the same direction just above this, so that the four groups of lines form a diamond shape. 

Japanese Multiplication of 21 x 23

The lines intersect in a total of 4 points on the left side of the diamond, a total of 8 points in the top and bottom sides of the diamond, and a total of 3 times on the right side of the diamond for a final and correct answer of 483.

The Japanese Multiplication Method can be extended to handle more digits by creating a larger diamond, and handle a digit of zero by drawing a different colored line.  In some cases, carrying is required in the final addition steps.

Japanese Multiplication Method Tutorial Video

Despite its name, the origin of the Japanese Multiplication Method is unknown.  The method is also known as Indian Multiplication and Chinese Stick Multiplication, but it is not known if it actually did originate from Japan, India, China, or elsewhere.

Validation

When it comes to multiplying two numbers of multiple digits, most people use the traditional vertical method that is taught in most elementary schools.  For example, to multiply 21 x 23, the numbers are placed vertically, and the last digit of the top number is multiplied by the last digit of the second number to obtain 1 x 3 = 3 (Step 1). 

Step 1	Step 2	Step 3	Step 4	Step 5
21         x 23               3	21         x 23            63	21         x 23            63            20	21         x 23            63          420	21         x 23            63      + 420          483

Vertical Multiplication of 21 x 23

Then the first digit of the top number 2 is multiplied by the last digit of the second number 3 to obtain 2 x 3 = 6, and so the first product is 63 (Step 2).  Then the last digit of the first number 1 is multiplied by the first digit of the second number 2 to obtain 1 x 2 = 2 and placed beside a place holder of 0 (Step 3).  Then the first digit of the first number 2 is multiplied by the first digit of the second number 2 to obtain 2 x 2 = 4, so the second product is 420 (Step 4).  The two products 63 and 420 are then added together to obtain the final answer of 63 + 420 = 483 (Step 5).

In summary, in the traditional vertical method a student first multiplies 1 x 3, then 20 x 3, then 1 x 20, then 20 x 20, and then adds all the results together.  In other words, when multiplying numbers with multiple digits, each digit of the first number is multiplied by each digit of the second number (with appropriate positioning or zeroes to preserve place value) and then added all together.  Algebraically, this can be expressed as (20 + 1)(20 + 3) = 3·1 + 20·3 + 1·20 + 20·20 = 3 + 60 + 20 + 400 = 483.  Tweaking the order a little bit gives the algebraic equivalent of (20 + 1)(20 + 3) = 20·20 + 20·3 + 1·20 + 1·3 = 400 + 60 + 20 + 3 = 483, which is the same order as the popular FOIL method (first, outer, inner, last) taught in most algebra classes. 

The same multiplication problem can be visualized with a table using Base Ten Blocks.  The 21 can be represented as 2 rod blocks and 1 unit block as row headers, and the 23 can be represented as 2 rod blocks and 3 unit blocks as column headers. 

Base Ten Block Multiplication of 21 x 23

The table would then be filled in by 4 square blocks (hundreds), a group of 6 rod blocks and another group of 2 rod blocks for a total of 8 rod blocks (tens), and 3 unit blocks (ones) for a final answer of 483.  Once again, each digit of the first number is multiplied by each digit of the second number (this time with appropriate shapes to preserve place value) and then added all together.

The Japanese Multiplication Method is simply a transformation of the Base Ten Block Table.  Instead of 4 square blocks there are 4 points of intersection on the left side of the diamond of lines, instead of a group of 6 rod blocks and a group of 2 rod blocks there are 6 points of intersection on the top side of the diamond of lines and 2 points of intersection on the bottom side of the diamond of lines, and instead of 3 unit blocks there are 3 points of intersection on the right side of the diamond of lines.  The integrity of the multiplication is maintained because each digit of the first number is multiplied by each digit of the second number (with appropriate positioning to preserve place value) and then added all together.

Because of its similarities with the FOIL method, it should be noted that the Japanese Multiplication Method can also be used to multiply polynomials.  The above Japanese Multiplication diagram that shows 21 x 23 = 483 can also be used to multiply (2x + 1)(2x + 3) and obtain the result 4x² + 8x + 3.  (The equation 21 x 23 = 483 is a specific example of (2x + 1)(2x + 3) = 4x² + 8x + 3 when x = 10.)

Evaluation

After watching the video and examining the above example, it is tempting to conclude that the Japanese Multiplication Method is the superior algorithm for multiplying two numbers.  After all, it just requires drawing a few lines and counting its intersections.  Unfortunately, the above example is a bit misleading because all of the numbers used have small digits (3 and under).  Here is an example of multiplying some numbers with larger digits, 69 x 78, using the Japanese Multiplication Method:

Japanese Multiplication of 69 x 78

In this example, a lot more lines have to be drawn, and a lot more points of intersection are formed.  Counting the points of intersection becomes time-consuming and carrying is required.  In this example, the Japanese Multiplication Method takes longer than the traditional vertical method of multiplication.

Still, the Japanese Multiplication Method is a great way to visualize the multiplication process, especially for numbers with smaller digits.

Conclusion

The Japanese Multiplication Method is an algorithm for multiplying two large numbers by representing both numbers by a group of lines that form a diamond pattern.  The number of points of intersection near each vertex of the diamond are then counted in a certain order to obtain the solution.  Because each digit of the first number is multiplied by each digit of the second number (with appropriate positioning to preserve place value) and then added all together, it is a valid algorithm for multiplying two numbers.  Unfortunately, the Japanese Multiplication Method is too time-consuming for multiplying numbers with larger digits, but remains a great visual aid for the multiplication process.

Perfect Numbers

A perfect number is a number which is equal to the sum of all its divisors less than itself.  For example, 6 is a perfect number because all of its divisors less than itself are 1, 2, and 3; and 1 + 2 + 3 = 6.  The number 28 is another perfect number because all of its divisors less than itself are 1, 2, 4, 7, and 14; and 1 + 2 + 4 + 7 + 14 = 28.

Another way to define a perfect numbers is to state that is a number whose sum of all of its factors (including itself) is equal to twice its value.  For example, 6 is a perfect number because all of its factors are 1, 2, 3, and 6; and 1 + 2 + 3 + 6 = 12, which is twice its value.  The number 28 is another perfect number because all of its factors are 1, 2, 4, 7, 14, and 28; and 1 + 2 + 4 + 7 + 14 + 28 = 56, which is also twice its value.

A visual representation of the perfect number 6

(from Wikipedia)

A computer can be used to quickly find other perfect numbers.  The following program goes through every integer (less than a user-defined integer), finds its factors, adds them up, and displays the ones that are perfect along with its factors:

01	# Perfect Numbers
02	# Python 2.7.3
03	# To find all perfect numbers less than n, type "perfects(n)".  For example,
04	#   to find all perfect numbers less than 1000, type "perfects(1000)".
05
06	# prints a string with a hanging indentation
07	import textwrap
08	def hprint(string):
09	print textwrap.fill(textwrap.dedent(
10	string).strip(), initial_indent = "", subsequent_indent = "  ")
11
12	# returns a list of factors of n
13	def factor(n):
14	arrFactors = []
15	# go through all the numbers < or = the square root of n
16	for i in range(1, int(n ** 0.5) + 1):
17	# if the numbers divides into n, add it to the list
18	if (n % i == 0):
19	arrFactors.append(i)
20	# it is different, add the other factor to the list, too
21	if (i != n / i):
22	arrFactors.append(n / i)
23	# return the sorted list
24	return sorted(arrFactors)
25
26	# returns the sum of all the factors of n
27	def o(n):
28	intO = 0
29	# get the factors of n
30	arrFactors = factor(n)
31	# go through all the factors and add them up
32	for i in range(0, len(arrFactors)):
33	intO += arrFactors[i]
34	# return the sum
35	return intO
36
37	# determines if n is a perfect number
38	def perfect(n):
39	# if sigma of n (the sum of the factors) equals 2n, then it is a
40	#  perfect number, so display it and its factors, and return True
41	if (o(n) == 2 * n):
42	hprint(str(n) + ": " + str(factor(n)))
43	return True
44	# if not, return False
45	else:
46	return False
47
48	# find all the perfect numbers less than n
49	def perfects(n):
50	# go through all the numbers between 1 and n and test them for being
51	#   a perfect number
52	for i in range(1, n):
53	perfect(i)

Typing in “perfects(10000)” results in all the perfect numbers less than 10,000, and there are only 4: 6, 28, 496, and 8128.

>> perfects(10000)

6: [1, 2, 3, 6]

28: [1, 2, 4, 7, 14, 28]

496: [1, 2, 4, 8, 16, 31, 62, 124, 248, 496]

8128: [1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064, 8128]

Amazingly, the Ancient Greeks knew about all 4 of these perfect numbers in an age without computers.  In fact, around 300 B.C. Euclid proved that if 2^p – 1 is prime, then 2^{p – 1}(2^p – 1) is a perfect number.  For example, 3 is a prime number for p = 2 (2^p – 1 = 2² – 1 = 3), so 2^{p – 1}(2^p – 1) = 2^{2 – 1}(2² – 1) = 2(3) = 6 is a perfect number.  Also, 7 is a prime number for p = 3 (2^p – 1 = 2³ – 1 = 7), so 2^{p – 1}(2^p – 1) = 2^{3 – 1}(2³ – 1) = 4(7) = 28 is a perfect number.  Euclid’s proof can be found here (Proof PNP01).

Euclid

Since many perfect numbers are in the form 2^{p – 1}(2^p – 1), the following functions can be added to improve the above computer program to test 2^{p – 1}(2^p – 1) as a perfect number for any given p value:

55	# determines if (2 ** (p - 1)) * (2 ** p - 1) is a perfect number
56	def pperfect(p):
57	if perfect((2 ** (p - 1)) * (2 ** p - 1)) == False:
58	return False
59
60	# find all the perfect numbers in the form of (2 ** (p - 1)) * (2 ** p - 1)
61	#   less than the given value of p
62	def pperfects(p):
63	# go through all the numbers between 1 and p and test
64	#   (2 ** (p - 1)) * (2 ** p - 1) for being a perfect number
65	for i in range(1, p):
66	pperfect(i)

Typing in “pperfects(25)” quickly gives 3 more perfect numbers 33,550,336 and 8,589,869,056 and 137,438,691,328:

>> pperfects(25)

6: [1, 2, 3, 6]

28: [1, 2, 4, 7, 14, 28]

496: [1, 2, 4, 8, 16, 31, 62, 124, 248, 496]

8128: [1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064, 8128]

33550336: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,

  8191, 16382, 32764, 65528, 131056, 262112, 524224, 1048448, 2096896,

  4193792, 8387584, 16775168, 33550336]

8589869056: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,

  8192, 16384, 32768, 65536, 131071L, 262142L, 524284L, 1048568L,

  2097136L, 4194272L, 8388544L, 16777088L, 33554176L, 67108352L,

  134216704L, 268433408L, 536866816L, 1073733632L, 2147467264L,

  4294934528L, 8589869056L]

137438691328: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,

  4096, 8192, 16384, 32768, 65536, 131072, 262144, 524287L, 1048574L,

  2097148L, 4194296L, 8388592L, 16777184L, 33554368L, 67108736L,

  134217472L, 268434944L, 536869888L, 1073739776L, 2147479552L,

  4294959104L, 8589918208L, 17179836416L, 34359672832L, 68719345664L,

  137438691328L]

Unfortunately, testing p ≥ 29 results in a “MemoryError” on my current personal computer, but supercomputers can be used to find more perfect numbers.

Euclid’s proof showed that perfect numbers are directly related to prime numbers in the form of 2^p – 1, and these prime numbers later became known as Mersenne primes, named after the French mathematician who studied them extensively in the 17^th century.  Over the years since, there have been many clever tricks developed to find larger and larger Mersenne prime numbers with the help of computers (see here for more details), and currently the largest known Mersenne prime is 2^74,207,281 – 1, a number with 22,338,618 digits!  According to Euclid’s proof, since 2^74,207,281 – 1 is a prime number, 2^74,207,280(2^74,207,281 – 1) must be a perfect number, currently making it the largest known perfect number, a number with 44,677,235 digits!

Mersenne

Interesting Facts

Here are some more interesting facts about perfect numbers:

-          Euler proved that all even perfect numbers must be in the form of 2^{p – 1}(2^p – 1) (Proof PNP02).

Euler

-          There are no known odd perfect numbers.  Computers have verified that there are no odd perfect numbers below 10¹⁵⁰⁰.

-          It is not known if there is an infinite number of perfect numbers.  (It is also not known if there is an infinite number of Mersenne primes.  Proving one would prove the other.)

-          All even perfect numbers (in the form of 2^{p – 1}(2^p – 1)) can be represented in binary as p ones followed by p − 1 zeros (Proof PNP03):

perf	binary
6	110
28	11100
496	111110000
8128	11111111000000

-          All even perfect numbers (in the form of 2^{p – 1}(2^p – 1))are the sum of all the integers from  1 to 2^p – 1 (also called 2^p – 1 triangular numbers) (Proof PNP04):

perf	Sum
6	1 + 2 + 3
28	1 + 2 + 3 + 4 + 5 + 6 + 7
496	1 + 2 + 3 + … + 29 + 30 + 31
8128	1 + 2 + 3 + … + 125 + 126 + 127

-          All even perfect numbers except for 6 (in the form of 2^{p – 1}(2^p – 1)) are the sum of the first 2^(p−1)/2 odd cubes (Proof PNP05):

perf	Sum
28	13 + 33
496	13 + 33 + 53 + 73
8128	13 + 33 + 53 + 73 + 93 + 113 + 133 + 153

-          All even perfect numbers except for 6 (in the form of 2^{p – 1}(2^p – 1)) are in the form of 1 + 9(T_(2^p-2)/3), where T_(2^p-2)/3 is the sum of all the integers from 1 to ^{2^p – 2} / ₃ (also called ^{2^p – 2} / ₃ triangular numbers) (Proof PNP06):

perf	sum
28	1 + 9(1 + 2)
496	1 + 9(1 + 2 + 3 + … + 8 + 9 + 10)
8128	1 + 9(1 + 2 + 3 + … + 40 + 41 + 42)

-          All even perfect numbers except 6 have a digital root of 1 (to find a digital root of a number, add the digits, then add the digits of the resulting number, then repeat the process until there is a single digit) (Proof PNP07):

perf	digit sum
28	2 + 8 = 10, 1 + 0 = 1
496	4 + 9 + 6 = 19, 1 + 9 = 10, 1 + 0 = 1
8128	8 + 1 + 2 + 8 = 19, 1 + 9 = 10, 1 + 0 = 1

-          The sum of reciprocals of all the divisors of every perfect number is equal to 2 (Proof PNP08)

perf	reciprocal sum
6	1/1 + 1/2 + 1/3 + 1/6 = 2
28	1/1 + 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 2
496	1/1 + 1/2 + 1/4 + … + 1/248 + 1/496 = 2
8128	1/1 + 1/2 + 1/4 + … + 1/4064 + 1/8128 = 2

                                                                                                                                            

-          Any number raised to a perfect number exponent is equal to the product of all its perfect roots.  For example, 6 is a perfect number, 2⁶ = 64, the perfect roots of 64 are ⁶√64 = 2, ³√64 = 4, and √64 = 8, and the product of 2, 4, and 8 is 2 ∙ 4 ∙ 8 = 64 (Proof PNP09).

perf	root product
6	6√x6 ∙ 3√x6 ∙ 2√x6 = x6
28	28√x28∙14√x28∙7√x28∙4√x28∙2√x28 = x28
496	496√x496∙248√x496∙…∙4√x496∙2√x496 = x496
8128	8128√x8128∙4064√x8128∙…∙4√x8128∙2√x8128 = x8128

-          All even perfect numbers end in 6 or 8 (Proof PNP10).  All even perfect numbers with more than 1 digit end in 16, 28, 36, 56, 76, or 96 (Proof PNP11).

perf	last digit	last 2 digits
6	6	n/a
28	8	28
496	6	96
8128	8	28

Related Concepts

Like perfect numbers, there are many other types of numbers defined by the sum of their divisors:

-          In the book Cutting for Stone by Abraham Verghese, one of the characters explains about a set of numbers whose sum of divisors is a perfect square:

“’Sixty-six is my second-favorite number,’ Shiva said. ‘Pray, why is it your second favorite?’ said Bailey. ‘Because if you take the numbers you can divide into sixty-six, including sixty-six, and add them up, what you have is a square.’ Mr. Bailey couldn't resist. He wrote down 1, 2, 3, 6, 11, 22, 33, and 66 – all the numbers that went into 66 – and then he totaled. What he got was 144, at which point both he and Shiva said, ‘Twelve squared!’ ‘That's what makes sixty-six special,’ Shiva said. ‘It's also true of three, twenty-two, sixty-six, seventy – their divisors add up to a square.’”

Cutting for Stone

-          An abundant number is a number in which the sum of all its divisors less than itself is greater than the number itself.  For example, 12 is an abundant number because its divisors less than itself are 1, 2, 3, 4, and 6; and 1 + 2 + 3 + 4 + 6 = 16 which is greater than 12.

-          A deficient number is a number in which the sum of all its divisors less than itself is less than the number itself.  For example, 8 is a deficient number because its divisors less than itself are 1, 2, and 4; and 1 + 2 + 4 = 7 which is less than 8.

-          Amicable numbers are a pair of numbers in which the sum of all the divisors less than itself of the first number is equal to the second number, and the sum of all the divisors less than itself of the second number is equal to the first number.  For example, 220 and 284 are amicable numbers because all of the factors less than itself of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, and 110; and  1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284; and all the factors less than itself of 284 are 1, 2, 4, 71, and 142; and 1 + 2 + 4 + 71 + 142 = 220.  Other amicable numbers include 1184 and 1210, 2620 and 2924, 5020 and 5564, 6232 and 6368, and many more.

Conclusion

Perfect numbers have a simple definition but a wealth of related facts.  Yet despite the plethora of postulates concerning perfect numbers, there is still much to prove, including whether or not an odd perfect number exists, and whether or not there is an infinite number of perfect numbers.  Hopefully these mysteries will inspire mathematical works in the future.

Many of the facts about perfect numbers presented in this article were inspired by information found at Wolfram Mathematics and Wikipedia.