Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|improve this question
    
Can we start at index 0? P(0)=1... – nimi 17 hours ago
3  
May I ask for the rationale behind the name you gave to this sequence? – Jan Dvorak 16 hours ago
    
@JanDvorak It just seems like the numbers are "piggybacking" each other. – DerpfacePython 12 hours ago
    
@nimi Yes, you are allowed. – DerpfacePython 12 hours ago

13 Answers 13

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.

share|improve this answer
    
You can save one byte by removing the space between x<4 and or – daHugLenny 19 hours ago
    
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 14 hours ago

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]}
share|improve this answer

C, 46 bytes

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

Ideone

share|improve this answer

Haskel, 32 bytes

(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.

share|improve this answer
1  
Nice method for beating the direct recursive definition. I think you can shift to 1-indexed by initializing (0,1,1). – xnor 17 hours ago

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
share|improve this answer

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;
}
share|improve this answer

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.

share|improve this answer

Pyth, 20 bytes

L?<b4h0+y-b3cy-b2ytb

Try it online!

share|improve this answer

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>

share|improve this answer
    
Why not ES6? It saves a metric ton of bytes. – Ismael Miguel 14 hours ago
    
Like this: P=n=>n<4?1:P(n-3)+P(n-2)/P(n-1) – Ismael Miguel 13 hours ago
    
@IsmaelMiguel Thanks. Frankly, I have no idea about the difference between the different Javascripts :D – βετѧ Λєҫαγ 13 hours ago
    
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 13 hours ago
    
@IsmaelMiguel Thanks, that will come in useful :D – βετѧ Λєҫαγ 13 hours ago

Jelly, 15 bytes

ạ2,1,3߀÷2/SµḊ¡

Try it online! or verify all test cases.

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).
share|improve this answer

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
           /+      # divide then add
             ¸ì    # wrap in list and prepend to full list
                ¬  # get first element and implicitly print

Try it online!

Saved 1 byte thanks to Luis Mendo

share|improve this answer
1  
@LuisMendo: Nice catch! – Emigna 13 hours ago

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}
share|improve this answer

Dyalog APL, 25 bytes

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.