Your Base to 1-2-3-Tribonacci to Binary back to Your Base

Question

Background

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

Brown's Criterion state that you may represent any integer value as a sum of members of a sequence provided that:

1. 

2. For all n greater 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!

Definition (finally)

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:

1. Convert the value into the defined 1-2-3-Tribonacci's numerical representation.
2. 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.
3. Take this binary number and convert it into the base of the original number.
4. 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.

Examples

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]
[1]
[1]
1

>>> f(5)
[5]
[0, 1, 1]
[6]
6

>>> f(63)
[63]
[0, 0, 0, 1, 0, 1, 1]
[104]
104

Answer 1

Javascript 117 111 bytes

Thanks to @theonlygusti for helping golf off 5 bytes

x=>{r=0;a=[1,2,3];i=1;while(a[++i]<x)a[i+1]=a[i]+a[i-1]+a[i-2];for(;x;i--)if(x>=a[i]){r+=1<<i;x-=a[i]}return r}

How It Works

First, the function generates all tribonacci numbers until it finds one greater than the input

a=[1,2,3];i=1;for(;a[++i]<x;)a[i+1]=a[i]+a[i-1]+a[i-2];

Next, it reverse searches the list of numbers. If a number is less than the input, it adds 2^(index of that number) to the return value and reduces the input by that number.

for(;x;i--)if(x>=a[i]){r+=1<<i;x-=a[i]}

Finally it returns the result.

Try it Online

Answer 2

Python 2, 110 102 bytes

-3 bytes thanks to Rod (neat trick for casting boolean i to an int with +i so the repr `+i` works)

n=input()
x=[3,2,1]
r=''
while x[0]<n:x=[sum(x[:3])]+x
for v in x:i=n>=v;n-=v*i;r+=`+i`
print int(r,2)

Try it online!

Answer 3

JavaScript (ES6), 97 93 bytes

Here, we are using reduce() on a recursive function. We assume that the output is 31-bit (which is the largest unsigned quantity that JS can easily work with for bitwise operations anyway).

n=>[...Array(x=31)].reduce(p=>(c=(F=k=>k<4?k:F(--k)+F(--k)+F(--k))(x--))>n?p:(n-=c,p|1<<x),0)

Performance wise, this is clearly not very efficient.

For the curious:

• The ratio between the number of calls to F() for N+1 reduce() iterations vs N iterations quickly converges towards the Tribonacci Constant (≈ 1.83929). Therefore, each additional bit in the output costs approximately twice as much time as the previous one.
• With 31 bits, the F() function is called a good 124 million times.

Test

NB: This may take 1 or 2 seconds to complete.

let f =

n=>[...Array(x=31)].reduce(p=>(c=(F=k=>k<4?k:F(--k)+F(--k)+F(--k))(x--))>n?p:(n-=c,p|1<<x),0)

console.log(f(63))

Answer 4

Mathematica, 78 74 bytes

Fold[#+##&,#~NumberDecompose~Reverse@LinearRecurrence[{1,1,1},{1,2,3},#]]&

LinearRecurrence[{1,1,1},{1,2,3},#] generates a list, of length equal to the input, of the 1-2-3 tribonacci numbers. (The {1,1,1} represents the sum of the previous three terms, while {1,2,3} are the initial values.) Then #~NumberDecompose~ finds the greediest way to write the input as a sum of elements of the list (this is the same function that would decompose a monetary amount into multiples of the available currencies, for example). Finally, Fold[#+##&,...] converts the resulting binary list into a (base-10) integer.

Previous submission:

Fold[#+##&,#~NumberDecompose~Reverse@Array[If[#<4,#,Tr[#0/@(#-Range@3)]]&,#]]&

As is often the case (though not above), this golfed version is super slow on inputs larger than 20 or so, because it generates (with non-optimized recursion) a list of tribs whose length is the input; replacing the final # by a more reasonable bound like Round[2Log@#+1] results in much better performance.

Answer 5

Haskell, 95 bytes

(a!b)c=a:(b!c)(a+b+c)
e#(r,c)|c-e<0=(2*r,c)|1<2=(2*r+1,c-e)
f n=fst$foldr(#)(0,n)$take n$(1!2)3

Usage example: f 63 -> 104. Try it online!.

How it works: ! builds the 1-2-3-Tribonacci sequence. Given 1, 2 and 3 as the start parameters, we take the first n elements of the sequence. Then we fold from the right function # which subtracts the next element e from n and sets the bit in the return value r if e is needed or lets the bit unset. Setting the bit is doubling r and adding 1, letting it unset is just doubling.

Answer 6

Jelly, 31 bytes

S=³
3RUµḣ3S;µ<³Ạµ¿µŒPÇÐfṀe@ЀµḄ

Try it online!

I'm almost certain there is a MUCH shorter way to achieve this in Jelly.

How?

S=³ - Link 1, compare sum to input: list
S   - sum
  ³ - 3rd command line argument which is 1st program argument.
 =  - equal?

3RUµḣ3S;µ<³Ạµ¿µŒPÇÐfṀe@ЀµḄ - Main link: n
3RU                         - range(3) upended -> [3,2,1]
   µ    µ   µ¿              - while
         <³                 - less than input (vectorises)
           Ạ                - all?
    ḣ3S;                    -     head(3), sum, and concatenate
                                  [3,2,1] -> [6,3,2,1] -> [11,6,3,2,1] -> ...
              µ             - monadic chain separation, call the result x
               ŒP           - power set of x - e.g. for [6,3,2,1] -> [[],[6],[3],[2],[1],[6,3],[6,2],[6,1],[3,2],[3,1],[2,1],[6,3,2],[6,3,1],[6,2,1],[3,2,1],[6,3,2,1]]
                  Ðf        - filter keep
                 Ç          -     last link (1) as a monad (those that sum to the input)
                    Ṁ       - maximum (e.g. an input of 63 would yield [[37,20,6],[37,20,3,2,1]], the maximum of which is [37,20,6], the one with the largest numbers used)
                         µ  - monadic chain separation (to have x as the right argument below)
                     e@Ѐ   - exists in with reversed arguments mapped over x (e.g. [37,20,6] with x = [68,37,20,11,6,3,2,1] yields [0,1,1,0,1,0,0,0])
                          Ḅ - convert from binary to integer.        

Answer 7

Perl 6, 93 91 bytes

-2 bytes thanks to b2gills

{my@f=1,2,3,*+*+*...*>$^n;sum @f».&{$_~~any first *.sum==$n,@f.combinations}Z*(2 X**^∞)}

How it works

• First, it generates the 1-2-3-Tribonacci sequence up to the first element larger than the input:

  my @f = 1, 2, 3, *+*+* ... * > $^n;

• Based on that it finds the subset of the sequence which adds up to the input:

  first *.sum==$n, @f.combinations

• Based on that it constructs a list of booleans specifying whether each element of the sequence is part of the sum:

  @f».&{$_~~any ...}

• And finally it interprets that list of True=1, False=0 values as base 2 and returns it as a (base 10) number:

  sum ... Z* (2 X** ^∞)

Answer 8

JavaScript (ES6), 61 60 bytes

n=>(g=(x,y,z)=>(n>x&&g(y,z,x+y+z)*2)+!(n<x||![n-=x]))(1,2,3)

Calculates the 1-2-3-Tribonacci numbers until it reaches the original number, then as the recursion unwinds, tries to subtract each one in turn, doubling the result as it goes.

Edit: Saved 1 byte thanks to @Arnauld.

Answer 9

Batch, 151 148 145 bytes

@set/ar=0,n=%1
@call:c 3 2 1
@echo %r%
@exit/b
:c
@set/as=%1+%2+%3
@if %n% gtr %3 call:c %s% %*
@set/ar*=2
@if %n% geq %3 set/an-=%3,r+=1

Port of my JavaScript answer. Edit: Saved 3 bytes by passing my subroutine arguments in reverse order and another 3 bytes by using individual @s on each line instead of @echo off.

Answer 10

Jelly (fork), 17 16 bytes

ḣ3S;µ¡
3RṚdzæFṪḄ

Saved 1 byte thanks to @Dennis who golfed it without even running it.

This relies on a fork of Jelly where I am disappointingly still working on implementing an efficient Frobenius solve atom. For those who are interested, I would like to match Mathematica's speed in FrobeniusSolve and luckily there is an explanation of their method in the paper "Making Change and Finding Repfigits: Balancing a Knapsack" by Daniel Lichtblau.

Explanation

ḣ3S;µ¡  Helper link. Input: a list
    µ   Create monadic chain
ḣ3        Take the first 3 items
  S       Sum
   ;      Prepend to the list
     ¡  Repeat it n (initial argument from main) times

3RṚdzæFṪḄ  Main link. Input: integer n
3          The constant 3
 R         Range. Makes [1, 2, 3]
  Ṛ        Reverse. Makes [3, 2, 1]
   Ç       Call the helper link on that list.
           Generates the first (n+3) 123-Tribonacci values in reverse
    ³      Get n
     æF    Frobenius solve for n using the first n 123-Tribonacci values in reverse
       Ṫ   Tail. Take the last value. The results of Frobenius solve are ordered
           where the last result uses the least
        Ḅ  Unbinary. Convert digits from base 2 to base 10

Answer 11

Jelly, 19 18 17 bytes

Ḣx3+
BÇL¡2ị
²Ç€»ċ

Try it online!

Background

Instead of trying to convert an integer to 1,2,3-Tribonacci base, then from binary to integer, we'll do the opposite: convert integers to binary, then from 1,2,3-Trionacci base to integer, and return the highest one that matches the input. This is easily accomplished.

We'll exemplify the process for input 63, in particular the step where 104 is tested. In binary, from most significant to least significant digit, 104 is equal to

 1  1  0  1  0  0  0
37 20 11  6  3  2  1

where the second row represents the positional values of those digits.

We can extend the 1,2,3-Tribonacci sequence to the right, observing that the added digits comply with the same recursive formula. For three mre digits, this gives

 1  1  0  1  0  0  0  0  0  0
37 20 11  6  3  2  1  0  1  0

Now, to compute the value of the base 1,2,3-Tribonacci number, we can make use of the recursive formula. Since each number is the sum of the three numbers to its right (in the table above), we can remove the first digit and add this to the first three digits of the remaining array. After 7 steps, which is equal to the number of binary digits of 104, we rare left with only three digits.

 1  1  0  1  0  0  0  0  0  0
37 20 11  6  3  2  1  0  1  0

    2  1  2  0  0  0  0  0  0
   20 11  6  3  2  1  0  1  0

       3  4  2  0  0  0  0  0
      11  6  3  2  1  0  1  0

          7  5  3  0  0  0  0
          6  3  2  1  0  1  0

            12 10  7  0  0  0
             3  2  1  0  1  0

               22 19 12  0  0
                2  1  0  1  0

                  41 34 22  0
                   1  0  1  0

                     75 63 41
                      0  1  0

Now, since the first and last remaining digit both have positional value 0, the result is the middle digit, i.e, 63.

How it works

²Ç€»ċ   Main link. Argument: n

²       Yield n². Since 1.839² = 3.381921 > 2, the range [1, ..., n²] will contain
        the answer. Better bounds, at the cost of additional bytes are possible.
 Ç€     Map the the second helper link over [1, ..., n²].
   »    Take the maximum of n and each result.
    ċ   Count the occurrences of n.


BÇL¡2ị  Second helper link. Left argument: k. Right argument: n

B       Convert k to binary. Let's call the result A.
  L     Length; count the number of binary digits. Let's call the result l.
 Ç ¡    Apply the first helper link l times to A.
    2ị  Retrieve the second element.


Ḣ×3+    First helper link. Argument: A (array)

Ḣ       Head; pop and yield the first element of A.
 x3     Repeat it thrice.
   +    Add the result, component by component, to the beheaded A.

Answer 12

dc, 110 102 bytes

?se1sa2sb3sc_1sf[laddSdlbdsalcdsb++sclf1+sfle>y]dsyx0sk[lk2lf^+skler-se]sr[Lddle!<rlf1-dsf0!>z]dszxlkp

Well, seems like great minds do think alike. Apparently, the algorithm I came up with to get around the limitations of dc is coincidentally the exact same one used in @LliwTelrac's answer. Interesting.

Try it online!

Answer 13

Python 2, 93 bytes

n=input();y=k=n*n
while y>n:
 x=y=z=0;k-=1
 for t in bin(k):x+=t=='1';x,y,z=y+x,z+x,x
print k

This is a port of my Jelly answer.

Try it online!

Answer 14

bash + BSD utilities (OS X, etc.), 53 bytes

jot $[2#$1**4]|egrep -v '[2-9]|11(1|$)'|sed $[2#$1]!d

bash + GNU utilities (works under BSD also), 59 bytes

seq -f2o%.fp $[2#$1**2]|dc|egrep -v '11(1|$)'|sed $[2#$1]!d

Input and output in both the above are in binary.

---

Try out the GNU version at TIO. (The example linked to demonstrates input of 111111, which is 63 in binary, and output of 1101000, which is 104 in binary.)

I don't think TIO offers a BSD option, but if you have a Mac available, you can try them both out there. (The 59-byte program is much faster than the 53-byte program.)

---

Unfortunately, seq can't simply be dropped into the BSD solution in place of jot, since the output format for seq is different for outputs above 999999. (This starts being a problem for inputs around 32, since 32^4 > 1000000.)

You can replace jot above with seq -f%.f to get this to work with GNU utilities, but for the same 59 bytes, you can use the GNU solution above, which is much faster.