A sequence of sums of integers that aren't in the sequence

Question

Background

Consider a sequence defined as follows:

• The first element is 0;
• The second element is 4;
• From the third element onwards, its value can be calculated by:
  • Taking the set of integers from 0 up to the previous element of the sequence (inclusive or exclusive, it doesn't matter);
  • Removing any integers that have already appeared earlier in the sequence from the set;
  • Adding together the remaining elements of the set; that's the value you want.

Interestingly, this sequence doesn't seem to be on OEIS yet.

The task

Write a program or function which takes an integer n as input, and outputs the nth element of the sequence.

Test cases

The first few elements of the sequence are:

• 0
• 4
• 6 (1+2+3)
• 11 (1+2+3+5)
• 45 (1+2+3+5+7+8+9+10)
• 969 (1+2+3+5+7…10+12…44)
• 468930 (1+2+3+5+7…10+12…44+46…968)

Clarifications

• Your program should in theory be able to handle arbitrary n if run on a variant of your language that has unboundedly large integers and access to an unlimited amount of memory. (Languages without bignums are unlikely to be able to get much beyond 468930, but that's no excuse to hardcode the answers.)
• You may choose either 0-based or 1-based indexing for the sequence (e.g. it's up to you whether n=1 returns the first element, n=2 the second element, and so on; or whether n=0 returns the first element, n=1 the second element, and so on).
• There are no requirements on the algorithm you use, nor on its efficiency; you may implement the definition of the sequence directly (even though it's really inefficient), and you may also implement a different algorithm which leads to the same results.

Victory condition

This is code-golf, so the shortest correct program, measured in bytes, wins.

Answer 1

Jelly, 13 12 9 bytes

rSạo4¥ð@¡

Uses 0-based indexing.

Try it online!

How it works

rSạo4¥ð@¡  Main link. No arguments. Implicit argument: 0

      ð    Collect everything to the left into a chain and start a new, dyadic one.
           The arity of the first chain is unknown at this point, as it isn't
           prefixed by ø, µ, or ð.
       @   Swap the arguments of the first chain. Swapping  arguments is only
           implemented for dyadic links, so this makes the chain dyadic.
        ¡  Read an integer n from STDIN and execute the chain n times. Taking the
           argument swap into account, the chain is executed first with 0 as left
           and right argument, then with the previous right argument as left
           argument and the previous return value as right argument.
           The return value of the last call is the return value of the quicklink
           and becomes the implicit output.

           Let's call the left argument x and the right argument y.
r            Range; yield [x, ..., y].
 S           Compute the sum of all integers in the range.
     ¥       Convert the two atoms to the left into a dyadic chain, and call that
             chain with arguments x and y.
   o4          Take the logical OR of x and 4, replacing a 0 with 4 and leaving
               positive integers untouched.
  ạ          Take the absolute difference of the sum to the left and the result of
             the logical OR to the right.

Answer 2

Python, 66 60 bytes

Thanks to @Dennis for shaving off 6 bytes!

f=lambda n:n>2and(f(n-1)-~f(n-2))*(f(n-1)-f(n-2))/2or(5-n)*n

It's not the golfiest piece of code ever, but it uses a formula that I made:

Where x on the right-hand side is f(n - 1), and y is f(n - 2).

Explanation:

The sum of continuous integers from a to b (inclusive) can be described by this formula:

amount * average

Where amount (amount of numbers) is described like so:

((a - b) - 1)

And average (the average of all numbers) is described like so:

(a + b) / 2

So the full formula is now:

  ((a - b) - 1)(a + b) / 2
= (a - b - 1)(a + b) / 2

The way we implement this formula into the final formula is to substitute a for f(n - 1), b for f(n - 2), which basically calculates the sum of all of the new terms, and add another f(n - 1) (which is now a) on, which is the sum of all previous terms.

Combining that together, we get:

  a + ((a - b - 1)(a + b) / 2)
= a + ((a^2 + ab - ab - b^2 - a - b) / 2)
= a + ((a^2 - b^2 - a - b) / 2)
= (a^2 - b^2 - a - b + 2a) / 2
= (a^2 - b^2 + a - b) / 2
= ((a + b)(a - b) + (a - b)) / 2
= (a + b + 1)(a - b) / 2

Replace a with x and b with y, and hey presto, you have to formula above.

Answer 3

Python 2, 58 54 50 bytes

r=t=0
exec'r,t=t+r*~-r/2or 4,t-r;'*input()
print r

Try it online!

Answer 4

Mathematica, 49 48 bytes

±2=4;±1=0;±n_:=Tr@Range@±(n-1)-Tr@Array[±#&,n-1]
(* or *)
±2=4;±1=0;±n_:=-Tr@Array[(k=±#)&,n-1]+Tr@Range@k

Uses CP-1252 encoding. Defines function PlusMinus (±). 1-indexed.

Explanation

±2=4;±1=0;±n_:=Tr@Range@±(n-1)-Tr@Array[±#&,n-1]

±2=4;±1=0;                                        (* Define ±1 and ±2 *)
          ±n_:=                                   (* ±n equals ... *)
               Tr@Range@±(n-1)                    (* Sum of (1, 2, ..., ±(n-1)) ... *)
                              -Tr@Array[±#&,n-1]  (* Minus the sum of previous terms *)

Answer 5

Oasis, 11 bytes

Code:

+>bc-*2/640

Explanation:

To visualize the relation of f_n, let's take the example f₅. To calculate f₅, let's take a look at the following sum:

1 + 2 + 3 + 5 + 7 + 8 + 9 + 10

The bold part is just the same as f₄. The 7 + 8 + 9 + 10 part is the range [f_n-2 + 1, f_n-1 - 1]. That makes the formula f_n-1 + Σ [f_n-2 + 1 ... f_n-1 - 1] (Wolfram link):

f_n = 0.5 × (f_n-1² - f_n-2² + f_n-1 - f_n-2)

Which can be rewritten to:

f_n = 0.5 × ((f_n-1 - f_n-2)(f_n-1 + f_n-2) + (f_n-1 - f_n-2))

f_n = 0.5 × ((f_n-1 - f_n-2)(f_n-1 + f_n-2 + 1))

Which is the formula that we will be using in the code:

Code explanation

The 640 part gives us the base cases:

a(0) = 0
a(1) = 4
a(2) = 6

The code that will be executed (which defines a(n)):

+>bc-*2/

+          # Add a(n + 1) and a(n + 2) implicitly
 >         # Add one to get a(n + 1) + a(n + 2) + 1
  b        # Push a(n + 1)
   c       # Push a(n + 2)
    -      # Subtract from each other
     *     # Multiply with the previous result
      2/   # Halve the result

Try it online!

Answer 6

Julia, 39 33 32 bytes

!n=n<3?5n-n^2:sum(!(n-2)+1:!~-n)

0-based.

Thanks to @Dennis, saved 6 bytes.

Thanks to @GlenO, saved a byte.

Try it online!

Previous answer 1- based:

!n=n<4?2(n>1)n:sum(!(n-2)+1:!~-n)

Try it online!

Previous ungolfed answer 1-based :

f(n)=n<4?n<2?0:n*2:sum(f(n-2)+1:f(n-1))

Try it online!

Answer 7

JavaScript (ES6), 47 bytes

f=(n,b=4,a=6)=>n?--n?f(n,a,(a+b+1)*(a-b)/2):b:0

Uses the recurrence relation that f(n) = sum(range(f(n-2) + 1, f(n-1) + 1)) for n > 2.

Answer 8

PowerShell, 84 89 88 87 bytes

$OFS='+'
for($a=0,4;$a.Count-le($n="$args")){$a+=("$(1..$a[-1])"|iex)-("$a"|iex)}$a[$n]

Try it online!

Explanation

0-based indexing. Only works through n = 6 (on my Windows machine it crashes with a stack overflow for n = 7).

Using the same method as JungHwan Min's answer (sum of the range minus sum of previous terms).

Summing a range/array in PowerShell is long, so I'm using a trick of joining a n array with + to create a long expression (like 1+2+3+4...etc) and then sending it through iex (Invoke-Expression).

Since I need to do it twice, instead of using -join I'm setting the special variable $OFS, which stands for output field separator. When you stringify an array, this is the character used to the join the elements; it default to a space. So by setting it to + (once), I can replace something like $a-join'+'|iex with "$a"|iex.

A simple for loop keeps going until the sequence count is less than or equal to the input integer, then I return the $nth element.

Answer 9

MATL, 17 16 bytes

OKi:"tP:yX-sv]G)

1-based indexing is used. The code is very inefficient. For n = 6 it already exceeds the memory limit of the online compiler.

Try it online!

How it works

O       % Push 0
K       % Push 4
i       % Input n
:"      % Do the following n times
  t     %   Push a copy of the top array (or number)
  P:    %   Range from 1 to the last element of array
  y     %   Push a copy of the second-top number/array
  X-    %   Set difference
  s     %   Sum
  v     %   Concatenate everything into a column vector
]       % End
G)      % Get n-th entry of the array. Implicity display

---

For 20 bytes, the following version avoids the memory limitation. But there's still the data type limitation (double type can only guarantee that integers are accurately represented up to 2^53), so results are valid up to n = 8 only.

OKi:"t0)tQ*2/ys-v]G)

Try it online too!

Answer 10

Haskell, 42 bytes

f 0=0
f 1=4
f 2=6
f n=sum[1+f(n-2)..f$n-1]

Try it online!

This directly implements the recurrence that for n>2, f(n) equals f(n-1) plus the sum of the open interval from f(n-2) to f(n-1) which again is equal to the sum of the half-open interval from f(n-2) to f(n-1) inclusive.

f(0) = 0
f(1) = 4
f(2) = 6 = 1+2+3
f(3) = 11 = 1+2+3+5 = 6 + 5 = 6 + sum]4,6[ = f(2)+ sum]f(1),f(2)[ = sum]f(1),f(2)]
...
f(n) = sum]f(n-2),f(n-1)] = sum[f(n-2)+1,f(n-1)]

Answer 11

Haskell, 31 bytes

m#s=m:s#sum[m+1..s]
((0:4#6)!!)

Usage example: ((0:4#6)!!) 6 -> 468930. Try it online!.

Simple recursion, that keeps track of the maximum element m so far and the next value s.

Answer 12

JavaScript, 123 119 bytes

(a,i=x=y=0)=>{r=[0,4];while(r.length<a){x++;y=0;for(i=0;i<r[x];i++){if(!r.includes(i)){y+=i;}}r.push(y)}return r[a-1];}

Try it online! This solution is 1-based, f(1) => 0.

Answer 13

Perl 6,  52 49 44  35 bytes

{(|(0,4 X 0),{[+](^.[0])-.[1],.[0]+.[1]}...*)[$_;0]}

Try it

{(0,(4,0),{[+](^.[0])-.[1],.[0]+.[1]}...*)[$_;0]}

Try it

{(0,(4,0),{[+](^.[0])-.[1],.sum}...*)[$_;0]}

Try it

{(0,4,6,{[+] $^a^..$^b}...*)[$_]}

Try it

Expanded:

{ # bare block lambda with implicit parameter ｢$_｣

  (
    # generate a sequence

    0, 4, 6,      # seed the sequence

    {             # lambda with placeholder parameters ｢$a｣ ｢$b｣
      [+]         # reduce with ｢&infix:<+>｣
          $^a     # n-2
          ^..     # Range that excludes the first value
          $^b     # n-1
    }
    ...           # keep generating values until
    *             # never stop

  )[ $_ ]         # get the value that was asked for (0 based index)
}

Answer 14

PowerShell, 77 73 bytes

param($n)$a=0,4;1..$n|%{$a+=(0..$a[-1]|?{$_-notin$a})-join'+'|iex};$a[$n]

Try it online!

Implements the algorithm as defined, and is 0-indexed. Input of 6 is too much for TIO to handle.

Sets $a to be an array [0,4]. Loops from 1 up to input $n. In the loop, we take the range of numbers from 0 up to the biggest number we have $a[-1], and use a Where-Object clause |?{...} to pull out only those numbers that are not already present. That array of numbers is -joined together with +s, and then fed to iex (short for Invoke-Expression and similar to eval). That value is then array-concatenated onto the end of $a. Finally, we exit our loop, and take the $nth number in our array. That number is left on the pipeline, and output is implicit.

Answer 15

Python 2, 85 bytes

def g(n):
 if n<2:return n*4
 s=set(map(g,range(n)));return sum(set(range(max(s)))-s)

Try it online!

Answer 16

Batch, 108 bytes

@if %1==0 echo 0&exit/b
@set/ab=4,a=6
@for /l %%i in (2,1,%1)do @set/ac=(a+b+1)*(a-b)/2,b=a,a=c
@echo %b%

Port of my JavaScript answer.

Answer 17

dc, 47 bytes

?d1-scd/4*dd[d1+*2/r-dsn+dlnlc1-dsc0<x]sxlc0<xp

Works with integers as large as you want, up to the memory capacity of the computer.

Try it online!

0-based indexing, input on stdin, output on stdout. (There's also output on stderr, which is to be ignored.)

Sample runs:

$ for ((j=0;j<12;j++)){ echo -n "$j ";dc -f sumseq.dc <<<"$j";echo;} 2>/dev/null
0 0

1 4

2 6

3 11

4 45

5 969

6 468930

7 109947436950

8 6044219445882138462810

9 18266294354989892462984673364511343859409730

10 166828754731567805766174036610844675771635260155825966927845486666328\
837158267993261860

11 139159167026428037700805570917048711514125048327321592278500415852500\
422178720517080334552793040951056255170819719745908378102737875659900\
61575545777065220385544711322919415

This uses the same algorithm as the following solution in bash, which is (a little) more readable:

Pure bash, 60 bytes

for((n=s=$1?4:0,k=1;k<$1;k++,s+=(n=n++*n/2-s))){ :;}
echo $n

But the bash program only works for inputs up to 7, since it hits integer overflow beyond that.

Answer 18

Pyth - 15 bytes

ePu+Gs-UeGGQ,Z4

Test Suite.

Answer 19

C# - 74 bytes

int A(int f){int e=4,i=1,s=0;for(;i++<f;)e=e*-~e/2-(s+=e);return f>0?e:0;}

Ungolfed:

int A(int f)
{
    int e = 4, 
        i = 1, 
        s = 0; // e is the last element, s is the sum of all previous elements
    for (; i++ < f; ) // calculate for indexes 1 through max (don't need the index, just a correct number of loop cycles)
        e = e * -~e / 2 - (s += e); // -~e => (e + 1), higher precedence to remove parentheses
    return f > 0 ? e : 0; //handle input 0 as a special case, which is 0
}

There is probably a way to convert this to a lambda to save even more, or something using the .Aggregate Function. Although currently I have no imports, so maybe it evens out?

Answer 20

><>, 43+3 = 46 bytes

Makes use of the formula presented in Adnan's and Qwerp-Derp's answers.

:2(?^&46v
}v?=&:&l<,2*{-$@:}+1+@:{::
*>n;>4

Expects the input to be present on the stack, so +3 bytes for the -v flag.

Try it online!

Answer 21

Stax, 14 bytes

╟s╒π4╬╪♀○¢fΦå┼

Run and debug it

0-indexed.

Answer 22

Vyxal, 14 bytes

04"?(Dtɽ$F∑J)i

Try it Online!