# 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? – John Dvorak Aug 21 '16 at 16:57
• @JanDvorak It just seems like the numbers are "piggybacking" each other. – clismique Aug 21 '16 at 21:20
• @nimi Yes, you are allowed. – clismique 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 – acrolith 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. – Dennis 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. – Ismael Miguel Aug 21 '16 at 19:47
• Like this: P=n=>n<4?1:P(n-3)+P(n-2)/P(n-1) – Ismael Miguel Aug 21 '16 at 19:59
• @IsmaelMiguel Thanks. Frankly, I have no idea about the difference between the different Javascripts :D – Beta Decay 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 {}. – Ismael Miguel Aug 21 '16 at 20:12
• @IsmaelMiguel Thanks, that will come in useful :D – Beta Decay 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).


# 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 – user5957401 Aug 22 '16 at 19:30

# 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
{1, 1, 1, 2, 3/2, 7/3, 37/14, 529/222, 38242/11109, 66065507/19809356}


# Dyalog APL, 25 bytes

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