Fondo

Considere una secuencia definida de la siguiente manera:

• El primer elemento es 0;
• El segundo elemento es 4;
• A partir del tercer elemento, su valor puede calcularse mediante:
  • Tomando el conjunto de enteros desde 0 hasta el elemento anterior de la secuencia (inclusivo o exclusivo, no importa);
  • Eliminar todos los enteros que ya aparecieron anteriormente en la secuencia del conjunto;
  • Agregar todos los elementos restantes del conjunto; ese es el valor que quieres.

Curiosamente, esta secuencia aún no parece estar en OEIS .

La tarea

Escribir un programa o función que toma un número entero n como entrada, y da salida a la n -ésimo elemento de la secuencia.

Casos de prueba

Los primeros elementos de la secuencia son:

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

Aclaraciones

• En teoría, su programa debería ser capaz de manejar n arbitraria si se ejecuta en una variante de su lenguaje que tiene enteros ilimitados y acceso a una cantidad ilimitada de memoria. (Es improbable que los idiomas sin bignums puedan llegar mucho más allá de 468930, pero eso no es excusa para codificar las respuestas).
• Puede elegir la indexación basada en 0 o en 1 para la secuencia (por ejemplo, depende de usted si n = 1 devuelve el primer elemento, n = 2 el segundo elemento, etc.) o si n = 0 devuelve el primer elemento , n = 1 el segundo elemento, y así sucesivamente).
• No hay requisitos sobre el algoritmo que usa, ni sobre su eficiencia; puede implementar la definición de la secuencia directamente (aunque sea realmente ineficiente), y también puede implementar un algoritmo diferente que conduzca a los mismos resultados.

Condición de victoria

Este es el código de golf , por lo que gana el programa correcto más corto, medido en bytes.

Jalea , 13 12 9 bytes

rSạo4¥ð@¡

Utiliza indexación basada en 0.

Pruébalo en línea!

Cómo funciona

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

¡Gracias a @Dennis por reducir 6 bytes!

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

No es el código de golf más sofisticado, pero usa una fórmula que hice:

Donde está xel lado derecho f(n - 1), y yesf(n - 2) .

Explicación:

La suma de enteros continuos desde ahasta b(inclusive) se puede describir con esta fórmula:

amount * average

Donde amount(cantidad de números) se describe así:

((a - b) - 1)

Y average(el promedio de todos los números) se describe así:

(a + b) / 2

Entonces la fórmula completa es ahora:

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

La forma en que aplicamos esta fórmula en la fórmula final es sustituir apor f(n - 1), bpara f(n - 2), que, básicamente, calcula la suma de todos los nuevos términos, y añadir otraf(n - 1) (que es ahora a), lo cual es la suma de todos los términos anteriores.

Combinando eso juntos, obtenemos:

  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

Reemplazar acon xy bcon y, y listo, tienes que formular la fórmula anterior.

Python 2 , 58 54 50 bytes

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

Pruébalo en línea!

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

Utiliza la codificación CP-1252. Define la funciónPlusMinus (±) . 1 indexado.

Explicación

±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

Código:

+>bc-*2/640

Explicación:

Para visualizar la relación de f _n , tomemos el ejemplo f ₅ . Para calcular f ₅ , echemos un vistazo a la siguiente suma:

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

La parte en negrita es igual a f ₄ . La parte 7 + 8 + 9 + 10 es el rango [f _n-2 + 1, f _n-1 - 1] . Eso hace que la fórmula f _n-1 + Σ [f _n-2 + 1 ... f _n-1 - 1] ( enlace Wolfram ):

f _n = 0.5 × (f _n-1 ² - f _n-2 ² + f _n-1 - f _n-2 )

Que se puede reescribir a:

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

Cuál es la fórmula que usaremos en el código:

Explicación del código

La 640parte nos da los casos base:

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

El código que se ejecutará (que define 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

Pruébalo en línea!

Julia, 39 33 32 bytes

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

Basado en 0.

Gracias a @Dennis, guardado 6 bytes.

Gracias a @GlenO, guardé un byte.

Pruébalo en línea!

Respuesta anterior 1- basada:

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

Pruébalo en línea!

Respuesta anterior sin golf 1 basada:

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

Pruébalo en línea!

JavaScript (ES6), 47 bytes

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

Utiliza la relación de recurrencia que f(n) = sum(range(f(n-2) + 1, f(n-1) + 1))para n> 2.

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]

Pruébalo en línea!

Explicación

Indexación basada en 0. Solo funciona n = 6(en mi máquina Windows se bloquea con un desbordamiento de pila n = 7).

Usando el mismo método que la respuesta de JungHwan Min (suma del rango menos la suma de los términos anteriores).

Sumar un rango / matriz en PowerShell es largo, por lo que estoy usando un truco para unir una matriz con +para crear una expresión larga (como 1+2+3+4...etc) y luego enviarla a través de iex( Invoke-Expression).

Como necesito hacerlo dos veces, en lugar de usar -joinestoy configurando la variable especial $OFS, que significa separador de campo de salida. Cuando cadenas una matriz, este es el carácter utilizado para unir los elementos; Por defecto es un espacio. Entonces, configurándolo en +(una vez), puedo reemplazar algo como $a-join'+'|iexcon"$a"|iex .

Un forbucle simple continúa hasta que el recuento de secuencia es menor o igual que el entero de entrada, luego devuelvo el $nelemento th.

MATL , 17 16 bytes

OKi:"tP:yX-sv]G)

1basada en la indexación se utiliza. El código es muy ineficiente. Porque n = 6ya supera el límite de memoria del compilador en línea.

Pruébalo en línea!

Cómo funciona

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

Para 20 bytes , la siguiente versión evita la limitación de memoria. Pero todavía existe la limitación del tipo de datos (el doubletipo solo puede garantizar que los enteros se representen con precisión 2^53), por lo que los resultados son válidos n = 8solo.

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

¡Pruébalo en línea también!

Haskell , 42 bytes

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

Pruébalo en línea!

Esto implementa directamente la recurrencia que para n>2, f(n)es igual a f(n-1)más la suma del intervalo abierto de f(n-2)a f(n-1)que de nuevo es igual a la suma del intervalo semiabierto desde f(n-2)a 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)]

Haskell, 31 bytes

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

Ejemplo de uso: ((0:4#6)!!) 6-> 468930. Pruébalo en línea! .

Recurrencia simple, que realiza un seguimiento del elemento máximo mhasta el momento y el siguiente valor 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];}

Pruébalo en línea! Esta solución se basa-1, f(1) => 0.

Perl 6 ,  52 49 44  35 bytes

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

Intentalo

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

Intentalo

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

Intentalo

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

Intentalo

Expandido:

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

Pruébalo en línea!

Implementa el algoritmo como se define y está indexado en 0. La entrada de 6es demasiado para TIO para manejar.

Establece $aser una matriz [0,4]. Bucles desde 1hasta la entrada $n. En el ciclo, tomamos el rango de números desde 0el número más grande que tenemos $a[-1], y usamos una Where-Objectcláusula |?{...}para extraer solo aquellos números que aún no están presentes. Ese conjunto de números se -joinedita junto con +s, y luego se alimenta a iex(abreviatura Invoke-Expressiony similar a eval). Ese valor se concatena en una matriz al final de $a. Finalmente, salimos de nuestro bucle y tomamos el $nnúmero th en nuestra matriz. Ese número se deja en la tubería, y la salida es implícita.

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)

Pruébalo en línea!

Lote, 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%

Puerto de mi respuesta de JavaScript.

cc , 47 bytes

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

Funciona con enteros tan grandes como desee, hasta la capacidad de memoria de la computadora.

Pruébalo en línea!

Indización basada en 0, entrada en stdin, salida en stdout. (También hay salida en stderr, que debe ignorarse).

Ejecuciones de muestra:

$ 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

Utiliza el mismo algoritmo que la siguiente solución en bash, que es (un poco) más legible:

Bash puro, 60 bytes

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

Pero el programa bash solo funciona para entradas de hasta 7, ya que alcanza un desbordamiento de enteros más allá de eso.

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

Sin golf:

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
}

Probablemente haya una manera de convertir esto a una lambda para ahorrar aún más, o algo usando la función .Aggregate. Aunque actualmente no tengo importaciones, ¿tal vez se iguala?

> <> , 43 + 3 = 46 bytes

Utiliza la fórmula presentada en las respuestas de Adnan y Qwerp-Derp .

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

Espera que la entrada esté presente en la pila, por lo que +3 bytes para el -vindicador.

Pruébalo en línea!