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

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

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 , so the shortest correct program, measured in bytes, wins.

• Why not allow infinite output instead of taking input? – John Dvorak Feb 19 '17 at 16:44
• @JanDvorak: Because that forces all programs to use algorithms that generate every term; this method of writing the question leaves it up to the answerers whether they want to do that, or whether they want to use a closed-form formula (assuming there is one). So it gives more of a choice of strategies in solving the question. – user62131 Feb 19 '17 at 20:57
• I'd assume the sequence isn't there because 0,4 is a strange offset – boboquack Feb 20 '17 at 7:04
• @boboquack With (0,3), (0,2), (1,4) or similar variations, the sequence would be constant after a few terms. – Dennis Feb 20 '17 at 19:32
• Does the [math] tag make sense for this? – mbomb007 Feb 20 '17 at 22:33

# Jelly, 1312 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
¡  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.


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

# Python 2, 5854 50 bytes

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


Try it online!

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


# Oasis, 11 bytes

### Code:

+>bc-*2/640


### Explanation:

To visualize the relation of fn, let's take the example f5. To calculate f5, 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 f4. The 7 + 8 + 9 + 10 part is the range [fn-2 + 1, fn-1 - 1]. That makes the formula fn-1 + Σ [fn-2 + 1 ... fn-1 - 1] (Wolfram link):

fn = 0.5 × (fn-12 - fn-22 + fn-1 - fn-2)

Which can be rewritten to:

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

fn = 0.5 × ((fn-1 - fn-2)(fn-1 + fn-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!

• Explanation? This has got me more curious than many of the other answers. – user62131 Feb 19 '17 at 11:43
• @ais523 I've added an explanation. – Adnan Feb 19 '17 at 18:25

# Julia, 3933 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!

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


Try it online!

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


Try it online!

• To save an extra byte, use n<3?5n-n^2: rather than n<4?2(n>1)n: - note that it switches to using 0-based indexing, though. – Glen O Feb 19 '17 at 15:40
• @GlenO Thanks, 1 bytes saved! – rahnema1 Feb 19 '17 at 16:32

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

# PowerShell, 848988 87 bytes

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. • @AdmBorkBork very nice! I really think that's worthy of a distinct answer; the method is different enough that it wouldn't feel like my own if I used it. – briantist Feb 20 '17 at 15:14 • @AdmBorkBork nice, +1, and I did learn one thing from that: no ; needed after the for loop. Never realized that one before. – briantist Feb 20 '17 at 20:29 # 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! # Haskell, 42 bytes f 0=0 f 1=4 f 2=6 f n=sum[1+f(n-2)..f$n-1]


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


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.

• Whenever I come to a new challenge, someone's always made a haskell answer better than any I could ever make XD – theonlygusti Feb 19 '17 at 18:31
• I always arrive at some mathsy challenge, think "Hey finally I can try out haskell!" CMD-F 'Haskell' – oh wait nope, this answer... wait, what? Gives up on haskell – theonlygusti Feb 19 '17 at 18:32

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

# Perl 6,  52 49 44  35 bytes

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


Try it

{(0,(4,0),{[+](^.)-.,.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)
}


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

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

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


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

# Pyth - 15 bytes

ePu+Gs-UeGGQ,Z4


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

# ><>, 43+3 = 46 bytes

:2(?^&46v

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