The 1-2-3-Tribonacci Sequence
Imagine for a second that you could make a fibonacci sequence by replacing the standard iteration formula with the following:
Basically, instead of summing the last two to get the next, you sum the last three. This is the basis for the 1-2-3-Tribonacci sequence.
Brown's Criterion state that you may represent any integer value as a sum of members of a sequence provided that:
ngreater than 1,
What this means for the challenge
You may describe any positive integer as a sum of members of the 1-2-3-Tribonacci sequence formed by the following initial conditions:
This is known as, for every value in this sequence, the ratio between terms is never greater than 2 (the ratio averages out at about 1.839).
How to write in this numerical representation system
Let's say that you use a little-endian representation. Line up members of the sequence like so:
1 2 3 6 11 20 37 68
Then, you take your number to be represented (for our tests, let's say it's
63) and find the values of the given 1-2-3-Tribonacci which sum to 63 (using the largest values first!). If the number is part of the sum, put a 1 under it, 0 if not.
1 2 3 6 11 20 37 68 0 0 0 1 0 1 1 0
You may do this for any given integer - just verify that you use the largest values below your given input first!
Write a program or function that will do the following given some positive integer input
n (written in any standard base) between 1 and your language's maximum value:
- Convert the value into the defined 1-2-3-Tribonacci's numerical representation.
- Using this binary-like representation, and read it as if it were binary. This means that the digits stay the same, but what they mean changes.
- Take this binary number and convert it into the base of the original number.
- Output or return this new number.
However, as long as the output is valid, you needn't follow these steps. If you magically find some formula that is shorter (and mathematically equivalent), feel free to use it.
Let the function
f be the function described by the definition, and let
 represent steps taken (as little-endian, though it shouldn't matter) (you do not need to follow this process, this is just the process described):
>>> f(1)    1 >>> f(5)  [0, 1, 1]  6 >>> f(63)  [0, 0, 0, 1, 0, 1, 1]  104