# The Piggyback Sequence

I made my own sequence recently (called the Piggyback sequence), and it works like this:

P(1), P(2) and P(3) = 1.

For all P(n) where n>3, the sequence works like this:

P(n) = P(n-3) + P(n-2)/P(n-1)


So, continuing the sequence:

P(4) = 1 + 1/1 = 2

P(5) = 1 + 1/2 = 3/2 = 1.5

P(6) = 1 + 2/(3/2) = 7/3 = 2.33333...

P(7) = 2 + (3/2)/(7/3) = 37/14 = 2.6428571428...

P(8) = 3/2 + (7/3)/(37/14) = 529/222 = 2.3828828828...

Your task is, when given n, calculate P(n) either as a floating point number or an (im)proper fraction.

This is , so shortest code in bytes wins.

If anyone can find the name of the sequence, please edit the post accordingly.

## Current leaders: MATL and Jelly (both at 15 bytes).

• Can we start at index 0? P(0)=1...
– nimi
Aug 21 '16 at 16:30
• May I ask for the rationale behind the name you gave to this sequence? Aug 21 '16 at 16:57
• @JanDvorak It just seems like the numbers are "piggybacking" each other. Aug 21 '16 at 21:20
• @nimi Yes, you are allowed. Aug 21 '16 at 21:21

# Python 2, 40 39 bytes.

f=lambda x:x<4or.0+f(x-3)+f(x-2)/f(x-1)


Gives True instead of 1, if this isn't allowed we can have this for 42 bytes:

f=lambda x:.0+(x<4or f(x-3)+f(x-2)/f(x-1))


The way it works is pretty straightforward, the only trick is using .0+ to cast the result to a float.

• You can save one byte by removing the space between x<4 and or Aug 21 '16 at 14:33
• In Python 2, you can use f(x-1.) to cast to float. In Python 3, you don't need to cast at all. Aug 21 '16 at 19:31

(a#b)c=a:(b#c)(a+b/c)
((0#1)1!!)


Usage example: ((0#1)1!!) 7 -> 2.642857142857143. I start the sequence with 0, 1, 1 to fix !!'s 0-based indexing.

Edit: @xnor found a way to switch from 0-based to 1-based index, without changing the byte count.

• Nice method for beating the direct recursive definition. I think you can shift to 1-indexed by initializing (0,1,1).
– xnor
Aug 21 '16 at 16:39

# Ruby, 34 bytes

Since Ruby uses integer division by default, it turns out that it's shorter to use fractions instead. Golfing suggestions welcome.

f=->n{n<4?1r:f[n-3]+f[n-2]/f[n-1]}


# Perl 6,  25  23 bytes

{(0,1,1,1,*+*/*...*)[$_]}  {(0,1,1,*+*/*...*)[$_]}


## Explanation:

# bare block lambda with implicit parameter ｢$_｣ { ( # initial set-up # the ｢0｣ is for P(0) which isn't defined 0, 1, 1, 1, # Whatever lambda implementing the algorithm * + * / * # {$^a + $^b /$^c }

# keep using the lambda to generate new values until
...

# Whatever (Forever)
*

# get the value indexed by the argument
)[ $_ ] }  This returns a Rat (Rational) for inputs starting with 3 up until the result would start having a denominator bigger than can fit in a 64 bit integer, at which point it starts returning Nums (floating point). The last Rat it will return is P(11) == 8832072277617 / 2586200337022 If you want it to return Rational numbers rather than floats you can swap it for the following which will return a FatRat instead. {(0.FatRat,1,1,*+*/*...*)[$_]}


## Test:

#! /usr/bin/env perl6
use v6.c;
use Test;

my &piggyback = {(0,1,1,*+*/*...*)[$_]} # */ # stupid highlighter no Perl will ever have C/C++ comments my @test = ( 1, 1, 1, 2, 3/2, 7/3, 37/14, 529 / 222, 38242 / 11109, 66065507 / 19809356, 8832072277617 / 2586200337022, ); plan +@test; for 1..* Z @test -> ($input,$expected) { cmp-ok piggyback($input), &[==], $expected,$expected.perl;
}


## C, 46 bytes

float P(n){return n<4?1:P(n-3)+P(n-2)/P(n-1);}


Ideone

# MATL, 15 bytes

llli3-:"3$t/+]&  Try it online! ### Explanation lll % Push 1, 1, 1 i % Take input n 3-: % Pop n and push range [1 2 ... n-3] (empty if n<4) " % For each 3$t     %    Duplicate the top three numbers in the stack
/       %    Pop the top two numbers and push their division
+       %    Pop the top two numbers and push their addition
]         % End
&         % Specify that the next function, which is implicit display, will take
% only one input. So the top of the stack is displayed


# Cheddar, 31 bytes

n P->n<4?1:P(n-3)+P(n-2)/P(n-1)


The ungolfed version is so clear imo you don't need explanation:

n P->
n < 4 ? 1 : P(n-3) + P(n-2) / P(n-1)


basically after the function arguments you can specify the variable to use which will be set to the function itself. Why? because this function will be tail-call-optimized, or at least should be.

# Javascript (ES6), 31 bytes

P=n=>n<4?1:P(n-3)+P(n-2)/P(n-1)


A simple function.

P=n=>n<4?1:P(n-3)+P(n-2)/P(n-1)

var out = '';

for (var i=1;i <= 20;i++) {
out +='<strong>'+i+':</strong> '+P(i)+'<br/>';
}

document.getElementById('text').innerHTML = out;
div {
font-family: Arial
}
<div id="text"></div>

• Why not ES6? It saves a metric ton of bytes. Aug 21 '16 at 19:47
• Like this: P=n=>n<4?1:P(n-3)+P(n-2)/P(n-1) Aug 21 '16 at 19:59
• @IsmaelMiguel Thanks. Frankly, I have no idea about the difference between the different Javascripts :D Aug 21 '16 at 20:07
• To your advantage, on most challenges, you only need to know the "Big Arrow notation", which allows you to create functions without using the keyword function. The bit P=n=>[...] is creating an anonymous function that takes 1 parameter (n). Also, on ES6, returns are implicit. So, P=n=>5 is a function that always returns 5. You only need to enclose the body in {} if you have more than one statement (E.g.: P=n=>{alert(1);console.log(1)}). Since you have only 1 (big) statement (the ternary operator), you can forget the {}. Aug 21 '16 at 20:12
• @IsmaelMiguel Thanks, that will come in useful :D Aug 21 '16 at 20:13

# 05AB1E, 18 17 bytes

3Ld                # push list [1,1,1]
¹ÍG         }   # input-3 times do
D3£          # duplicate list and take first 3 elements of the copy
R        # reverse and flatten
¸ì    # wrap in list and prepend to full list
¬  # get first element and implicitly print


Try it online!

Saved 1 byte thanks to Luis Mendo

# Pyth, 20 bytes

L?<b4h0+y-b3cy-b2ytb


Try it online!

# Jelly, 15 bytes

ạ2,1,3ß€÷2/SµḊ¡


### How it works

ạ2,1,3ß€÷2/SµḊ¡  Main link. Argument: n (integer)

Ḋ   Dequeue; yield [2, ..., n].
µ ¡  If the range is non-empty (i.e., if n > 1), execute the chain to
the left. If n is 0 or 1, return n.
Note that P(3) = P(0) + P(2)/P(1) if we define P(0) := 0.
ạ2,1,3           Take the absolute difference of n and 2, 1, and 3.
This gives [0, 1, 1] if n = 2, and P(0) + P(1)/P(1) = 0 + 1/1 = 1.
ß€         Recursively apply the main each to each difference.
÷2/      Perform pairwise division.
This maps [P(n-2), P(n-1), P(n-3)] to [P(n-2)/P(n-1), P(n-3)].
S     Sum, yielding P(n-2)/P(n-1) + P(n-3).


# Mathematica, 36 bytes

P@n_:=If[n<4,1,P[n-3]+P[n-2]/P[n-1]]


Here are the first few terms:

P /@ Range[10]
{1, 1, 1, 2, 3/2, 7/3, 37/14, 529/222, 38242/11109, 66065507/19809356}


# R, 53 47 bytes

f=function(N)ifelse(N>3,f(N-3)+f(N-2)/f(N-1),1)


This answer made use of the pretty neat function ifelse : ifelse(Condition, WhatToDoIfTrue, WhatToDoIfNot)

• You should be able to get rid of the return() in your code. But you also need to name the function in order for your recursion to work Aug 22 '16 at 19:30

# Dyalog APL, 25 bytes

⊃{1↓⍵,⍎⍕' +÷',¨⍵}⍣⎕⊢0 1 1`