This assignment is worth 50 points (5.0% of the course grade) and must be completed and turned in before 11:59pm on Monday, March 12 2018. That's two weeks because of Spring Break. You have a week to do the project before you go, so we recommend that you get it done before the break. There will be no extensions to the day the project is due (it's due the Monday after you return from Spring Break). Background, Fibonacci Sequence You probably have all seen, or at least heard about, the Fibonacci sequence, named after Italian mathematician Leonardo of Pisa, known as Fibonacci. It is a sequence based on a starting set of numbers and a way to calculate subsequent numbers The starting sequence for the Fibonacci numbers requires m seed numbers, typically 1 and 1 (though there is some variation if you look at the web page https:len.wikipedia.org/wiki Fibonacci number). All subsequent numbers are based on the sum of the nwo (which is important for our purposes, see below) previous numbers. It is often written as a recurrence relation: = Fn-1 + Fn-2 Thus the Fibonacci sequence is: 1, 1,2, 3, 5, 8, 13, 21, 34, 55, 89, 144. where the seed numbers required to start the sequence are marked in bold. That is, the seed numbers are required to be present before the calculations can begin. Fibonacci n-step sequences But why should we restrict ourselves to 2-sceds and the sum of the 2-previous numbers. Why not 3, 6, 9 ctc? Sure, why not. We can generalize to Fibonacci n-step numbers where n represents both the number of seeds required and the number of previous values that are added to create the next number in the sequence. Here are some examples 112358 1321 34 55 89 144 233 377 610 11 24713 24 44 81 149 274 504 927 1705 3136 11 2 4 8 15 29 56 108 208 401 773 1490 28725536 11 24816 31 61 120 236 464 912 1793 3525 6930 11248 16 3263 125 249 492 976 1936 3840 7617 11 24816 3264 127 253 504 1004 2000 3984 7936 1124816 32 64 128 255 509 1016 2028 4048 8080 1124816 32 64 128 256 511 1021 2040 4076 8144 11248 16 32 64 128 256 512 1023 2045 4088 8172 10 The numbers in bold italics are the seed numbers required to start the sequences. Thus for n=5, we require 5 seeds, each of which is the sum of all the previous numbers, starting with 1, 1. For n-5, that gives 1, 1, 2, 4, 8 where, for example, 8 is the sum of all the previous numbers 1,1,2,4) After that, the sequence continues by providing each subsequent number based on the sum of the 5 previous numbers. For n=5, the lon number (index 9) is 236, the sum of 8+16+31+61+1 20 (the 5th 6th, 7th, 8t,9th numbers in the sequence). Fibonacci number encoding There is a encoding of numbers called a Fibonacci coding ), which is a way to encode an integer as a binary number based on the Fibonacci sequence. The Fibonacci sequence (and, as it turns out, all Fibonacci n-step sequences) is complete, which means that any integer can be represented as a sum of some combination of the numbers in a Fibonacci (or Fibonacci n-step) sequence. A binary code of a number is therefore a string where the I's in the string indicate which elements are being used. Note, we ignore the index 0 number(1), as it is repeated at index 1(1) For example, for Fibonacci sequence (n=2), we have the following: 10 11 index 0 I Fib val 5 89 144 A nstep encoding (for n-2) of the number 100 would be: 0010100001 index 0 bit 2 3 45 6789 Which represents adding the index:3 (3), index:5 (8) and index:10 (89) numbers to form 100, which it does. Notice that a trailing 0 (for the index 0) is not relevant and is consequently It's a backwards encoding