In early grades, students learn that a decimal integer is a sum of multiples of integer powers of 10. In this lesson, students are asked to interpret a numeral given in a base other than 10 as a sum of multiples of powers of that base,
b. Finally, students learn to use two methods for writing a given decimal integer in base
b.
Begin by reminding students what place value means, using an example. For example, the place value interpretation of 4273 is 4000 + 200 + 70 + 3, which is a sum of multiples of powers of 10. Note that 4000 = 4(103) is a multiple of a power of 10. Similarly, 2(102), 7(101), and 3(100) are multiples of powers of 10, too.
For students familiar with algebra tiles, the following diagram shows a physical representation of 4273.
When a number is expressed in a base other than b, the interpretation is similar. For convenience, assume that b = 6. The procedures outlined below will work no matter what the value of b is, but fixing the value of b makes the discussion much easier.
Next, show that base‑6 numerals can be interpreted in the same way as base 10 numerals. The notation 21136 is interpreted as a sum of multiples of powers of 6, just as 4273 was interpreted as a sum of multiples of powers of 10 above. The subscript 6 must be attached unless we are using base 10, because 10 is the default value of the base, by convention. Thus, 21136 = 2(63) + 1(62) + 1(61) + 3(60) = 477. Thus, 21136 is interpreted as 477. The reverse process—that of finding the base‑6 representation of an integer expressed in decimal notation—is harder but more interesting. There are two methods for completing such a conversion: (a) repeated subtraction and (b) repeated division. Each method has some advantages over the other.
Lead students through the processes of repeated subtraction and repeated division for converting the decimal number 477 to base‑6.
Repeated Subtraction
Make a list of all the (positive) integer powers of 6 that are less than the given number. For 477, the following powers are needed: 60 = 1, 61 = 6, 62 = 36, and 63 = 216. (Note that the next power of 6, 64 = 1296, is greater than 477.)
Next, as the name implies, repeatedly subtract the largest power of 6 that is less than or equal to the current number (which changes during the process). Performing the first subtraction, the amount remaining is 477 – 216 = 261. At this point, the current number is 261; because it is still larger than 63 = 216, repeat the process. Then, 477 – 2(216) = 45, so the current number becomes 45.
Now, because the current number is less than 63 = 216 but greater than 62 = 36, repeatedly subtract 36. This gives 45 – 36 = 9. Putting this together with the above result gives 477 = 2(216) + 1(36) + 9. As a sum of multiples of powers of 6, the remaining current number, 9, leads to 9 = 1(6) + 3(1).
Combining all of this work gives 477 = 2(63) + 1(62) + 1(61) + 3(60) = 21136. (This result agrees with the result above.)
At this point, ask each student to pick a three‑digit decimal number. Then ask them to use repeated subtraction to find its base‑6 representation. Finally, they should expand their numeral to get back the original three‑digit decimal number. An alternative approach would be to have students work in pairs to find the base‑6 representation. Once they have the representation completed, they can exchange their answer with another pair of students and interpret the base‑6 numeral they receive back into its original three‑digit decimal representation.
Repeated subtraction has two advantages over the method of repeated division. First, it is closely related to the definition, hence it leads to a better conceptualization. Second, it can be used in other situations when repeated division cannot, as in the case of Fibonacci representation (explained below).
Repeated Division
The process of repeated division requires continual division by the base, b, and interpreting the results.
When 4273 is divided by 10, the remainder is 3, which is the units digit of 4273. The integer quotient of that division is 427; and if 427 is then divided by 10, the remainder is 7, which is the tens digit of 4273.
In the same way, repeated division enables an integer to be expressed as the sum of multiples of powers of b, where b is an integer. In fact, the process even works when b is negative.
Using the repeated division algorithm for our example above, first divide 477 by 6. This gives a quotient of 79 with a remainder of 3. In other words, 477 = 6(79) + 3. (Notice that the remainder can never exceed 5, since in such a case the quotient would have been larger.) Next, divide the quotient by 6, and record the new quotient and remainder. Thus, 79 = 6(13) + 1. Repeat the process: 13 = 6(2) + 1, and finally 2 = 6(0) + 2. Writing the remainders in reverse order gives the base‑6 representation of 21136.
To further illustrate the process, consider the following example.
To see why 477 = 21136, repeatedly replace each quotient with its value obtained during the division process. Consequently,
| 477 | = | 6(79) + 3 |
| | = | 6(6(13)+1) + 3 |
| | = | 6(6(6(2) + 1) + 1) + 3 |
| | = | 6(6)(6)(2) + 6(6)(1) + 6(1) + 3 |
| | = | 2(63) + 1(62) + 1(61) + 3(60) |
| | = | 21136 |
The advantage of repeated division over repeated subtraction is that it is computationally more efficient. Also, the method of justification can be applied in other situations, such as synthetic division and the Euclidean algorithm.
At this point, ask each student to pick a three‑digit number. Then ask them to use repeated division to find the base‑6 representation. Finally, they should expand their numeral to get back the original three‑digit decimal number. An alternative approach would be to have students work in pairs to find the base‑6 representation. Once they have the represenation completed, they can exchange their answer with another pair of students and interpret the base‑6 numeral they receive back into its original three‑digit decimal representation.
Technology Help
The following applet can be used to convert between bases. In the classroom, you can display this applet and use it to verify student answers.
Alternatively, the following program for the TI-83+ graphing calculator will convert any number from base‑10 to base b, where 2 ≤ b ≤ 9. The program can be downloaded to student calculators, or you can download it to a calculator with projection capabilities and display the results on the overhead projector.
Next ask the students to complete the Binary Representations Activity Sheet.
This page contains all the binary representations of the numbers 0 through 31 and can be completed individually, although allowing students to work in groups will reduce errors as well as decrease the time required for completion. Ask students to compare the left and right sides of the page for similarities. Consider the pattern of 0’s and 1’s in each column. Students may notice the following:
- In the rightmost column (1), the 0’s and 1’s alternate.
- In the next column (2), the pattern is two 0’s, two 1’s, two 0’s, two 1’s, and so on.
- In the next column (4), the pattern is four 0’s, four 1’s, four 0’s, four 1’s, and so on.
- In the next column (8), the pattern is eight 0’s, eight 1’s, eight 0’s, eight 1’s, and so on.
- The left-most column (16) contains 0’s along the left side of the table and 1’s on the right side of the table.
To see these patterns, you may wish to view the solutions
to the activity sheet.
At this point students should be able to complete the Place Value Activity Sheet questions 1‑4. Challenge questions are also available at the end of the activity sheet.
Note: Prior to beginning the lesson, you may wish to review the
solutions.
Fibonacci Representation
Just as every positive integer can be expressed as a sum of distinct powers of 2, 6, or 10, every integer can also be expressed as a sum of Fibonacci numbers.
Although this can be done in several ways, the method for this lesson is known as a greedy algorithm. It’s called "greedy" because at each stage, the largest possible number is chosen.
This method is based on the method of repeated subtraction. To represent a number N, pick the largest Fibonacci number not exceeding N, then subtract it and continue with the difference. For example, consider N = 100. The largest Fibonacci number less than 100 is 89, so subtract 89. The result is 100 – 89 = 11. Because 11 is less than the Fibonacci numbers 55, 34, 21, and 13, they cannot be subtracted. The next Fibonacci number that can be subtracted is 8, and 11 – 8 = 3. Because 3 is a Fibonacci number, the subtraction is complete.
To interpret the results, write the original number as a sum of Fibonacci numbers:
100 = 1(89) + 0(55) + 0(34) + 0(21) + 0(13) + 1(8) + 0(5) + 1(3) + 0(2) + 0(1)
= 1000010100f
Practice this with your students by asking them to convert back and forth, making sure that you get back the number with which you started.
In addition, counting in Fibonacci is something all students should eventually be able to do: 1, 10, 100, 101, 1000, 1001, 1010, 10000, …. (Note that counting in Fibonacci numbers is the next-to-last question on the activity sheet.) Students should also think about why Fibonacci representations never have two consecutive 1’s, no matter what integer is represented.
In another lesson in this unit, the Fibonacci representation is used to provide a strategy for playing a variation of the game Nim.
