fundo

Considere uma sequência definida da seguinte maneira:

• O primeiro elemento é 0;
• O segundo elemento é 4;
• A partir do terceiro elemento, seu valor pode ser calculado por:
  • Tomando o conjunto de números inteiros de 0 até o elemento anterior da sequência (inclusivo ou exclusivo, não importa);
  • Remoção de números inteiros que já apareceram anteriormente na sequência do conjunto;
  • Adicionando os demais elementos do conjunto; esse é o valor que você deseja.

Curiosamente, essa sequência ainda não parece estar no OEIS .

A tarefa

Escrever um programa ou função que leva um número inteiro n como entrada, e gera o n ésimo elemento da sequência.

Casos de teste

Os primeiros elementos da sequência são:

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

Esclarecimentos

• Em teoria, seu programa deve ser capaz de lidar com n arbitrário se for executado em uma variante de sua linguagem que possua números inteiros ilimitados e acesso a uma quantidade ilimitada de memória. (É improvável que os idiomas sem bignums possam ir muito além do 468930, mas isso não é desculpa para codificar as respostas.)
• Você pode escolher a indexação com base em 0 ou em 1 para a sequência (por exemplo, depende de você se n = 1 retorna o primeiro elemento, n = 2 o segundo elemento e assim por diante; ou se n = 0 retorna o primeiro elemento , n = 1 o segundo elemento e assim por diante).
• Não há requisitos no algoritmo que você usa, nem em sua eficiência; você pode implementar a definição da sequência diretamente (mesmo que seja realmente ineficiente) e também pode implementar um algoritmo diferente que leva aos mesmos resultados.

Condição de vitória

Isso é código-golfe , e o programa correto mais curto, medido em bytes, vence.

Geléia , 13 12 9 bytes

rSạo4¥ð@¡

Usa indexação baseada em 0.

Experimente online!

Como 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

Obrigado a @Dennis por eliminar 6 bytes!

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

Não é o código mais golfista de todos os tempos, mas usa uma fórmula que eu criei:

Onde xestá do lado direito f(n - 1)e yestá f(n - 2).

Explicação:

A soma dos números inteiros contínuos de aaté b(inclusive) pode ser descrita por esta fórmula:

amount * average

Onde amount(quantidade de números) é descrito da seguinte maneira:

((a - b) - 1)

E average(a média de todos os números) é descrita assim:

(a + b) / 2

Portanto, a fórmula completa é agora:

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

A nossa forma de implementar esta fórmula na fórmula final é substituir apara f(n - 1), bpara f(n - 2), que, basicamente, calcula a soma de todos os novos termos, e adicionar outro f(n - 1)(que é agora a), o que é a soma de todos os termos anteriores.

Combinando isso, obtemos:

  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

Substitua acom xe bcom y, e voilá, você tem que fórmula acima.

Python 2 , 58 54 50 bytes

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

Experimente 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

Usa a codificação CP-1252. Define a função PlusMinus (±). 1 indexado.

Explicação

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

Oásis , 11 bytes

Código:

+>bc-*2/640

Explicação:

Para visualizar a relação de f _n , vamos dar o exemplo f ₅ . Para calcular f ₅ , vamos dar uma olhada na seguinte soma:

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

A parte em negrito é igual a f ₄ . A parte 7 + 8 + 9 + 10 é o intervalo [f _n-2 + 1, f _n-1 - 1] . Isso cria a fórmula f _n-1 + Σ [f _n-2 + 1 ... f _n- 1-1 ] ( link Wolfram ):

f _n = 0,5 × (f _n-1 ² - f _n-2 ² + f _n-1 - f _n-2 )

Que pode ser reescrito para:

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

Qual é a fórmula que usaremos no código:

Explicação do código

A 640parte nos fornece os casos básicos:

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

O código que será executado (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

Experimente online!

Julia, 39 33 32 bytes

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

Baseado em 0.

Graças a @Dennis, economizou 6 bytes.

Graças a @GlenO, salvou um byte.

Experimente online!

Resposta anterior 1- baseada:

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

Experimente online!

Resposta ungolfed anterior, baseada em 1:

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

Experimente online!

JavaScript (ES6), 47 bytes

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

Usa a relação de recorrência 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]

Experimente online!

Explicação

Indexação baseada em 0. Só funciona n = 6(na minha máquina Windows, ele trava com um estouro de pilha n = 7).

Usando o mesmo método da resposta de JungHwan Min (soma do intervalo menos soma dos termos anteriores).

A soma de um intervalo / matriz no PowerShell é longa; portanto, estou usando um truque para associar uma matriz a +para criar uma expressão longa (como 1+2+3+4...etc) e depois enviá-la através iex( Invoke-Expression).

Como eu preciso fazer isso duas vezes, em vez de usar -join, estou configurando a variável especial $OFS, que significa separador de campos de saída. Quando você especifica uma matriz, esse é o caractere usado para juntar os elementos; padrão para um espaço. Assim, definindo-o como +(uma vez), eu posso substituir algo como $a-join'+'|iexcom "$a"|iex.

Um forloop simples continua até que a contagem de sequências seja menor ou igual ao número inteiro de entrada e, em seguida, retorno o $nelemento th.

MATL , 17 16 bytes

OKi:"tP:yX-sv]G)

1indexação baseada em dados é usada. O código é muito ineficiente. Pois n = 6já excede o limite de memória do compilador online.

Experimente online!

Como 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 , a versão a seguir evita a limitação de memória. Mas ainda existe a limitação do tipo de dados (o doubletipo só pode garantir que os números inteiros sejam representados com precisão até 2^53), portanto, os resultados são válidos até n = 8apenas.

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

Experimente online também!

Haskell , 42 bytes

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

Experimente online!

Este implementa diretamente a recorrência que para n>2, f(n)iguala f(n-1)mais a soma do intervalo aberto a partir f(n-2)de f(n-1)que novamente é igual à soma do intervalo semi-aberto a partir f(n-2)de f(n-1)inclusiva.

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

Exemplo de uso: ((0:4#6)!!) 6-> 468930. Experimente online! .

Recursão simples, que monitora o elemento máximo maté o momento e o próximo 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];}

Experimente online! Esta solução é baseada em 1 f(1) => 0.

Perl 6 ,  52 49 44  35 bytes

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

Tente

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

Tente

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

Tente

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

Tente

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]

Experimente online!

Implementa o algoritmo conforme definido e é indexado em 0. Entrada de6 é demais para o TIO manipular.

Define $apara ser uma matriz [0,4]. Loops de 1até entrada $n. No loop, pegamos o intervalo de números do 0maior número que temos $a[-1]e usamos uma Where-Objectcláusula |?{...}para extrair apenas os números que ainda não estão presentes. Essa matriz de números é -joineditada junto com +s e depois é alimentada com iex(abreviação de Invoke-Expressione semelhante a eval). Esse valor é então concatenado por matriz no final de $a. Finalmente, saímos do loop e pegamos o $nnúmero th em nossa matriz. Esse número é deixado no pipeline e a saída está 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)

Experimente online!

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%

Porta da minha resposta JavaScript.

dc , 47 bytes

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

Funciona com números inteiros do tamanho que você deseja, até a capacidade de memória do computador.

Experimente online!

Indexação baseada em 0, entrada em stdin, saída em stdout. (Também há saída no stderr, que deve ser ignorada.)

Amostras de execuções:

$ 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

Isso usa o mesmo algoritmo que a seguinte solução no bash, que é (um pouco) mais legível:

Festa pura, 60 bytes

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

Mas o programa bash funciona apenas para entradas de até 7, pois atinge o número inteiro além disso.

Pitão - 15 bytes

ePu+Gs-UeGGQ,Z4

Conjunto de Teste .

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
}

Provavelmente existe uma maneira de converter isso em um lambda para economizar ainda mais, ou algo usando a função .Aggregate. Embora atualmente não possua importações, talvez isso seja igual?

> <> , 43 + 3 = 46 bytes

Utiliza a fórmula apresentada nas respostas de Adnan e Qwerp-Derp .

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

Espera que a entrada esteja presente na pilha, portanto, +3 bytes para o -vsinalizador.

Experimente online!