28
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Why not allow infinite output instead of taking input? \$\endgroup\$ – John Dvorak Feb 19 '17 at 16:44
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – user62131 Feb 19 '17 at 20:57
  • 1
    \$\begingroup\$ I'd assume the sequence isn't there because 0,4 is a strange offset \$\endgroup\$ – boboquack Feb 20 '17 at 7:04
  • 1
    \$\begingroup\$ @boboquack With (0,3), (0,2), (1,4) or similar variations, the sequence would be constant after a few terms. \$\endgroup\$ – Dennis Feb 20 '17 at 19:32
  • \$\begingroup\$ Does the [math] tag make sense for this? \$\endgroup\$ – mbomb007 Feb 20 '17 at 22:33

20 Answers 20

10
\$\begingroup\$

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.
\$\endgroup\$
10
\$\begingroup\$

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:

enter image description here

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.

\$\endgroup\$
9
\$\begingroup\$

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!

\$\endgroup\$
9
\$\begingroup\$

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 *)
\$\endgroup\$
8
\$\begingroup\$

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!

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

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Glen O Feb 19 '17 at 15:40
  • \$\begingroup\$ @GlenO Thanks, 1 bytes saved! \$\endgroup\$ – rahnema1 Feb 19 '17 at 16:32
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – briantist Feb 20 '17 at 15:14
  • 1
    \$\begingroup\$ @AdmBorkBork nice, +1, and I did learn one thing from that: no ; needed after the for loop. Never realized that one before. \$\endgroup\$ – briantist Feb 20 '17 at 20:29
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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)]
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Whenever I come to a new challenge, someone's always made a haskell answer better than any I could ever make XD \$\endgroup\$ – theonlygusti Feb 19 '17 at 18:31
  • \$\begingroup\$ 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 \$\endgroup\$ – theonlygusti Feb 19 '17 at 18:32
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Pyth - 15 bytes

ePu+Gs-UeGGQ,Z4

Test Suite.

\$\endgroup\$
0
\$\begingroup\$

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?

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy