tło

Rozważ sekwencję zdefiniowaną w następujący sposób:

• Pierwszy element to 0;
• Drugi element to 4;
• Od trzeciego elementu jego wartość można obliczyć poprzez:
  • Przyjęcie zestawu liczb całkowitych od 0 do poprzedniego elementu sekwencji (włącznie lub wykluczenia, to nie ma znaczenia);
  • Usunięcie ze zbioru wszelkich liczb całkowitych, które pojawiły się wcześniej w sekwencji;
  • Dodanie razem pozostałych elementów zestawu; to jest wartość, którą chcesz.

Co ciekawe, ta sekwencja nie wydaje się jeszcze znajdować w OEIS .

Zadanie

Napisać program lub funkcja, która bierze całkowitą N jako dane wejściowe, i wysyła n ty element sekwencji.

Przypadki testowe

Pierwsze kilka elementów sekwencji to:

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

Wyjaśnienia

• Twój program powinien teoretycznie być w stanie obsłużyć dowolne n, jeśli działa na wariancie twojego języka, który ma nieskończenie duże liczby całkowite i dostęp do nieograniczonej ilości pamięci. (Języki bez bignum raczej nie będą w stanie wyjść znacznie dalej niż 468930, ale to nie jest usprawiedliwienie dla zakodowania odpowiedzi na sztywno).
• Możesz wybrać indeksowanie w oparciu o 0 lub w oparciu o 1 (np. Od Ciebie zależy, czy n = 1 zwróci pierwszy element, n = 2 drugi element itd. Lub czy n = 0 zwróci pierwszy element , n = 1 drugi element itd.).
• Nie ma wymagań dotyczących używanego algorytmu ani jego wydajności; możesz zaimplementować definicję sekwencji bezpośrednio (nawet jeśli jest ona naprawdę nieefektywna), a także możesz zaimplementować inny algorytm, który prowadzi do takich samych wyników.

Warunek zwycięstwa

To jest golf golfowy , więc wygrywa najkrótszy poprawny program, mierzony w bajtach.

Galaretka , 13 12 9 bajtów

rSạo4¥ð@¡

Korzysta z indeksowania opartego na 0.

Wypróbuj online!

Jak to działa

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 bajtów

Dzięki @Dennis za zgolenie 6 bajtów!

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

To nie jest najbardziej golfowy kawałek kodu, ale używa formuły, którą stworzyłem:

Gdzie xjest f(n - 1)i yjest po prawej stronie f(n - 2).

Wyjaśnienie:

Suma liczb całkowitych ciągłych od ado b(włącznie) można opisać następującym wzorem:

amount * average

Gdzie amount(liczba liczb) jest opisana w następujący sposób:

((a - b) - 1)

I average(średnia wszystkich liczb) jest opisana w następujący sposób:

(a + b) / 2

Pełna formuła jest teraz:

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

Sposób, w jaki wdrożyć tę formułę do ostatecznego wzoru ma zastąpić ana f(n - 1), bna f(n - 2), które zasadniczo oblicza sumę wszystkich nowych kategoriach i dodać kolejny f(n - 1)(który jest teraz a) na, która jest sumą wszystkich poprzednich kadencjach.

Łącząc to razem, otrzymujemy:

  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

Wymień asię xi bz y, i hej presto, musisz powyższym wzorem.

Python 2 , 58 54 50 bajtów

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

Wypróbuj online!

Matematyka, 49 48 bajtów

±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

Wykorzystuje kodowanie CP-1252. Definiuje funkcję PlusMinus (±). 1-indeksowany.

Wyjaśnienie

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

Oaza , 11 bajtów

Kod:

+>bc-*2/640

Wyjaśnienie:

Aby zwizualizować relację f _n , weźmy przykład f ₅ . Aby obliczyć f ₅ , spójrzmy na następującą sumę:

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

Pogrubiona część jest taka sama jak f ₄ . Część 7 + 8 + 9 + 10 jest zakresem [f _n-2 + 1, f _n-1 - 1] . To sprawia, że ​​wzór 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 )

Które można przepisać na:

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

Jakiej formuły będziemy używać w kodzie:

Wyjaśnienie kodu

640Część daje nam przypadki Base:

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

Kod, który zostanie wykonany (który definiuje (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

Wypróbuj online!

Julia, 39 33 32 bajty

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

W oparciu o 0.

Dzięki @Dennis zaoszczędzono 6 bajtów.

Dzięki @GlenO zapisano bajt.

Wypróbuj online!

Poprzednia odpowiedź 1- w oparciu:

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

Wypróbuj online!

Poprzednia odpowiedź bez odpowiedzi na podstawie 1:

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

Wypróbuj online!

JavaScript (ES6), 47 bajtów

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

Wykorzystuje relację powtarzalności f(n) = sum(range(f(n-2) + 1, f(n-1) + 1))dla n> 2.

PowerShell , 84 89 88 87 bajtów

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

Wypróbuj online!

Wyjaśnienie

Indeksowanie na podstawie 0. Działa tylko przez n = 6(na moim komputerze z systemem Windows ulega awarii z przepełnieniem stosu n = 7).

Przy użyciu tej samej metody, co odpowiedź JungHwan Min (suma zakresu minus suma poprzednich terminów).

Podsumowanie zakresu / tablicy w PowerShell jest długie, więc używam sztuczki, łącząc tablicę z, +aby utworzyć długie wyrażenie (jak 1+2+3+4...etc), a następnie wysyłając je przez iex(Invoke-Expression ).

Ponieważ muszę to zrobić dwa razy, zamiast używania -joinustawiam specjalną zmienną $OFS, która oznacza separator pola wyjściowego. Kiedy tworzymy tablicę, jest to znak używany do łączenia elementów; domyślnie jest to spacja. Więc przez ustawienie go +(raz), mogę wymienić coś podobnego $a-join'+'|iexz"$a"|iex .

Prosta forpętla trwa, dopóki liczba sekwencji nie jest mniejsza lub równa wejściowej liczbie całkowitej, a następnie zwracam $nelement th.

MATL , 17 16 bajtów

OKi:"tP:yX-sv]G)

1stosuje się indeksowanie na podstawie. Kod jest bardzo nieefektywny. Ponieważ n = 6już przekracza limit pamięci kompilatora online.

Wypróbuj online!

Jak to działa

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

W przypadku 20 bajtów następująca wersja pozwala uniknąć ograniczenia pamięci. Ale nadal istnieje ograniczenie typu danych ( doubletyp może jedynie zagwarantować, że liczby całkowite są dokładnie reprezentowane do 2^53), więc wyniki są ważne n = 8tylko do .

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

Wypróbuj też online !

Haskell , 42 bajty

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

Wypróbuj online!

To bezpośrednio realizuje nawrotom że n>2, f(n)równa f(n-1)plus suma otwartym przedziale od f(n-2)celu f(n-1), który ponownie jest równa sumie przedziału półotwartej od f(n-2)do f(n-1)włącznie.

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 bajtów

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

Przykład użycia: ((0:4#6)!!) 6-> 468930. Wypróbuj online! .

Prosta rekurencja, która śledzi maksymalny do mtej pory element i następną wartość s.

JavaScript, 123 119 bajtów

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

Wypróbuj online! Rozwiązanie to jest 1 na bazie f(1) => 0.

Perl 6 ,  52 49 44  35 bajtów

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

Spróbuj

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

Spróbuj

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

Spróbuj

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

Spróbuj

Rozszerzony:

{ # 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 bajtów

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

Wypróbuj online!

Implementuje zdefiniowany algorytm i ma indeks 0. Wejście z6 jest zbyt duże, aby poradzić sobie z TIO.

Ustawia $asię na tablicę [0,4]. Pętle od 1do wejścia $n. W pętli bierzemy zakres liczb od 0największej, jaką mamy $a[-1], i używamy Where-Objectklauzuli, |?{...}aby wyciągnąć tylko te liczby, które nie są jeszcze obecne. Ta tablica liczb jest -joinedytowana razem z +s, a następnie podawana do iex(skrót od Invoke-Expressioni podobny do eval). Ta wartość jest następnie konkatenowana z tablicą na końcu $a. Na koniec wychodzimy z pętli i bierzemy $nliczbę th z naszej tablicy. Liczba ta pozostanie w potoku, a dane wyjściowe są niejawne.

Python 2 , 85 bajtów

def g(n):
 if n<2:return n*4
 s=set(map(g,range(n)));return sum(set(range(max(s)))-s)

Wypróbuj online!

Partia, 108 bajtów

@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 mojej odpowiedzi JavaScript.

dc , 47 bajtów

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

Działa z liczbami całkowitymi tak dużymi, jak chcesz, aż do pojemności pamięci komputera.

Wypróbuj online!

Indeksowanie na podstawie 0, wejście na stdin, wyjście na stdout. (Jest także wyjście na stderr, które należy zignorować.)

Przykładowe przebiegi:

$ 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

Używa tego samego algorytmu jak poniższe rozwiązanie w bash, które jest (trochę) bardziej czytelne:

Pure Bash, 60 bajtów

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

Ale program bash działa tylko dla wejść do 7, ponieważ przekracza przepełnienie liczb całkowitych.

Pyth - 15 bajtów

ePu+Gs-UeGGQ,Z4

Pakiet testowy .

C # - 74 bajty

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

Nie golfowany:

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
}

Prawdopodobnie istnieje sposób, aby przekonwertować to na lambda, aby zaoszczędzić jeszcze więcej, lub coś przy użyciu funkcji .Aggregate. Chociaż obecnie nie mam importu, to może wyrównuje się?

> <> , 43 + 3 = 46 bajtów

Wykorzystuje wzór przedstawiony w odpowiedziach Adnana i Qwerp-Derpa .

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

Oczekuje, że dane wejściowe będą obecne na stosie, więc +3 bajty dla -vflagi.

Wypróbuj online!