# Sylvester's sequence

Sylvester's sequence, OEIS A000058, is an integer sequence defined as follows:

Each member is the product of all previous members plus one. The first member of the sequence is 2.

Create the smallest program possible that takes an n and calculates the nth term of Sylvester's Sequence. Standard input, output and loopholes apply. Since the result grows very quickly you are not expected to take any term of which the result would cause an overflow in your chosen language.

## Test Cases

You may use either zero or one indexing. (Here I use zero indexing)

>>0
2
>>1
3
>>2
7
>>3
43
>>4
1807

• What inputs are expected to be handled? The output grows quite rapidly. – Geobits Aug 26 '16 at 1:44
• @Geobits you are expected to handle as much as your language can – Wheat Wizard Aug 26 '16 at 1:46
• Is an array which when indexed with n returns the nth number of the sequence accepted? – user6245072 Aug 26 '16 at 7:05
• @user6245072 No you must index your own arrays – Wheat Wizard Aug 26 '16 at 12:55

# Brain-Flak, 76685852 46 bytes

<>(()())<>{({}[()])<>({({}[()])({})}{}())<>}<>


Try it online!

which is derived from this relationship modified from that provided in the sequence:

a(n+1) = a(n) * (a(n) - 1) + 1.

### Explanation

For a documentation of what each command does, please visit the GitHub page.

There are two stacks in Brain-Flak, which I shall name as Stack 1 and Stack 2 respectively.

The input is stored in Stack 1.

<>(()())<>             Store 2 in Stack 2.

{                      while(Stack_1 != 0){
({}[()])                 Stack_1 <- Stack_1 - 1;
<>                       Switch stack.
({({}[()])({})}{}())     Generate the next number in Stack 2.
<>                       Switch back to Stack 1.
}

<>                     Switch to Stack 2, implicitly print.


For the generation algorithm:

({({}[()])({})}{}())      Top <- (Top + Top + (Top-1) + (Top-1) + ... + 0) + 1

(                  )      Push the sum of the numbers evaluated in the process:

{            }               while(Top != 0){
({}[()])                        Pop Top, push Top-1    (added to sum)
({})                    Pop again, push again  (added to sum)
}

{}             Top of stack is now zero, pop it.
()           Evaluates to 1 (added to sum).


## Alternative 46-byte version

This uses only one stack.

({}<(()())>){({}<({({}[()])({})}{}())>[()])}{}


Try it online!

• Only 10 more bytes to show that java develepors should go to brain flack – Rohan Jhunjhunwala Aug 26 '16 at 3:15
• @RohanJhunjhunwala I'm afraid that's impossible... – Leaky Nun Aug 26 '16 at 3:20
• @LeakyNun it still is interesting to think of. Brain Flak has some power, and is suprisingly terse – Rohan Jhunjhunwala Aug 26 '16 at 3:21
• The one stack version is also stack clean. Which tends to be a important point for code modularity in brain-flak. – Wheat Wizard Aug 26 '16 at 4:51
• Wow. This is an extremely impressive answer. – James Aug 26 '16 at 6:59

# Jelly, 5 bytes

Ḷß€P‘


This uses 0-based indexing and the definition from the challenge spec.

### How it works

Ḷß€P‘  Main link. Argument: n

Ḷ      Unlength; yield [0, ..., n - 1].
ß€    Recursively apply the main link to each integer in that range.
P   Take the product. This yields 1 for an empty range.
‘  Increment.

• Ah, I forgot that the empty product is 1. – Leaky Nun Aug 26 '16 at 3:46

## Hexagony, 27 bytes

1{?)=}&~".>")!@(</=+={"/>}*


Unfolded:

    1 { ? )
= } & ~ "
. > " ) ! @
( < / = + = {
" / > } * .
. . . . .
. . . .


Try it online!

### Explanation

Let's consider the sequence b(a) = a(n) - 1 and do a little rearranging:

b(a) = a(n) - 1
= a(n-1)*(a(n-1)-1) + 1 - 1
= (b(n-1) + 1)*(b(n-1) + 1 - 1)
= (b(n-1) + 1)*b(n-1)
= b(n-1)^2 + b(n-1)


This sequence is very similar but we can defer the increment to the very end, which happens to save a byte in this program.

So here is the annotated source code:

Created with Timwi's HexagonyColorer.

And here is a memory diagram (the red triangle shows the memory pointer's initial position and orientation):

Created with Timwi's EsotericIDE.

The code begins on the grey path which wraps the left corner, so the initial linear bit is the following:

1{?)(
1      Set edge b(1) to 1.
{     Move MP to edge N.
?    Read input into edge N.
)(  Increment, decrement (no-op).


Then the code hits the < which is a branch and indicates the start (and end) of the main loop. As long as the N edge has a positive value, the green path will be executed. That path wraps around the grid a few times, but it's actually entirely linear:

""~&}=.*}=+={....(


The . are no-ops, so the actual code is:

""~&}=*}=+={(
""             Move the MP to edge "copy".
~            Negate. This is to ensure that the value is negative so that &...
&           ...copies the left-hand neighbour, i.e. b(i).
}=         Move the MP to edge b(i)^2 and turn it around.
*        Multiply the two copies of b(i) to compute b(i)^2.
}=      Move the MP back to edge b(i) and turn it around.
+     Add the values in edges "copy" and b(i)^2 to compute
b(i) + b(i)^2 = b(i+1).
={   Turn the memory pointer around and move to edge N.
(  Decrement.


Once this decrementing reduces N to 0, the red path is executed:

")!@
"     Move MP back to edge b(i) (which now holds b(N)).
)    Increment to get a(N).
!   Print as integer.
@  Terminate the program.

• Can you run your bruteforcer on this? – CalculatorFeline Jun 19 '17 at 17:39
• @CalculatorFeline The brute forcer can do at most 7-byte programs (and even that only with a bunch of assumptions) in a reasonable amount of time. I don't see this being remotely possible in 7 bytes. – Martin Ender Jun 19 '17 at 17:42
• So? What's wrong with trying? – CalculatorFeline Jun 19 '17 at 17:45
• @CalculatorFeline Laziness. The brute forcer always requires a bit of manual tweaking that I can't be bothered to do for the practically 0 chance that it will find something. Some version of the script is on GitHub though so anyone else is free to give it a go. – Martin Ender Jun 19 '17 at 17:48
• And how do I do that? – CalculatorFeline Jun 19 '17 at 18:14

# J, 1814 12 bytes

This version thanks to randomra. I'll try to write a detailed explanation later.

0&(]*:-<:)2:


# J, 14 bytes

This version thanks to miles. Used the power adverb ^: instead of an agenda as below. More explanation to come.

2(]*:-<:)^:[~]


# J, 18 bytes

2:(1+*/@$:@i.)@.*  0-indexed. ## Examples  e =: 2:(1+*/@$:@i.)@.*
e 1
3
e 2
7
e 3
43
e 4
1807
x: e i. 10
2 3 7 43 1807 3263443 10650056950807 113423713055421862298779648 12864938683278674737956996400574416174101565840293888 1655066473245199944217466828172807675196959605278049661438916426914992848    91480678309535880456026315554816
|: ,: x: e i. 10
2
3
7
43
1807
3263443
10650056950807
113423713055421862298779648
12864938683278674737956996400574416174101565840293888
165506647324519994421746682817280767519695960527804966143891642691499284891480678309535880456026315554816


## Explanation

This is an agenda that looks like this:

           ┌─ 2:
│    ┌─ 1
┌───┤    ├─ +
│   └────┤           ┌─ / ─── *
── @. ─┤        │     ┌─ @ ─┴─ $: │ └─ @ ─┴─ i. └─ *  (Generated using (9!:7)'┌┬┐├┼┤└┴┘│─' then 5!:4<'e') Decomposing:  ┌─ ... │ ── @. ─┤ │ └─ *  Using the top branch as a the gerund G, and the bottom as the selector F, this is: e n <=> ((F n) { G) n  This uses the constant function 2: when 0 = * n, that is, when the sign is zero (thus n is zero). Otherwise, we use this fork:  ┌─ 1 ├─ + ──┤ ┌─ / ─── * │ ┌─ @ ─┴─$:
└─ @ ─┴─ i.


Which is one plus the following atop series:

            ┌─ / ─── *
┌─ @ ─┴─ $: ── @ ─┴─ i.  Decomposing further, this is product (*/) over self-reference ($:) over range (i.).

• You can also use the power adverb to get 2(]*:-<:)^:[~] for 14 bytes using the formula a(0) = 2 and a(n+1) = a(n)^2 - (a(n) - 1). To compute larger values, the 2 at the start will have to be marked as an extended integer. – miles Aug 26 '16 at 4:08
• Both solutions are very nice. I think I was unaware of the v$:@.u recursive format. I always used a ^:v format which is often more complex. @miles I also never used the (]v) trick. It took me a good 5 minutes to understand it. – randomra Aug 26 '16 at 8:37 • For completeness a 3rd kind of looping (14 bytes using miles's method): 2(]*:-<:)~&0~] (or 2:0&(]*:-<:)~]). And combining them 13 bytes ]0&(]*:-<:)2:. – randomra Aug 26 '16 at 8:44 • 12 bytes: 0&(]*:-<:)2:. (Sorry, I shouldn't golf in the comments.) – randomra Aug 26 '16 at 8:52 • @randomra That is a really neat use of bond. I had to read the page to find out exactly what happened since normally one would think that middle verb was receiving three arguments. – miles Aug 26 '16 at 10:20 # Perl 6, 24 bytes {(2,{1+[*] @_}...*)[$_]}

{(2,{1+.²-$_}...*)[$_]}


## Explanation

# bare block with implicit parameter ｢$_｣ { ( # You can replace 2 with 1 here # so that it uses 1 based indexing # rather than 0 based 2, # bare block with implicit parameter ｢@_｣ { 1 + # reduce the input of this inner block with ｢&infix:<*>｣ # ( the input is all of them generated when using a slurpy @ var ) [*] @_ # that is the same as: # ｢@_.reduce: &infix:<*>｣ } # keep calling that to generate more values until: ... # forever * # get the value as indexed by the input )[$_ ]
}


## Usage:

my &code = {(2,{1+[*] @_}...*)[$_]} say code 0; # 2 say code 1; # 3 say code 2; # 7 say code 3; # 43 say code 4; # 1807 # you can even give it a range say code 4..7; # (1807 3263443 10650056950807 113423713055421844361000443) say code 8; # 12864938683278671740537145998360961546653259485195807 say code 9; # 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 say code 10; # 27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920807 my$start = now;
# how many digits are there in the 20th value
say chars code 20;
# 213441

my $finish = now; # how long did it take to generate the values up to 20 say$finish - $start, ' seconds'; # 49.7069076 seconds  • An array slice with $_? What witchcraft is this? – Zaid Aug 26 '16 at 16:15

f n|n<1=2|m<-f$n-1=1+m*m-m  Usage example: f 4 -> 1807. ## Java 7, 46 42 bytes int f(int n){return--n<0?2:f(n)*~-f(n)+1;}  Uses 0-indexing with the usual formula. I swapped n*n-n for n*(n-1) though, since Java doesn't have a handy power operator, and the f() calls were getting long. • f(n)*~-f(n) should work. – Dennis Aug 26 '16 at 2:44 • How do I forget about that trick every single time? If that isn't on the tips page, it's damn sure about to be. – Geobits Aug 26 '16 at 2:45 • return--n<0 saves one more byte. – Dennis Aug 26 '16 at 2:49 • – Leaky Nun Aug 26 '16 at 3:23 • – Geobits Aug 26 '16 at 3:32 ## Haskell, 25 bytes (iterate(\m->m*m-m+1)2!!)  # S.I.L.O.S, 60 bytes readIO p = 2 lblL r = p r + 1 p * r i - 1 if i L printInt r  Try it online! Port of my answer in C. • Yay :D finally a SILOS golfer, the interesting thing is that it beats Scala :) – Rohan Jhunjhunwala Aug 26 '16 at 16:32 # Brain-Flak, 158 154 bytes Leaky Nun has me beat here ({}<(()())>){({}[()]<<>(())<>([]){{}<>({}<<>(({}<>))><>)<>({<({}[()])><>({})<>}{})<>{}([])}{}<>({}())([]){{}({}<>)<>([])}{}<>>)}{}([][()]){{}{}([][()])}{}  Try it Online! ## Explanation Put a two under the input a(0) ({}<(()())>)  While the input is greater than zero subtract one from the input and... { ({}[()]  Silently... <  Put one on the other stack to act as a catalyst for multiplication <>(())<> While the stack is non-empty  ([]) { {}  Move the top of the list over and copy  <>({}<<>(({}<>))><>)  Multiply the catalyst by the copy  <>({<({}[()])><>({})<>}{})<>{} ([]) } {}  Add one  <>({}())  Move the sequence back to the proper stack  ([]) { {} ({}<>)<> ([]) } {} <> >) }{}  Remove all but the bottom item (i.e. the last number created) ([][()]) { {} {} ([][()]) } {}  # C, 32 bytes f(n){return--n?f(n)*~-f(n)+1:2;}  Uses 1-based indexing. Test it on Ideone. # Actually, 9 bytes 2@rΣτun  Try it online! Uses this relationship instead: which is derived from this relationship modified from that provided in the sequence: a(n+1) = a(n) * (a(n) - 1) + 1. ## R, 44 42 41 bytes 2 bytes save thanks to JDL 1 byte save thanks to user5957401 f=function(n)ifelse(n,(a=f(n-1))^2-a+1,2)  • It's not clear from the problem statement, but as long as n is guaranteed to not be negative then the condition can be reduced from n>0 to just n. – JDL Aug 26 '16 at 14:26 • @JDL Nice ! Thanks ! – Mamie Aug 26 '16 at 15:21 • f(n-1) is 6 bytes. I think you save a byte by assigning it to something. i.e. ifelse(n,(a=f(n-1))^2-a+1,2) – user5957401 Aug 26 '16 at 16:58 # Oasis, 4 bytes (non-competing) Probably my last language from the golfing family! Non-competing, since the language postdates the challenge. Code: ²->2  Alternative solution thanks to Zwei: <*>2  Expanded version: a(n) = ²-> a(0) = 2  Explanation: ² # Stack is empty, so calculate a(n - 1) ** 2. - # Subtract, arity 2, so use a(n - 1). > # Increment by 1.  Uses the CP-1252 encoding. Try it online! • Last golfing language? You're not going to make any more? D: – Conor O'Brien Aug 31 '16 at 0:58 • @ConorO'Brien Probably, I'm out of ideas now :( – Adnan Aug 31 '16 at 1:00 • Before looking at this challenge, I got b<*>2 using a(n-1)*(a(n-1)+1)-1 – Zwei Sep 23 '16 at 3:12 • @Zwei Very neat! You can actually leave out the b since that will be automatically filled in (rather than the input) :). – Adnan Sep 23 '16 at 5:48 • Yup, I noticed that after posting. I'm surprised how well this language works for this, even though it is designed for sequences. – Zwei Sep 23 '16 at 20:29 # Python, 38 36 bytes 2 bytes thanks to Dennis. f=lambda n:0**n*2or~-f(n-1)*f(n-1)+1  Ideone it! Uses this relationship modified from that provided in the sequence instead: a(n+1) = a(n) * (a(n) - 1) + 1 ### Explanation 0**n*2 returns 2 when n=0 and 0 otherwise, because 0**0 is defined to be 1 in Python. # Cheddar, 26 bytes n g->n?g(n-=1)**2-g(n)+1:2  Try it online! Pretty idiomatic. ## Explanation n g -> // Input n, g is this function n ? // if n is > 1 g(n-=1)**2-g(n)+1 // Do equation specified in OEIS : 2 // if n == 0 return 2  • Now 4 times (almost) – Leaky Nun Aug 26 '16 at 1:55 • Why did you remove the TIO link? – Leaky Nun Aug 26 '16 at 2:35 • @LeakyNun oh you must of been editing while I was – Downgoat Aug 26 '16 at 2:51 # CJam, 10 bytes 2{_(*)}ri*  Uses 0-based indexing. Try it online! # 05AB1E, 7 bytes 2sFD<*>  Explained Uses zero-based indexing. 2 # push 2 (initialization for n=0) sF # input nr of times do D<* # x(x-1) > # add 1  Try it online! # Prolog, 49 bytes a(0,2). a(N,R):-N>0,M is N-1,a(M,T),R is T*T-T+1.  # SILOS 201 bytes readIO def : lbl set 128 2 set 129 3 j = i if j z print 2 GOTO e :z j - 1 if j Z print 3 GOTO e :Z i - 1 :a a = 127 b = 1 c = 1 :b b * c a + 1 c = get a if c b b + 1 set a b i - 1 if i a printInt b :e  Feel free to try it online! • What the hell is going on – TuxCrafting Aug 26 '16 at 18:22 • @TùxCräftîñg witchcraft – Rohan Jhunjhunwala Aug 26 '16 at 18:22 # Jelly, 7 bytes ²_’ 2Ç¡  Try it online! Uses this relationship provided in the sequence instead: a(n+1) = a(n)^2 - a(n) + 1 ### Explanation 2Ç¡ Main chain, argument in input 2 Start with 2 ¡ Repeat as many times as the input: Ç the helper link. ²_’ Helper link, argument: z ² z² ’ z - 1 _ subtraction, yielding z² - (z-1) = z² - z + 1  # C, 46 bytes s(n,p,r){for(p=r=2;n-->0;p*=r)r=p+1;return r;}  Ideone it! Uses p as the temporary storage of the product. Basically, I defined two sequences p(n) and r(n), where r(n)=p(n-1)+1 and p(n)=p(n-1)*r(n). r(n) is the required sequence. • Any reason you're not using the same relation from your Python answer here? That should be a lot shorter... – Dennis Aug 26 '16 at 3:20 • @Dennis This is more interesting. – Leaky Nun Aug 26 '16 at 3:21 • @Dennis And this answer can be ported – Leaky Nun Aug 26 '16 at 18:29 # R, 50 46 44 bytes  n=scan();v=2;if(n)for(i in 1:n){v=v^2-v+1};v  Rather than tracking the whole sequence, we just keep track of the product, which follows the given quadratic update rule as long as n>1 n>0. (This sequence uses the "start at one zero" convention) Using the start at zero convention saves a couple of bytes since we can use if(n) rather than if(n>1) ## Jellyfish, 13 bytes p \Ai &(* ><2  Try it online! ### Explanation Let's start from the bottom up: (* <  This is a hook, which defines a function f(x) = (x-1)*x. &(* ><  This composes the previous hook with the increment function so it gives us a function g(x) = (x-1)*x+1. \Ai &(* ><  Finally, this generates a function h which is an iteration of the previous function g, as many times as given by the integer input. \Ai &(* ><2  And finally, we apply this iteration to the initial value 2. The p at the top just prints the result. ### Alternative (also 13 bytes) p > \Ai (* >1  This defers the increment until the very end. # C, 43, 34, 33 bytes 1-indexed: F(n){return--n?n=F(n),n*n-n+1:2;}  Test main: int main() { printf("%d\n", F(1)); printf("%d\n", F(2)); printf("%d\n", F(3)); printf("%d\n", F(4)); printf("%d\n", F(5)); }  # Brachylog, 13 bytes 0,2|-:0&-y+*+  Try it online! Uses this relationship instead: which is derived from this relationship modified from that provided in the sequence: a(n+1) = a(n) * (a(n) - 1) + 1. # Mathematica, 19 bytes Nest[#^2-#+1&,2,#]&  Or 21 bytes: Array[#0,#,0,1+1##&]&  • The Array solution is magical. Too bad, ##0 is not a thing. ;) – Martin Ender Aug 26 '16 at 15:34 ## Labyrinth, 18 bytes Credits to Sp3000 who found the same solution independently. ? # )}"{!@ * ( (:{  Try it online! # Flurry, 26 bytes {}[(<><<>()>)({})]{{}}{}{}  ### Verification $ echo -n "{}[(<><<>()>)({})]{{}}{}{}" | wc -c
26
$./flurry -nin -c "{}[(<><<>()>)({})]{{}}{}{}" 0 2$ ./flurry -nin -c "{}[(<><<>()>)({})]{{}}{}{}" 1
3
$./flurry -nin -c "{}[(<><<>()>)({})]{{}}{}{}" 2 7$ ./flurry -nin -c "{}[(<><<>()>)({})]{{}}{}{}" 3
43
\$ ./flurry -nin -c "{}[(<><<>()>)({})]{{}}{}{}" 4
1807


### How it works

We have a formula $$\a(n+1) = a(n) (a(n) - 1) + 1\$$, but pred is well-known to be expensive in SKI calculus, so I defined an auxiliary sequence:

$$b(n) = a(n)-1 \\ a(n+1) - 1 = (a(n)-1+1)(a(n)-1) \\ b(n+1) = b(n)(b(n)+1), b(0) = 1$$

Then we can use the nature of Church numerals to calculate the $$\n\$$-th term as

b = \n. n (\x. x ∘ succ x) 1
a = \n. succ (b n)
= \n. succ (n (\x. x ∘ succ x) 1)


where succ is the successor function and ∘ is function composition (which acts as multiplication when given two Church numerals).

We can represent the \x. x ∘ succ x part directly in Flurry as {<({})[<><<>()>{}]>}, but we can do better. We can try converting to SKB:

\x. \f. x (succ x f)
\x. \f. K x f (succ x f)
\x. S (K x) (succ x)
\x. (S∘K) x (succ x)
S (S∘K) succ
succ succ  (because succ = S (S∘K))


So we can duplicate succ via the stack, making it [(<><<>()>){}] (-6 bytes). Using it in the full program, we get:

\n. succ (n (\x. x ∘ succ x) 1)
\n. succ (n (succ succ) 1)

<><<>()>[       succ (
{}[              n (
(<><<>()>)       succ [push succ]
{}               succ [pop]
]                )
{}               I [pop from empty stack]
]               )


But I wasn't satisfied because it still has two copies of succ. So I changed the "calculate b(n) and apply succ on it" to "apply succ b(n) times to 1", which gives

\n. n (succ succ) 1 succ 1

{}[           n (
(<><<>()>)    succ [push succ]
({})          succ [pop and push succ]
]           )
{{}}          I    [1]
{}            succ [pop]
{}            I    [pop from empty stack]

• I've just had a glance at the Flurry docs. I think I'm in love. Really excited to take this for a drive. – Wheat Wizard Aug 12 '20 at 2:52
• @AdHocGarfHunter I just opened a chat room for Flurry. – Bubbler Aug 12 '20 at 23:51

# Actually, 14 12 bytes

This used 0-indexing. Golfing suggestions welcome. Try it online!

2#,;πu@onF


Ungolfing:

2#              Start with [2]
,     n     Take 0-indexed input and run function (input) times
;           Duplicate list
πu         Take product of list and increment
@o       Swap and append result to the beginning of the list
F    Return the first item of the resulting list
`