14
\$\begingroup\$

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

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

14 Answers 14

6
\$\begingroup\$

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.

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

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.

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

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]}
\$\endgroup\$
4
\$\begingroup\$

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;
}
\$\endgroup\$
3
\$\begingroup\$

C, 46 bytes

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

Ideone

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ Why not ES6? It saves a metric ton of bytes. \$\endgroup\$ – Ismael Miguel Aug 21 '16 at 19:47
  • \$\begingroup\$ Like this: P=n=>n<4?1:P(n-3)+P(n-2)/P(n-1) \$\endgroup\$ – Ismael Miguel Aug 21 '16 at 19:59
  • \$\begingroup\$ @IsmaelMiguel Thanks. Frankly, I have no idea about the difference between the different Javascripts :D \$\endgroup\$ – Beta Decay Aug 21 '16 at 20:07
  • \$\begingroup\$ 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 {}. \$\endgroup\$ – Ismael Miguel Aug 21 '16 at 20:12
  • \$\begingroup\$ @IsmaelMiguel Thanks, that will come in useful :D \$\endgroup\$ – Beta Decay Aug 21 '16 at 20:13
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Pyth, 20 bytes

L?<b4h0+y-b3cy-b2ytb

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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).
\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – user5957401 Aug 22 '16 at 19:30
0
\$\begingroup\$

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}
\$\endgroup\$
0
\$\begingroup\$

Dyalog APL, 25 bytes

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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