The Piggyback Sequence

Question

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 code-golf, 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).

May I ask for the rationale behind the name you gave to this sequence? — John Dvorak, Aug 21, 2016 at 16:57
@JanDvorak It just seems like the numbers are "piggybacking" each other. — clismique, Aug 21, 2016 at 21:20

Loovjo · Accepted Answer · 2016-08-21 14:35:14Z

6

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.

edited Aug 21, 2016 at 14:35

answered Aug 21, 2016 at 12:58

Loovjo

8,0802 gold badges26 silver badges57 bronze badges

\$\begingroup\$ You can save one byte by removing the space between x<4 and or \$\endgroup\$
– acrolith
Aug 21, 2016 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, 2016 at 19:31

Add a comment |

nimi · Accepted Answer · 2016-08-21 17:36:23Z

5

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.

edited Aug 21, 2016 at 17:36

answered Aug 21, 2016 at 16:33

nimi

35.7k4 gold badges32 silver badges96 bronze badges

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, 2016 at 16:39

Add a comment |

Sherlock9 · Accepted Answer · 2016-08-21 15:43:35Z

4

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]}

answered Aug 21, 2016 at 15:43

Sherlock9

12.2k1 gold badge27 silver badges68 bronze badges

Add a comment |

Brad Gilbert b2gills · Accepted Answer · 2016-08-22 03:05:45Z

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;
}

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

C, 46 bytes

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

Ideone

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 21, 2016 at 14:51

betseg

8,7433 gold badges26 silver badges59 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Downgoat · Accepted Answer · 2016-08-21 16:43:39Z

2

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.

edited Aug 21, 2016 at 16:43

answered Aug 21, 2016 at 16:18

Downgoat

28.8k6 gold badges81 silver badges154 bronze badges

Add a comment |

Beta Decay · Accepted Answer · 2016-08-21 20:08:23Z

2

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>

edited Aug 21, 2016 at 20:08

answered Aug 21, 2016 at 18:55

Beta Decay

23.2k7 gold badges67 silver badges163 bronze badges

\$\begingroup\$ Why not ES6? It saves a metric ton of bytes. \$\endgroup\$
– Ismael Miguel
Aug 21, 2016 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, 2016 at 19:59
\$\begingroup\$ @IsmaelMiguel Thanks. Frankly, I have no idea about the difference between the different Javascripts :D \$\endgroup\$
– Beta Decay
Aug 21, 2016 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, 2016 at 20:12
\$\begingroup\$ @IsmaelMiguel Thanks, that will come in useful :D \$\endgroup\$
– Beta Decay
Aug 21, 2016 at 20:13

| Show 1 more comment

Emigna · Accepted Answer · 2016-08-21 20:37:38Z

2

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

edited Aug 21, 2016 at 20:37

answered Aug 21, 2016 at 17:31

Emigna

52.8k5 gold badges41 silver badges161 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Pyth, 20 bytes

L?<b4h0+y-b3cy-b2ytb

Try it online!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 21, 2016 at 15:29

Lars

1463 bronze badges

Add a comment |

Dennis · Accepted Answer · 2016-08-21 20:28:46Z

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

phosgene · Accepted Answer · 2016-08-21 20:31:02Z

1

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}

edited Aug 21, 2016 at 20:31

answered Aug 21, 2016 at 20:20

phosgene

1,1757 silver badges15 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 22, 2016 at 17:37

Frédéric

2,0897 silver badges20 bronze badges

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, 2016 at 19:30

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Dyalog APL, 25 bytes

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 21, 2016 at 20:54

ngn

15.1k2 gold badges41 silver badges86 bronze badges

Add a comment |

Stack Exchange Network

The Piggyback Sequence

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

14 Answers 14

Python 2, 40 39 bytes.

Haskel, 32 bytes

Ruby, 34 bytes

Perl 6, 25 23 bytes

Explanation:

Test:

C, 46 bytes

MATL, 15 bytes

Explanation

Cheddar, 31 bytes

Javascript (ES6), 31 bytes

05AB1E, 18 17 bytes

Pyth, 20 bytes

Jelly, 15 bytes

How it works

Mathematica, 36 bytes

R, 53 47 bytes

Dyalog APL, 25 bytes

Your Answer

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

Hot Network Questions

The Piggyback Sequence

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

14 Answers 14

Python 2, 40 39 bytes.

Haskel, 32 bytes

Ruby, 34 bytes

Perl 6, 25 23 bytes

Explanation:

Test:

C, 46 bytes

MATL, 15 bytes

Explanation

Cheddar, 31 bytes

Javascript (ES6), 31 bytes

05AB1E, 18 17 bytes

Pyth, 20 bytes

Jelly, 15 bytes

How it works

Mathematica, 36 bytes

R, 53 47 bytes

Dyalog APL, 25 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

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