Number Representations

  • Number Representations

    Fibonacci Nim
    Grade: High School
    Periods: 2
    Author: Harold Reiter

    Instructional Plan

    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.

    2392 base fib

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

    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.

     TI-83+ Base Converter

    Next ask the students to complete the Binary Representations Activity Sheet.

    pdficonBinary 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.

    pdficonBinary Representations Answer Key

    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.

    pdficonPlace Value Activity Sheet

    Note: Prior to beginning the lesson, you may wish to review the solutions.

    pdficonPlace Value Answer Key

    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.

    Assessments and Extensions

    Assessment Options

    1. Assign Questions 1‑4 on the first day of the lesson. Questions 5‑8 can be assigned as homework after the second day of the lesson.
    2. Ask students to describe the repeated subtraction and repeated division algorithms to a neighbor. Then, have each student write a paragraph about why these algorithms work, either as a journal entry or as an informal assignment.

    Extensions

    1. Build the addition and multiplication tables for base‑6 arithmetic.
    2. Convert the 2006 from base 10 to base ‑6. Hint: Be careful with odd exponents.
    3. Move on to the next lesson, Static Nim.
     

    Questions and Reflections

    Questions for Students

    1. If you wish to convert a number, n, from base 10 to base b by the repeated subtraction method, the first p powers of b are needed. Write an inequality involving n, b and p that can be used to identify the maximum value of p that will be needed.

    [If bp < n < bp + 1, then the maximum power of b that is needed for the repeated subtraction method is p.]

    2. When using the repeated division algorithm, why can't the remainder exceed the divisor d?

    [If the remainder was larger than the divisor, it means the quotient was not corect and that more groups of size d can be removed from the dividend.]

    3. What advantage does repeated division have over repeated subtraction for converting a number to another base?

    [Repeated division is computationally more efficient.]

    4. Why will a Fibonacci representation never contain two consecutive 1’s?

    [The nature of the Fibonacci pattern is that each number is equal to the sum of the two previous numbers. Consequently, two consecutive 1’s should be replaced by 0’s, and the next larger place value should increase by 1. For instance, the incorrect Fibonacci representation 110 can be interpreted as the decimal sum 3 + 2 + 0 = 5; but since 5 is a Fibonacci number, this should instead be represented as 1000.]

    Teacher Reflection

    • Why should students practice interpreting numerals as sums of multiples of powers of 10?
    • Were students challenged by the activities in this lesson? How could you make the activities less challenging for those who struggled, or more challenging for those who did well?
    • Did you make any adjustments while teaching the lesson? If so, were they effective?



    Objectives and Standards

    Learning Objectives

    Students will:

    • Find the base b representation of a given integer.
    • Interpret a numeral whose base b representation is given.
    Common Core State Standards – Mathematics

    6th to 8th

    • Grade 6
      • CCSS.Math.Practice.MP8
        Look for and express regularity in repeated reasoning.

    9th to 12th

    • Number & Quantity
      • CCSS.Math.Content.HSN-VM.C
        Perform operations on matrices and use matrices in applications.
    Common Core State Standards – Practice
    • CCSS.Math.Practice.MP8
      Look for and express regularity in repeated reasoning.

    Related Resources

    Unit Icon

    Fibonacci Nim

    Grade: High School

    Represent numbers in other bases and convert to and from decimal representations, and then, learn how to play Static Nim.  

    2398icon

    Static Nim

    Number and Operations

    Grade: High School

    Analyze nim games for winning strategies.

    Optimal Strategies

    Number and Operations

    Grade: High School

    Determine the optimal strategy for dynamic one-pile nim.