title: Sylvester's sequence

text:
# Question
Title: 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.

## Task

Create a program to calculate the nth term of Sylvester's Sequence. Standard input, output and loopholes apply.

Standard rules apply.

This is , so the goal is to minimize the size of your source code as measured in bytes.

## 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

```

# Answer
# Brain-Flak, ~~76~~ ~~68~~ ~~58~~ ~~52~~ 46 bytes

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

```

Try it online!

Uses this relationship instead:

$$a(n) = 1+\sum^{a(n-1)-1}\_{i=0} 2i$$

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!
> 30 votes

# Answer
# Jelly, 5 bytes

```
Ḷß€P‘

```

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

Try it online! or verify all test cases.

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

```
> 14 votes

# Answer
## 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.

```
> 13 votes

# Answer
# 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

```
> 9 votes

# Answer
# J, ~~18~~ ~~14~~ 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.`).
> 9 votes

# Answer
## Haskell, 26 bytes

```
f n|n<1=2|m<-f$n-1=1+m*m-m

```

Usage example: `f 4` -\> `1807`.
> 8 votes

# Answer
## 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.
> 7 votes

# Answer
## Haskell, 25 bytes

```
(iterate(\m->m*m-m+1)2!!)

```
> 6 votes

# Answer
# 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.
> 6 votes

# Answer
# Oasis, 4 bytes

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!
> 6 votes

# Answer
# 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)

```
([][()])
{
{}
{}
([][()])
}
{}

```
> 5 votes

# Answer
# C, 32 bytes

```
f(n){return--n?f(n)*~-f(n)+1:2;}

```

Uses 1-based indexing. Test it on Ideone.
> 5 votes

# Answer
# Actually, 9 bytes

```
2@`rΣτu`n

```

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`.
> 5 votes

# Answer
## 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)

```
> 5 votes

# Answer
# 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.
> 4 votes

# Answer
# K (oK), 12 bytes

```
{2|1+*/o'!x}

```

Try it online!

~~Blatantly stolen from~~ Port of Adám's answer.

Prints up to the first 11 elements of the sequence, after which the numbers become too big to handle.

Thanks @ngn for 6 bytes!

### How:

```
{2|1+*/o'!x} # Main function, argument x.
       o'!x  # recursively do (o) for each (') of [0..x-1] (!x)
   1+*/      # 1 + the product of the list
 2|          # then return the maximum between that product and 2.

```
> 4 votes

# Answer
# 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

```
> 3 votes

# Answer
# 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

```
> 3 votes

# Answer
# CJam, 10 bytes

```
2{_(*)}ri*

```

Uses 0-based indexing. Try it online!
> 3 votes

# Answer
# 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!
> 3 votes

# Answer
# Mathematica, 19 bytes

```
Nest[#^2-#+1&,2,#]&

```

---

Or 21 bytes:

```
Array[#0,#,0,1+1##&]&

```
> 3 votes

# Answer
# 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)
> 3 votes

# Answer
## 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.
> 3 votes

# Answer
# Prolog, 49 bytes

```
a(0,2).
a(N,R):-N>0,M is N-1,a(M,T),R is T*T-T+1.

```
> 3 votes

# Answer
# 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!
> 3 votes

# Answer
# Red, ~~55 49 45~~ 39 bytes

```
func[n][x: 2 loop n[x: x * x - x + 1]x]

```

Try it online!

* *-6 thanks to Galen Ivanov*
* *-4 thanks to Pedro Maimere*
* *-6 thanks to 9214*

This is the first real thing I wrote in Red. You have been warned.
> 3 votes

# Answer
# Python 2, ~~87~~ ~~73~~ ~~64~~ ~~60~~ 51 bytes

*~~14~~ ~~23~~ 25 bytes saved thanks to Leaky Nun*

*9 bytes saved thanks to Specter Terrasbane*

Here's my go at my own challenge.

```
f=lambda x:reduce(int.__mul__,[1]+map(f,range(x)))+1

```
> 2 votes

# Answer
# 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.
> 2 votes

# Answer
# 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));
}

```
> 2 votes

# Answer
# 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`.
> 2 votes

# Answer
## Labyrinth, 18 bytes

*Credits to Sp3000 who found the same solution independently.*

```
?
#
)}"{!@
* (
(:{

```

Try it online!
> 2 votes

# Answer
# Haskell, 27 bytes

```
f 0=2
f n=f(n-1)^2-f(n-1)+1

```

Try it online!

Not the shortest Haskell answer but it uses a new method.
> 2 votes

# Answer
# 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]

```
> 2 votes

# Answer
# Ruby, 29 bytes

```
f=->a{a<1?2:(b=f[a-1])*~-b+1}

```

+2 for adding `f=` to byte count.

-2 from Dingus's suggestion.

Try it online!
> 2 votes

# Answer
# Vyxal, 7 bytes

*-2 bytes thanks to Steffan*

```
2$(:‹*›

```

**Explanation:**

```
2$(:‹*›
2$          Push 2 and swap it with the input
   (:       Loop through input and duplicate value
     ‹*     Decrement the value and multiply
       ›    Increment value

```

Try it Online!
> 2 votes

# Answer
# Julia 1.0, ~~27~~ 22 bytes

```
~x=*(1,.~(0:x-1)...)+1

```

Try it online!

-5 bytes (!!) thanks to MarcMush: Replace `prod()` with `*()`; also, pad the argument list with 1 to avoid handling \\$a\_0\\$ as a special case
> 2 votes

# Answer
# Actually, ~~14~~ 12 bytes

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

```
2#,`;πu@o`nF

```

**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

```
> 1 votes

# Answer
# GolfScript, ~~12~~ 10 bytes

**2 bytes thanks to Dennis.**

```
~2\{.(*)}*

```

Try it online!

Uses `a(n) = a(n-1) * (a(n-1)-1) + 1`.
> 1 votes

# Answer
## R,  56 49 bytes

```
n=scan();x=2;for(i in 1:n){x=c(x,prod(x)+1)};cat(x[n+1])

```

### Ungolfed:

```
n=scan()            # Take input n
x=2                 # Initialize sequence to 2
for(i in 1:n){
  x=c(x,prod(x)+1)  # Append the product of the previous numbers + 1
}
cat(x[n+1])         # Print the nth + 1 number in seq

```

Slightly golfed thanks to @Frédéric:

```
n=scan();x=2;for(i in 1:n)x=c(x,prod(x)+1);x[n+1]

```
> 1 votes

# Answer
# PHP 5.6+ (46 bytes)

```
function f($n){return--$n?f($n)**2-f($n)+1:2;}

```
> 1 votes

# Answer
## PowerShell v2+, 56 bytes

```
param($n)$a=,2;0..$n|%{$a+=($a-join'*')+'+1'|iex};$a[$n]

```

Iterative version. Takes input, sets the first value in our array `$a`, loops. Each loop we take all of `$a`, `-join` them together with `*`, tack on a `+1`, and pipe to `Invoke-Expression` (similar to `eval`). That's stored as a new value on the end of `$a`. Then, we just index into `$a` for the requested number.

Calculates one index higher than necessary, which shouldn't be a problem. Output is solid until you reach the limits of round-trip precision issues and/or formatting issues where PowerShell converts to scientific notation.

```
PS C:\Tools\Scripts\golfing> 0..10|%{"$_ -> "+(.\sylvesters-sequence.ps1 $_)}
0 -> 2
1 -> 3
2 -> 7
3 -> 43
4 -> 1807
5 -> 3263443
6 -> 10650056950807
7 -> 1.13423713055422E+26
8 -> 1.28649386832787E+52
9 -> 1.65506647324521E+104
10 -> 2.73924503086033E+208

```

---

The recursive version is one byte longer, at **57 bytes**, using PowerShell's equivalent of a lambda -- `$x={param($n)if(!$n){2}else{(&$x(--$n))*((&$x($n))-1)+1}}`. Call it via something like `&$x(4)`

---

You could tack on a `[bigint]` for the `iex` expression to carry forward the good precision as follows -- `param($n)$a=,2;0..$n|%{$a+='[bigint]"'+($a-join'"*"')+'"+"1"'|iex};$a[$n]` for **73 bytes** (corrected thanks to Brad Gilbert b2gills).

```
PS C:\Tools\Scripts\golfing> 0..10|%{"$_ -> "+(.\sylvesters-sequence.ps1 $_)}
0 -> 2
1 -> 3
2 -> 7
3 -> 43
4 -> 1807
5 -> 3263443
6 -> 10650056950807
7 -> 113423713055421844361000443
8 -> 12864938683278671740537145998360961546653259485195807
9 -> 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443
10 -> 273924503086030314234102342916746862811943643675809146279473679416086920262269936343321184045824386349295487372839923697584879743063177305807538834294603
44956410077034761330476016739454649828385541500213920807

```
> 1 votes

# Answer
# MATL, 12 bytes

This can definitely be golfed further

```
Hiq:"tpQh]0)

```

This solution uses 1-based indexing.

**Try it online!**
> 1 votes

# Answer
# PARI/GP, ~~29~~ 25 bytes

```
a(n)=prod(i=0,n-1,a(i))+1

```

Thanks to alephalpha for shaving off 4 bytes.
> 1 votes

# Answer
# Maple 35 bytes

```
f:=n->`if`(n>0,f(n-1)^2-f(n-1)+1,2)

```

Usage:

```
> f:=n->`if`(n>0,f(n-1)^2-f(n-1)+1,2):
> seq(f(i),i=0..4);
  2, 3, 7, 43, 1807

```
> 1 votes

# Answer
## Pip, 11 bytes

```
Lao*:o+1o+1

```

The shortest way I've found so far. Uses the formula from Martin's Hexagony answer: define `b(0) = 1`, `b(n) = b(n-1) * (b(n-1) + 1)`, and then `a(n) = b(n) + 1`.

```
La           Loop number of times equal to cmdline input:
  o*:o+1     Multiply o by o+1 in place (o is a variable preinitialized to 1)
        o+1  Output o+1

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES2016), 25 bytes

```
f=x=>x--?f(x)**2-f(x)+1:2

```

Uses the zero-indexed sequence.

Here's an example:

```
f=x=>x--?f(x)**2-f(x)+1:2

const output = document.getElementById('output');

for(let i = 0; i < 10; i++)
  output.textContent += 'f(' + i + ') = ' + f(i) + '\n';
```

```
<pre id="output"></pre>
```
> 1 votes

# Answer
# Retina, ~~43~~ 26 bytes

Input and output are in unary (input in `1`'s, output in `x`'s.) The result is computed using `a(n+1) = a(n) * (a(n) - 1) + 1`, iterated `n` times.

```
^
xx
{`x(?=.*1)
$`$`
x1
xx

```

**Try it online**

Input and output in decimal (~~53~~ 36 bytes):

```
.*
$*
^
xx
{`x(?=.*1)
$`$`
}`x1
xx
.

```

Try it online

*Thanks to Martin for golfing 17 bytes*
> 1 votes

# Answer
## Javascript (ES6), 25 bytes

```
f=n=>n--?(n=f(n))*--n+1:2

```

Returns:

* the exact result for `n=0` to `n=6`
* an approximated value for `n=7` to `n=10`
* `Infinity` for `n>10`

```
f=n=>n--?(n=f(n))*--n+1:2

console.log(f(0))
console.log(f(1))
console.log(f(2))
console.log(f(3))
console.log(f(4))
console.log(f(5))
console.log(f(6))
console.log(f(7))
```
> 1 votes

# Answer
# Dyalog APL, 15 bytes

```
{×⍵:1+×/∇¨⍳⍵⋄2}

```

`×⍵:` if the argument is grater than zero:
`1+` one plus
`×/` the product of
`∇¨` this function applied to each of
`⍳⍵` first *n* integers (beginning with zero)
else:
`2` return two

0-based indexing – needs `⎕IO←0`.

TryAPL online!
> 1 votes

# Answer
# Python 3, ~~71 69 68 63~~ 57 bytes

**Python 3, ~~71 69~~ 68 bytes**

```
l=[2]
for _ in range(int(input())):
    n=1
    for i in l:n*=i
    l+=[n+1]
print(l[-1])

```

**Also 68 bytes:**

```
l=[2]
a=int(input())
while len(l)<a:
    n=1
    for i in l:n*=i
    l+=[n+1]
print(l[-1])

```

**EDIT:**

Thanks @WheatWizard for pointing out about using `n` instead of `no`, and removing the space between `for i in l` and `n*=i`.

Also thanks for pointing out about moving `int(input())` into the `range` function.

**EDIT 2:**

Thanks @WheatWizard for pointing out the iteration tip, it has allowed me to write these two, shorter, programs:

**Python 3, 63 bytes**

```
l=[2]
for _ in"a"*int(input()):
    n=1
    for i in l:n*=i
    l+=[n+1]
print(l[-2])

```

# **Python 3, 57 bytes**

```
l=[2]
for _ in"a"*int(input()):
    b=l[-1]
    l+=[(b-1)*b+1]
print(b)

```

The second code (57 bytes) does not follow the instructions for making the sequence (i.e: product of the sequence+1) instead it works on the fact that the last number will always be the product of the rest+1 meaning that instead of iterating through the sequence, I can multiply the last number by itself-1 and then add 1 back on.
> 1 votes

# Answer
# Perl, ~~28~~ ~~26~~ ~~23~~ 22 bytes

Includes +1 for `-p`

Run with the input (with 1-based indexing) on STDIN:

```
sylvester.pl <<< 5

```

`sylvester.pl`:

```
#!/usr/bin/perl -p
$.*=$_=$.+1for($_)x$_

```
> 1 votes

# Answer
# dc, 34 bytes

```
0sg[[d1-*1+Lgx]Sg1-d0<f]dsfx2Lgx++

```

This pops the argument from top of stack, and pushes the result to stack, as normal for dc.

### Annotated full program

```
#!/usr/bin/dc

# accept input
?

# initialise the bottom of the g-stack
0sg
# Add n iterations of recurrence formula
[[d1-*1+Lgx]Sg1-d0<f]dsfx
# Prime the 0th value
2
# Execute all of the g-stack
Lgx
# Last instruction left a zero on the stack
+
# Special case: if input is 0, f left a -1 behind.  This is a correction
# for wrongly doing 2->3 in that case
+

# print output
p

```

It works by using the recurrence relation described in OEIS: `a[n+1] = a[n]² - a[n] + 1`, starting with `a[0]==2`. Equivalently, `a[n+1] = a[n](a[n]-1) + 1`, written in dc as `d1-*1+`.

We push *n* copies of the program `d1-*1+` to the stack `g`, prime the main stack with the initial value `2`, and set off. There's a correction for *n*=0, because we always push at least one instance of the recurrence. Handily, we can fix that, because function `f` leaves -1 on the stack in that case, and 0 otherwise.

### Test output:

```
0: 2
1: 3
2: 7
3: 43
4: 1807
5: 3263443
6: 10650056950807
7: 113423713055421844361000443
8: 12864938683278671740537145998360961546653259485195807
9: 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443
10: 27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920807
11: 750346333909286311464218348364293017384724140073732363176684391768374238237200233203724274839819736227493060107386942069521875902258281351952761393460726027774387698896086030486687796275661950199835484418384103096899499524666007073298797852932127876923983340497448231960048833094195425231846478785035602339261149953564729371337917773386670133413581537490788020231265093210310224397095644371148893261284201611453610443
12: 563019620811106188735345793029131127645126456201508328395934709948713369875017428398616526515350801978901280848429236023780360625686785326318172135941491985234945009397938528773976977887356630327917721419666751591559883455828027643329740930320548089836575156581070880066847294722353255119648341271402723167206816552066010592134725124376810874159292118224274440907862996344067325025151751506647339684959479438354192989470470488621172745980086435801519575581664038703641801974453354864238123148678312993828328158261237284571445163949954735321181426755485563860804935755099928085508785637606452207007984638610604113718738727804169240213041488645142155664706600019329809186121988322464207409749450811638629159492106903853533242008723387118397794980575878357156285111258733862431522178328441469980110808406224908967784943255608168545045807
13: 316991093418281796980738587324498503465985663563441351614965595710659626509023026378810664917769979749230375616949095839488230630774365784766585678394020150307543448990686716629735821013846949520218610883960194258122308878890968113466913053158083723070515602776324450012006168592325685889943262781933132780014500164781142497008320197365141855119010118077705678576368755229432787283587491897170937657553086679827144799087397199129432233281774986701578182361474362882421927116451702868297347253630717771757957438615228337552613006602138504913204731416596016919892552584014059657038635241014722034375088903021315484876024289828564177721518967548558336213757430766087730295001595138792039193609746512786881659903942227205537012891959828532940594409566163694454653037016800027294499421291400492041597627904670868358757293568071192353450861046220903121264904877170553117406388566305811088048722332066039563082830094354238880920553702156022717609505663704069061610519598560624334935881397512984533454362321248854729174814176943381209734396537109715522733592519084452225492188715705481658124794599731527140827530319488791822858978924780015280035310521766457660381662363459675166288099343838361130665940967928850877954452552005403436587169730515877297387774041696625714088910160966686976352250237188765370786055553236020704945964404004577531357576565107610684603955726197582253686411381871520005412537060114403951740688011605681233186481569161991920354077827812176666950510226500521720520469387009627382085749910481677989034236154462513159644551504513525508614268492165297534777956118363272320828495465015734808069866823697938666550506233479919235237378935603448169915183235443
14: 100483353306517857188816511171973264968130481955993490961776578914384855009465596512878627978186320098524674810822809215084298821790532480217571435837318997038501027166944291436298311859998927368878478765662052261013905379683606908563327049366289350227874801320137528476359434996625155321924896471487253609774383161294073700386567438895729619959183688827019175395384990049660760826706275656247200320644562229907983316938796200727194177710641698165578469600709422183645673081099011178658794923207340118316226811044120124994280172667435132674250477913878334229469634774955766654959747171269329356217729819952093850230832136940392143299736102334976183356619572749168857678782222255344301700168226608019630704240193738779198063738629831841413772846575231497629810592678428725195220732911880790353530776313807267315574488856933933931968726196972550157616749777588888821303729634383570842953721086839502335017753789603211887639264756326943906234925564059713122739441052488376985825209930025027331642643833862623818612641648534007690784009230583997364206027891426162271405399576520661523570494921380174573570295575834537952976231451138917903119690734728050868143651943079046629073247009723903287946523072583428647088990713577505274669321894108556505593299658881909461644436220683735665670039545950199079805499092674406353548516096407916275052371510047476698658893306349068133879014809524920709542592832744670134019181012820484031829100985336532444887396195766078330294774788615792775829183741076029977456631131003360810557200089618493958319779112283680033864350359591347851857639767660909655544622503481811302270128415655545885368248621757558781407774929247336942808205264958129961178967782261436710020914320953492879039247990865098954170193648898076402861312803632817456574773061811978648089614340109760702469211985641224691799075765885167117855362986656144090527289697873066081524676142089795828969028242126025160985084779781007974719610529121366009147473928798323429514961662955075830495059188425232901129844306717176754536658533793214326255403412914373598713551532524170357661947859352181097102731800860434424406585016086605044703266455861041380556886689319004123095655013285849524741495205262970148746426581276319938997140587845485798731493239638046736464142096404810367841352036464369335995230683471276720095626585363049720580305501778636182605592068492151793190258602236893550140479021220581841241476297575889705144565984983772835663470728331437295945770147420128139970898197153180098987682528952187399111614545313650329728193759220800741639763444502297436225484681500013482802572032911312979385547883726365017125898034265710900263014307543995711388447583272341504352098242603013317289071851486202200363353430637400418445403028209289752937101610106546407815385279051077386957963745649023423516876644029840971378691516442745761797057396994687382618710236478541855961623090443801434726418529440871490091117324165342131670988126442133481305788646667033011070351616554711007362680081909808994105138595194669575127185645557552945017168697977343707144183186705714691228418618276386168995938283316172058534438295911377445943568762495111242585896098376432273844229629284777619272064792008892485171141118486114024760197688360378085790695965894817048250719620713759873671293320363983916413298621510321025850259140267373664767105414000002388170807
15: [encoded data, 6671 characters]
16: (13341 digits)
17: (26681 digits)
18: (53361 digits)
19: (106721 digits)
20: (213441 digits)
21: (426881 digits)
22: (853761 digits)
23: (1707522 digits)
24: (3415043 digits)
25: (6830085 digits)
26: (13660169 digits)
27: (27320338 digits)
28: (54640675 digits)
29: (109281349 digits)

```

As you can see, these numbers grow quite rapidly; the computation time also increases in the same proportion as the result length. It took me half a minute to compute `a(23)`, and several hours for `a(29)`.
> 1 votes

# Answer
# Groovy, 26 bytes

This answer was basically stolen from @Geobits.

```
a={n->n--?a(n)*~-a(n)+1:2}

```

Took that answer and, using groovy shortcuts, optimized it further.
> 1 votes

# Answer
# Common Lisp, 53 bytes

```
(defun f(n)(do((x 2(1+(* x(1- x)))))((<(decf n)0)x)))

```

The result is computed through the formula `a(n+1) = a(n) * (a(n) - 1) + 1`, starting from 2 and iterated n times.
> 1 votes

# Answer
# Japt `-g`, 6 bytes

Takes input as a singleton integer array, 1-indexed.

```
ÇÆiU×Ä

```

Try it

## Japt `-h`, 6 bytes

Takes input as an integer, 1-indexed.

```
ÆßX ×Ä

```

Try it

## Original w/o flag, ~~9~~ 8 bytes

Takes input as an integer, 0-indexed.

```
@ÒZ×}gNÅ

```

Try it
> 1 votes

# Answer
# Husk, ~~11~~ 7 bytes

```
!¡o→Π;2

```

Try it online!

1-indexed.

-4 bytes from Leo.
> 1 votes

# Answer
# AWK, 32 bytes

```
{for(n=2;$0>i++;n=n*n-n+1);}$1=n

```

Try it online!
> 1 votes

# Answer
# Vyxal `m`, 5 bytes

```
λvxΠ›

```

Try it Online!

Jelly port.
> 1 votes

# Answer
# Thunno 2, 7 bytes

```
2${D⁻×⁺

```

Attempt This Online!

Port of Emigna's 05AB1E answer.

#### Explanation

```
2${D⁻×⁺  # Implicit input
2        # Start with 2
 ${      # Input number of times:
   D⁻×   #  Multiply by x-1
      ⁺  #  And increment
         # Implicit output

```
> 1 votes

# Answer
## Perl6, 49 bytes

```
my &f={my @c=2;@c.push: 1+[*] @c for ^$_;@c[*-1]}

```

Ungolfed:

```
sub f($n) {
  my @sylvester = 2; # declare an array to store the previous
                     # values of the sequence
  # insert S(1) ... S(n) (n iterations)
  @sylvester.push(1 + [*] @sylvester) for 0..^$n;
  return @sylvester[* - 1]; # return last element
}

```
> 0 votes

# Answer
# Scala, 85 bytes (51?)

```
val s:Stream[BigInt]=2#::3#::s.tail.map{c=>c*c-c+1}
print(s.take(args(0).toInt).last)

```

3 less if I stick with an Int. The stream bit which actually does all the work is 51 bytes. The rest is just printing

Usage:

```
$ scala sylvester.scala 20

```
> 0 votes

# Answer
## Batch, 70 bytes

```
@set/ap=r=2
@for /l %%i in (1,1,%1)do @set/at=p,p*=r,r=t+1
@echo %r%

```

Zero indexed, uses @LeakyNun's recurrence relation. Conveniently `set/a` works inside a `for` loop, because I'm not using `%` substitution.
> 0 votes

# Answer
# Javascript (Using external library - Enumerable) (52 bytes)

```
n=>_.Sequence(n,(i,a)=>_.From(a).Product()+1).Last()

```

Link to lib: https://github.com/mvegh1/Enumerable

Code explanation: Static method on library "Sequence" will generate a sequence of elements for a count of 'n', according to the predicate accepting params "i"teration, "a"ccumulated-array. The predicate states to cast the array to the library's Enumerable data-type, use the built in Product method on it, then add 1 to that value. After the sequence is generated, take the last value because the problem states to just find the 'N'th element of the sequence
> 0 votes

# Answer
# Sesos, 17 bytes

Hexdump:

```
0000000: ae2cf0 20f8be b273d0 7d9cde a0dd3b 7e3e           .,. ...s.}....;~>

```

Try it online!
> 0 votes

# Answer
# UGL, 15 bytes

```
cuuild@$d*u@:_o

```

Try it online!
> 0 votes

# Answer
## Pyke, 9 bytes

```
[SOm[BhRK

```

Try it here!
> 0 votes

# Answer
## Perl, 35 bytes

```
$a=2;$a=$a**2-$a+1 for 1..<>;say $a

```

Might be shorter with a recursive function but I couldn't get that to work in my few attempts
> 0 votes

# Answer
**C, 44 bytes**

```
g(i,j){return i<2?2:(j=g(i-1,0),j*(j-1)+1);}

```
> 0 votes

# Answer
# ForceLang, 193 bytes

Noncompeting, as for some reason I forgot to give the language's lists a `len` method when I first implemented them.

```
def s set
def l a.len()
s g goto
s n io.readnum()
s n n+1
s a []
s b 1
label 1
s n n+-1
s a[l] b+1
if n=0
g 3
s b 1
s i 0
label 2
s b b.mult a[i]
s i i+1
if i=l
g 1
g 2
label 3
io.write a[l+-1]

```
> 0 votes

# Answer
## Racket 74 bytes

```
(define(f n(l'(2)))(if(< n 2)(reverse l)(f(- n 1)(cons(+(apply * l)1)l))))

```

Detailed version:

```
(define (f n (l '(2)))
  (if (< n 2)
      (reverse l)
      (f (- n 1) (cons (+ 1 (apply * l)) l))))

```

Testing:

```
(f 7)

```

Output:

```
'(2 3 7 43 1807 3263443 10650056950807)

```
> 0 votes

# Answer
# C#, 144 Bytes

I used one indexing:

Golfed:

```
int s(int n){var a=new int[n];int b=1;for(int i=0;i<a.Length;i++){a[i]=b;b=1;a.ToList().GetRange(0,i).ForEach(o=>b*=o);a[i]=b+1;}return a[n-1];}

```

Ungolfed:

```
class SylvestersSequence
{
public int s(int n)
{
  var a = new int[n];

  int b = 1;

  for (int i = 0; i < a.Length; i++)
  {
    a[i] = b;

    b = 1;

    a.ToList().GetRange(0, i).ForEach(o => b *= o);

    a[i] = b + 1;
  }

  return a[n - 1];
}
}

```

Tests:

```
1 : 2
2 : 3
3 : 7
4 : 43
5 : 1807
6 : 3263443

```

(Things start to go a bit weird after this...)
> 0 votes

# Answer
# Forth (gforth), 35 bytes

Answer uses 0-indexing

```
: f 2 swap 0 ?do dup 1- * 1+ loop ;

```

Try it online!

### Explanation

1. place 2 on stack
2. loop from 0 to n-1
    1. multiply top of stack by itself minus 1
    2. add 1

### Code Explanation

```
: f             \ Start a new word definition
  2 swap        \ place 2 on the top of the stack
  0 ?do         \ loop from 0 to n-1 (skip loop if n=0)
    dup 1-      \ duplicate top of stack and subtract 1
    *           \ multiply top two stack values
    1+          \ add 1 to result
  loop          \ end loop
;               \ end word definition

```
> 0 votes

# Answer
# 05AB1E, 8 bytes

```
2λλP>}sè

```

Not shorter than the existing 05AB1E (legacy) answer by *@Emigna*, but I wanted to try out the new recursive function in the 05AB1E Elixir-rewrite.

Try it online or verify all test cases.

**Explanation:**

```
2λ   }      # Define a recursive sequence function starting at a(0) = 2
  λ         #  Generates a recursive infinite sequence-list [a(0), a(1), a(2), ...]
   P>       #  where each a(n) takes the product + 1 of all previous results
            #   i.e. [2,3,7,43,1807,3263443,10650056950807,...]
      s     # Swap so the input is at the top of the stack
       è    # Get the 0-indexed value of the infinite recursive sequence-list
            #  i.e. 4 and [2,3,7,43,1807,3263443,10650056950807,...] → 1807

```
> 0 votes

# Answer
## C++, 43 bytes

```
[&](int n){return n?f(n-1)*(f(n-1)-1)+1:2;}

```

Try it Online!
> 0 votes

# Answer
# cQuents, 9 bytes

```
=2:ZZ-Z+1

```

1-indexed.

Try it online!

## Explanation

```
=2          first term is 2
  :         given input n, output nth term
            each term equals
   ZZ-Z+1   previous * previous - previous + 1

```
> 0 votes

# Answer
# Zsh, 35 bytes

```
for ((A=2;n++<$1;A=A*~-A+1)):
<<<$A

```

Try it online!
> 0 votes

# Answer
# JavaScript, 28 bytes

A function. Expect a number as input.

`f=n=>n?f(n-1)*(f(n-1)-1)+1:2`

Using the formula `a[n] = a[n-1] * ( a[n-1] - 1 ) + 1`.

**Explanation**. The ungolfed and commented version:

```
var f = (n) => {                 // Define a function
  n ?                            // If n is not zero...
                                 // (non-negative numbers and TRUE booleans are
                                 // equivalent in JavaScript)
    f(n-1) * (f(n-1) - 1) + 1    // Then use the recurrence formula.
    :                            // Else, if n is zero...
    2                            // Return 2 to end recurrence.
}

```
> 0 votes

# Answer
# MMIX, 24 bytes (6 instrs)

Works mod \\$2^{64}\\$. One-based indexing.

(jxd)

```
00000000: e3ff0001 2301ff01 1affff01 27000001  ẉ”¡¢#¢”¢ȷ””¢'¡¡¢
00000010: 5b00fffd f8020000                    [¡”’ẏ£¡¡

```

Disassembly:

```
sylv    SET  $255,1         // b(1)=1
0H      ADDU $1,$255,$1     // loop: a(n) = b(n) + 1
        MULU $255,$255,$1   // b(n+1) = a(n) * b(n)
        SUBU $0,$0,1
        PBNZ $0,0B          // if(--i) goto loop
        POP  2,0            // return a

```
> 0 votes

# Answer
# Fig, \\$5\log\_{256}(96)\approx\\$ 4.116 bytes

```
}rMXr

```

Try it online!

Port of Jelly. Link contains extra code to run all test cases.

```
}rMXr
    r # Range [0, n)
  MX  # Map by this function
 r    # Product
}     # Increment

```
> 0 votes

# Answer
# Go, 59 bytes, `int` only

```
func f(n int)int{if n<1{return 2}
k:=f(n-1)
return k*k-k+1}

```

Attempt This Online!

# Go, 126 bytes, arbitrarily large outputs

```
import."math/big"
func f(n int)*Int{i,l:=NewInt,new(Int)
if n<1{return i(2)}
k:=f(n-1)
return l.Add(l.Sub(l.Mul(k,k),k),i(1))}

```

Attempt This Online!
> 0 votes

# Answer
# Nekomata, 7 bytes

```
2ᶦ{:←*→

```

Attempt This Online!

Takes no input, and outputs all terms of the Sylvester's sequence.

```
2ᶦ{:←*→
2           Start with 2
 ᶦ{         Infinite loop:
   :            Duplicate
    ←           Decrement
     *          Multiply
      →         Increment

```
> 0 votes

---
Tags: code-golf, sequence
---


# Question
Title: Shortest English prompt to produce LLM falsehood
Since programming is predicted to become natural linguisized by the unstoppable advances in LLM technology, perhaps we can code golf LLMs themselves.

Produce the shortest question that is not an arithmetic problem (we know it sucks at multiplication problems) that produces an obvious falsehood from ChatGPT with screenshot as evidence.

Extra points if the error is reproducible by others (perhaps it was generated with low temperature), not one even a child would make, or is particularly hilarious.

Use GPT4 if you have access.

# Answer
> 8 votes
# GPT3.5 model, 1 byte

Hexdump: `0x01`

It doesn’t look like a blank message…

Chat Link

# Answer
> 7 votes
## 12 characters (GPT-4)

```
Query: eerie sorted
GPT-4: Sorting the word "eerie" alphabetically results in "eeeri".

```

This one's quite inconsistent. The longer "Sort letters eerie", though, elicited a wrong answer 10/10 times, always with an extra r and sometimes an extra e, though the letters' ordering was correct.

# Answer
> 7 votes
# ChatGPT 3.5 - 5 bytes

```
Vyxal

```
1. APL and J aren't golfing languages
2. APL and J weren't inspirations for Vyxal (I know this because I didn't take anything from J)

# Answer
> 6 votes
# GPT-3.5, 2 bytes

```
_?

```

I entered a little more than an underscore, so it's somewhat of a falsehood.

# Answer
> 5 votes
# 9 characters (GPT-3.5)

> \[User\] am i dead
>
> \[GPT-3.5\] I'm just a computer program, so I can't determine your current state of being. If you're feeling uncertain or concerned about your health, I would strongly recommend seeking immediate medical attention or contacting a healthcare professional. They can provide you with the necessary assistance and guidance to address any health-related concerns.

One could argue this is clearly false, since if I am interacting with the model then I must be alive. (However, that is up for debate.)

# Answer
> 4 votes
# 17 bytes (ChatGPT)

ChatGPT sucks at code golf.

“th shrtst js quine”

The code it posted doesn’t work because it doesn’t include the `console.log(JSON.stringify())` bit, and is also not the shortest.

# Answer
> 4 votes
# ChatGPT, 5 bytes

“pi 97”

> The value of pi (π) to 97 decimal places is: 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

This is pi to 100 decimal places, not 97.

# Answer
> 0 votes
## 44 Characters (ChatGPT 3.5)

> User: "banana" sorted reverse lexicographically is
>
> ChatGPT: When the word "banana" is sorted in reverse lexicographical order (from Z to A), it becomes "nnaaab."

---
Tags: natural-language, error-message
---


# Question
Title: Sums of Euler's totient function in sublinear time
Related.

Given a number \\$n\\$, Euler's totient function, \\$\varphi(n)\\$ is the number of integers up to \\$n\\$ which are coprime to \\$n\\$. That is, no number bigger than \\$1\\$ divides both of them. For example, \\$\varphi(6) = 2\\$, because the only relevant numbers are \\$1, 5\\$. This is OEIS A000010.

We can now define the sum of euler's totient function as \\$S(n) = \sum\_{i=1}^{n}{\varphi(i)}\\$, the sum of \\$\varphi(i)\\$ for all numbers from \\$1\\$ to \\$n\\$. This is OEIS A002088.

Your task is to calculate \\$S(n)\\$, **in time sublinear in \\$\mathbf{n}\\$,** \\$o(n)\\$.

## Test cases

```
10 -> 32
100 -> 3044
123 -> 4636
625 -> 118984
1000 -> 304192
1000000 (10^6) -> 303963552392
1000000000 (10^9) -> 303963551173008414

```

## Rules

* **Your complexity must be \\$o(n)\\$**. That is, if your algorithm takes time \\$T(n)\\$ for input \\$n\\$, you must have \\$\lim\_{n\to\infty}\frac{T(n)}n = 0\\$. Examples of valid time complexities are \\$O(\frac n{\log(n)})\\$, \\$O(\sqrt n)\\$, \\$O(n^\frac57 \log^4(n))\\$, etc.
* You can use any reasonable I/O format.
* Note that due to the limited complexity you can't take the input in unary nor output in it (because then the I/O takes \\$\Omega(n)\\$ time), and the challenge might be impossible in some languages.
* Your algorithm should in theory be correct for all inputs, but it's fine if it fails for some of the big test cases (due to overflow or floating-point inaccuracies, for example).
* Standard loopholes are disallowed.

This is code golf, so the shortest answer in each language wins.

# Answer
> 3 votes
# Charcoal, ~~121~~ ~~99~~ 98 bytes

```
⊞υＮ≔⦃⦄ηＦυＦ¬§ηι«≔ιζ≔²ε≔÷ιεδ≔⟦⟧κＷ›δ¹«≔⊕÷ιδλ¿§ηδ≧⁺×⁻λε⊖⊗§ηδζ⊞κδ≔λε≔÷ιλδ»¿κＦ⊞Ｏκι⊞υλ§≔ηι÷⁺⁻×ιιζε²»Ｉ§η⊟υ

```

Attempt This Online! Link is to verbose version of code. Explanation: Ports the sublinear Python solution mentioned by @CommandMaster.

```
⊞υＮ

```

Input `n`.

```
≔⦃⦄η

```

Set up a dictionary to cache calculated results.

```
Ｆυ

```

Loop over the values that need to be calculated.

```
Ｆ¬§ηι«

```

Verify that this value hasn't actually been calculated.

```
≔ιζ≔²ε≔÷ιεδ≔⟦⟧κＷ›δ¹«≔⊕÷ιδλ¿§ηδ≧⁺×⁻λε⊖⊗§ηδζ⊞κδ≔λε≔÷ιλδ»

```

Try to calculate the result for this value, but if any dependent values haven't yet been calculated, collect them in a list.

```
¿κＦ⊞Ｏκι⊞υλ

```

If there were any dependent values that haven't yet been calculated then add them for processing and add the current value for reprocessing.

```
§≔ηι÷⁺⁻×ιιζε²

```

Otherwise actually calculate the result for the current value.

```
»Ｉ§η⊟υ

```

Output the result for the initial value, which is always the last value to be calculated.

Edit: Saved 1 byte thanks to @JonathanAllan.

# Answer
> 3 votes
# Ruby, ~~104~~ 100 bytes

Ports the algorithm at https://oeis.org/A002088. -4 bytes from Jonathan Allan.

```
A=->n,r=({0=>0}){r[c=n]||(k=n/i=2
(j=n/k+1;c+=(j-i).*2*A[k,r]-1;k=n/i=j)while k>1
r[n]=(n*n-c+i)/2)}

```

Attempt This Online!

# Answer
> 2 votes
# JavaScript (ES12), 75 bytes

Adapted from the Python code provided on OEIS.

```
f=(n,j=2,K)=>f[n]||=n>j?f(K=n/j|0)*(j+=J=~(n/K))-j/2+f(n,-J):n&&(n*~-n+j)/2

```

Attempt This Online!

### Statistics

Assuming the cache is cleared after each call to `f`:

| \\$n\\$ | total number of calls |
| --- | --- |
| 10 | 15 |
| 100 | 193 |
| 1000 | 1407 |
| 10000 | 9111 |
| 100000 | 55009 |

# Answer
> 2 votes
# Rust, 161 bytes

Adapted from the Python code provided on A002088

---

Golfed version. Try it online!(TIO has no `cached` crate, you need to run it locally.)

```
use cached::proc_macro::cached;
#[cached]
fn f(n:i32)->i32{let(mut c,mut j,mut v)=(0,2,n/2);while v>1{let b=n/v+1;c+=(b-j)*(2*f(v)-1);j=b;v=n/b;}(n*(n-1)-c+j)/2}

```

Ungolfed version. Try it online!

```
use std::collections::HashMap;

struct A002088 {
    cache: HashMap<i32, i32>,
}

impl A002088 {
    fn new() -> Self {
        let mut cache = HashMap::new();
        cache.insert(0, 0);
        A002088 { cache }
    }

    fn get(&mut self, n: i32) -> i32 {
        match self.cache.get(&n) {
            Some(&result) => result,
            _ => {
                let mut c = 0;
                let mut j = 2;
                let mut k1 = n / j;
                while k1 > 1 {
                    let j2 = n / k1 + 1;
                    c += (j2 - j) * (2*self.get(k1) - 1);
                    j = j2;
                    k1 = n / j2;
                }
                let result = (n * (n - 1) - c + j) / 2;
                self.cache.insert(n, result);
                result
            }
        }
    }
}

fn main() {
    let mut a002088 = A002088::new();
    let result = a002088.get(10000);
    println!("{}", result);
}

```

---
Tags: code-golf, math, number-theory, restricted-complexity
---