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.
The first few elements of the sequence are:
- 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)
- 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.
This is code-golf, so the shortest correct program, measured in bytes, wins.