Hintergrund

Betrachten Sie eine Sequenz, die wie folgt definiert ist:

• Das erste Element ist 0;
• Das zweite Element ist 4;
• Ab dem dritten Element kann sein Wert berechnet werden durch:
  • Nehmen Sie den Satz von Ganzzahlen von 0 bis zum vorherigen Element der Sequenz (einschließlich oder ausschließlich, es spielt keine Rolle);
  • Entfernen aller Ganzzahlen, die bereits früher in der Sequenz aufgetreten sind, aus der Menge;
  • Addiere die verbleibenden Elemente der Menge; Das ist der Wert, den Sie wollen.

Interessanterweise scheint diese Sequenz noch nicht auf OEIS zu sein .

Die Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die eine ganze Zahl n als Eingabe verwendet und das n- te Element der Sequenz ausgibt .

Testfälle

Die ersten Elemente der Sequenz sind:

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

Klarstellungen

• Ihr Programm sollte theoretisch in der Lage sein, beliebiges n zu verarbeiten, wenn es mit einer Variante Ihrer Sprache ausgeführt wird, die unbegrenzt große ganze Zahlen und unbegrenzten Speicherplatz hat. (Sprachen ohne Bignums werden wahrscheinlich nicht viel über 468930 hinaus kommen, aber das ist keine Entschuldigung, um die Antworten hart zu kodieren.)
• Sie können entweder 0-basierte oder 1-basierte Indizierung für die Sequenz wählen (z. B. liegt es an Ihnen, ob n = 1 das erste Element, n = 2 das zweite Element usw. zurückgibt oder ob n = 0 das erste Element zurückgibt , n = 1 das zweite Element und so weiter).
• Es gibt keine Anforderungen an den von Ihnen verwendeten Algorithmus oder dessen Effizienz. Sie können die Definition der Sequenz direkt implementieren (obwohl sie wirklich ineffizient ist), und Sie können auch einen anderen Algorithmus implementieren, der zu den gleichen Ergebnissen führt.

Siegbedingung

Das ist Code-Golf , also gewinnt das kürzeste richtige Programm, gemessen in Bytes.

Jelly , 13 12 9 Bytes

rSạo4¥ð@¡

Verwendet eine 0-basierte Indizierung.

Probieren Sie es online!

Wie es funktioniert

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.

Python, 66 60 Bytes

Vielen Dank an @Dennis für das Abschneiden von 6 Bytes!

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

Es ist nicht der geilste Code aller Zeiten, aber er verwendet eine Formel, die ich erstellt habe:

Wo xauf der rechten Seite ist f(n - 1)und yist f(n - 2).

Erläuterung:

Die Summe der kontinuierlichen ganzen Zahlen von abis b(einschließlich) kann durch diese Formel beschrieben werden:

amount * average

Wobei amount(Anzahl der Zahlen) wie folgt beschrieben wird:

((a - b) - 1)

Und average(der Durchschnitt aller Zahlen) wird wie folgt beschrieben:

(a + b) / 2

Die vollständige Formel lautet also jetzt:

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

Die Art , wie wir diese Formel in die endgültige Formel implementieren ist als Ersatz afür f(n - 1), bfür f(n - 2), die im Grunde die Summe aller von den neuen Bedingungen berechnet, und fügen Sie eine andere f(n - 1)(was jetzt ist a) auf, die die Summe aller vorherigen Bedingungen ist.

Wenn wir das zusammen kombinieren, erhalten wir:

  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

Ersetzen Sie amit xund bmit y, und hey presto, müssen Sie oben formeln.

Python 2 , 58 54 50 Bytes

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

Probieren Sie es 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

Verwendet die CP-1252-Codierung. Definiert die Funktion PlusMinus (±). 1-indiziert.

Erläuterung

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

Oase , 11 Bytes

Code:

+>bc-*2/640

Erläuterung:

Um die Beziehung von f _n zu visualisieren , nehmen wir das Beispiel f ₅ . Schauen wir uns zur Berechnung von f ₅ die folgende Summe an:

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

Der fettgedruckte Teil entspricht f ₄ . Der 7 + 8 + 9 + 10- Teil ist der Bereich [fn _-2 + 1, fn _-1 - 1] . Das ergibt die Formel f _n-1 + Σ [f _n-2 + 1 ... f _n-1 - 1] ( Wolfram-Verknüpfung ):

f _n = 0,5 × (f _{n - 1} ² - f _{n - 2} ² + f _{n - 1} - f _{n - 2} )

Welches kann umgeschrieben werden:

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

Welches ist die Formel, die wir im Code verwenden werden:

Code Erklärung

Das 640Teil gibt uns die Basisfälle:

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

Der auszuführende Code (der ein (n) definiert ):

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

Probieren Sie es online!

Julia, 39 33 32 Bytes

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

0-basiert.

Dank @Dennis, 6 Bytes gespart.

Dank @GlenO ein Byte gespeichert.

Probieren Sie es online!

Vorherige Antwort 1 basierend:

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

Probieren Sie es online!

Vorherige ungolfed Antwort 1-basiert:

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

Probieren Sie es online!

JavaScript (ES6), 47 Byte

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

Verwendet die Wiederholungsrelation, die f(n) = sum(range(f(n-2) + 1, f(n-1) + 1))für n> 2 gilt.

PowerShell , 84 89 88 87 Byte

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

Probieren Sie es online!

Erläuterung

0-basierte Indizierung. Funktioniert nur durch n = 6(auf meinem Windows-Rechner stürzt es mit einem Stapelüberlauf ab n = 7).

Verwenden der gleichen Methode wie die Antwort von JungHwan Min (Summe des Bereichs abzüglich der Summe der vorherigen Begriffe).

Das Aufsummieren eines Bereichs / Arrays in PowerShell ist lang, daher benutze ich einen Trick, um mit einem Array +einen langen Ausdruck (wie 1+2+3+4...etc) zu erstellen und ihn dann durch iex( Invoke-Expression) zu senden .

Da ich es zweimal machen muss, -joinsetze ich stattdessen die spezielle Variable $OFS, die für Ausgabefeldtrennzeichen steht. Wenn Sie ein Array stringifizieren, ist dies das Zeichen, das zum Verknüpfen der Elemente verwendet wird. Es wird standardmäßig ein Leerzeichen verwendet. Wenn +ich es also auf (einmal) setze, kann ich so etwas wie $a-join'+'|iexdurch ersetzen "$a"|iex.

Eine einfache forSchleife läuft so lange, bis die Sequenzzahl kleiner oder gleich der Eingangszahl ist. Dann gebe ich das $nth-Element zurück.

MATL , 17 16 Bytes

OKi:"tP:yX-sv]G)

1-basierte Indizierung wird verwendet. Der Code ist sehr ineffizient. Denn n = 6es überschreitet bereits die Speichergrenze des Online-Compilers.

Probieren Sie es online!

Wie es funktioniert

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

Bei 20 Byte vermeidet die folgende Version die Speicherbeschränkung. Es gibt jedoch immer noch die Einschränkung des Datentyps ( doubleTyp kann nur garantieren, dass Ganzzahlen bis zu genau dargestellt werden 2^53), sodass Ergebnisse nur bis zu gültig sind n = 8.

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

Probieren Sie es auch online aus !

Haskell , 42 Bytes

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

Probieren Sie es online!

Dies führt direkt das erneute Auftreten der für n>2, f(n)gleich f(n-1)plus die Summe des offenen Intervalls von f(n-2)bis f(n-1)wieder die aus der Summe aus dem halboffenen Intervall gleich ist f(n-2)zu f(n-1)einschließlich.

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

Haskell, 31 Bytes

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

Anwendungsbeispiel: ((0:4#6)!!) 6-> 468930. Probieren Sie es online! .

Einfache Rekursion, die das mbisherige maximale Element und den nächsten Wert festhält s.

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];}

Probieren Sie es online! Diese Lösung basiert auf 1 f(1) => 0.

Perl 6 ,  52 49 44  35 Bytes

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

Versuch es

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

Versuch es

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

Versuch es

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

Versuch es

Erweitert:

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

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

Probieren Sie es online!

Implementiert den Algorithmus wie definiert und ist 0-indiziert. Die Eingabe von 6ist zu viel für TIO.

Legt fest $a, dass es sich um ein Array handelt [0,4]. Schleifen von 1bis zu Eingabe $n. In der Schleife nehmen wir den Zahlenbereich von 0bis zu der größten Zahl, die wir haben $a[-1], und verwenden eine Where-ObjectKlausel |?{...}, um nur die Zahlen herauszuholen, die noch nicht vorhanden sind. Dieses Array von Zahlen wird -joinzusammen mit +s gebildet und dann zu iex(kurz für Invoke-Expressionund ähnlich zu eval) geführt. Dieser Wert wird dann auf das Ende von Array-verkettet $a. Schließlich verlassen wir unsere Schleife und nehmen die $nth-Zahl in unser Array. Diese Nummer bleibt in der Pipeline und die Ausgabe ist implizit.

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)

Probieren Sie es 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%

Port meiner JavaScript-Antwort.

Gleichstrom , 47 Bytes

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

Funktioniert mit Ganzzahlen, die bis zur Speicherkapazität des Computers beliebig groß sind.

Probieren Sie es online!

0-basierte Indizierung, Eingabe über stdin, Ausgabe über stdout. (Es gibt auch eine Ausgabe auf stderr, die ignoriert werden soll.)

Probeläufe:

$ 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

Dies verwendet den gleichen Algorithmus wie die folgende Lösung in bash, die (etwas) besser lesbar ist:

Pure Bash, 60 Bytes

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

Das Bash-Programm funktioniert jedoch nur für Eingaben bis zu 7, da es darüber hinaus auf einen Ganzzahlüberlauf trifft.

Pyth - 15 Bytes

ePu+Gs-UeGGQ,Z4

Test Suite .

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
}

Es gibt wahrscheinlich eine Möglichkeit, dies in ein Lambda zu konvertieren, um noch mehr zu sparen, oder etwas, das die .Aggregate-Funktion verwendet. Obwohl ich momentan keine Importe habe, gleicht es vielleicht aus?

> <> , 43 + 3 = 46 Bytes

Verwendet die Formel aus den Antworten von Adnan und Qwerp-Derp .

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

Erwartet, dass die Eingabe auf dem Stapel vorhanden ist, also +3 Byte für das -vFlag.

Probieren Sie es online!