Zsumuj pierwsze n parzyste liczby Fibonacciego

19

Wydaje się, że nie ma jeszcze konkursu na ten.

Zadanie jest proste. Dodaj pierwsze nliczby sekwencji Fibonacciego, które są parzyste, i wyślij wynik.

Jest to podane przez OEIS A099919 , z tą różnicą, że sekwencja jest przesunięta o jeden, zaczynając od fib(1) = 0zamiast fib(1) = 1.

To jest kod golfowy. Wygrywa najniższa liczba bajtów.

Przykłady

n sum
1 0
2 2
3 10
4 44
5 188
6 798
7 3382
8 14328
9 60696

Związane z

dfernan
źródło
@EasterlyIrk Przypadki testowe implikują to drugie, ale należy to wyraźnie zaznaczyć.
Mego
@Mego tak, doszedłem do wniosku.
Rɪᴋᴇʀ
9
Proszę nie przyjmować odpowiedzi tak szybko. Minęła tylko godzina, odpowiedź golfisty mogła się pojawić. EDYCJA: Widzę, że jest już krótsza odpowiedź, która nie została jeszcze zaakceptowana.
R
6
Zwyczajowo trzeba czekać co najmniej tydzień, zanim zaakceptuje się odpowiedź, ponieważ wiele osób interpretuje ją jako znak, że wyzwanie nie jest już aktywne.
Zgarb

Odpowiedzi:

8

Oaza , 8 7 5 bajtów

1 bajt zapisany dzięki @ETHProductions i 2 kolejne zapisane dzięki @Adnan!

zc»+U

Wypróbuj online!

Wyjaśnienie:

Używa tej samej formuły powtarzalności, co moja odpowiedź MATL.

Luis Mendo
źródło
1
Info.txt Oasis mówi, że Uw kodzie jest zastąpiony 00, czy to może zaoszczędzić bajt?
ETHproductions
@ETHproductions Dzięki! Zapomniałem o tym
Luis Mendo,
1
Ładny! Można wymienić 4*ze zi 2+ze »:)
Adnan
@Adnan Dziękujemy! Naprawdę powinienem przeczytać dokument :-)
Luis Mendo
17

Python, 33 bajty

c=2+5**.5
lambda n:(7-c)*c**n//20

Wypróbuj online

Magiczna formuła!

xnor
źródło
3
O Boże. Zajęło mi znacznie więcej czasu, niż powinienem sobie uświadomić, dlaczego „komentujesz” to 20 w drugim wierszu: P
Theo
@xnor, jakieś odniesienie do tej magicznej formuły?
TheChetan
@TheChetan: ewentualnie a(n) = (-10 + (5-3*sqrt(5))*(2-sqrt(5))^n + (2+sqrt(5))^n*(5+3*sqrt(5)))/20(Colin Barker, 26 listopada 2016 r.) Ze strony OEIS
Titus
7

Właściwie 6 bajtów

r3*♂FΣ

Wypróbuj online!

Wyjaśnienie:

Co trzecia liczba Fibonacciego (począwszy od F_0 = 0) jest parzysta. Tak więc, pierwsze nnumery parzyste Fibonacciego są F_{i*3}dla iw [0, n).

r3*♂FΣ
r       [0, n)
 3*     multiply each element by 3
   ♂F   retrieve the corresponding element in the Fibonacci sequence
     Σ  sum
Mego
źródło
7

JavaScript (ES6), 27 bajtów

f=x=>x>1&&4*f(x-1)+f(x-2)+2

Rekurencja na ratunek! Wykorzystuje to jedną z formuł na stronie OEIS:

f (n <1) = 0, f (n) = 4 * a (n + 1) + a (n) +2

(ale przesunięty o jeden, ponieważ wyzwanie przesuwa go o jeden)

ETHprodukcje
źródło
6

Pyke, 6 bajtów

3m*.bs

Wypróbuj tutaj!

3m*    -   map(i*3, range(input))
   .b  -  map(nth_fib, ^)
     s - sum(^)
niebieski
źródło
4

Perl 6 ,  38 35  32 bajtów

{[+] grep(*%%2,(1,&[+]...*))[^($_-1)]}

Spróbuj

{[+] grep(*%%2,(0,1,*+*...*))[^$_]}

Spróbuj

{[+] (0,1,*+*...*)[3,6...^$_*3]}

Spróbuj

Rozszerzony:

{  # bare block lambda with implicit parameter 「$_」

  [+]                       # reduce with 「&infix:<+>」

    ( 0, 1, * + * ... * )\  # fibonacci sequence with leading 0

    [ 3, 6 ...^ $_ * 3 ]    # every 3rd value up to
                            # and excluding the value indexed by
                            # the input times 3

}
Brad Gilbert b2gills
źródło
3

Oktawa , 36 35 33 bajtów

@(n)filter(2,'FAD'-69,(1:n)>1)(n)

Wypróbuj online!

Wyjaśnienie

Ta anonimowa funkcja implementuje równanie różnicy a(n) = 4*a(n-1)+a(n-2)+2jako filtr rekurencyjny :

Y = filter(B,A,X)filtruje dane w wektorze Xza pomocą filtra opisanego przez wektory Ai Btworzy filtrowane dane Y. Filtr jest implementacją standardowego równania różnicowego w postaci „transponowanej bezpośrednio w formie II”:

a(1)*y(n) = b(1)*x(n) + b(2)*x(n-1) + ... + b(nb+1)*x(n-nb) - a(2)*y(n-1) - ... - a(na+1)*y(n-na)

W naszym przypadku A = [1 -4 -1], B = 2i wejście xpowinno być wektorem jedności, a wynik pojawi się jako ostatni wpis wyniku y. Jednak ustawiamy 0na pierwszą wartość wejścia, tak aby inicjał 0pojawiał się na wyjściu, zgodnie z wymaganiami.

'FAD'-69jest po prostu krótszym sposobem na wytworzenie wektora współczynnika A = [1 -4 -1]; i (1:n)>1wytwarza wektor wejściowy x = [0 1 1 ... 1].

Luis Mendo
źródło
3

dc , 25 22 bajtów

9k5v1+2/3?*1-^5v/0k2/p

Wypróbuj online!

Lub zapisz program w pliku i uruchom go, wpisując

dc -f *filename*

Program przyjmuje nieujemną liczbę całkowitą n na stdin i wyświetla sumę pierwszych n parzystych liczb Fibonacciego na stdout. (Sekwencja Fibonacciego zaczyna się od 0, zgodnie z przykładami PO).


Ten program używa wzoru (F (3n-1) -1) / 2 do sumy pierwszych n parzystych liczb Fibonacciego, gdzie F jest zwykłą funkcją Fibonacciego, podaną przez F (0) = 0, F (1) = 1, F (n) = F (n-2) + F (n-1) dla n> = 2.


dc jest kalkulatorem stosowym. Oto szczegółowe wyjaśnienie:

9k  # Sets the precision to 9 decimal places (which is more than sufficient).

5v  # Push the square root of 5

1+  # Add 1 to the number at the top of the stack.

2/  # Divide the number at the top of the stack by 2.

W tym momencie liczba (1 + sqrt (5)) / 2 znajduje się na górze stosu.

3   # Push 3 on top of the stack.

?   # Read a number from stdin, and push it.

\*  # Pop two numbers from the stack, multiply them, and push the product

1-  # Subtract 1 from the number at the top of the stack.

W tym momencie 3n-1 znajduje się na górze stosu (gdzie n jest wejściem), a (1 + sqrt (5)) / 2 jest drugi od góry.

^   # Pop two numbers from the stack (x, then y), compute the power y^x, and push that back on the stack.

5v/ # Divide the top of the stack by sqrt(5).

W tym momencie liczba na górze stosu to (((1 + sqrt (5)) / 2) ^ (3n-1)) / sqrt (5). Najbliższa liczba całkowita do tej liczby to F (3n-1). Zauważ, że F (3n-1) jest zawsze liczbą nieparzystą.

0k # Change precision to 0 decimal places.

2/ # Divide the top of the stack by 2, truncating to an integer.

p # Print the top of the stack on stdout.
Mitchell Spector
źródło
3

Mathematica, 27 21 bajtów

Dzięki xnor za wskazanie alternatywnej formuły, alephalpha do korekty początkowego indeksu

Fibonacci[3#-1]/2-.5&
ngenisis
źródło
1
Czy (Fibonacci(3*n+2)-1)/2formuła może być krótsza?
xnor
2

MATL , 15 14 bajtów

OOi:"t4*b+2+]x

Wypróbuj online!

Wyjaśnienie

Wykorzystuje to jedną z formuł rekurencyjnych z OEIS:

a (n) = 4 * a (n-1) + a (n-2) +2

Dla wejścia N kod iteruje N razy, czyli 2 razy więcej niż to konieczne. To jest kompensowane przez ustawienie 0, 0(zamiast 0, 2) jako wartości początkowych, a usuwając ostatnią otrzymaną wartość i wyświetlanie poprzedniego.

OO      % Push two zeros as initial values of a(n-2), a(n-1)
i       % Input N
:"      % Do this N times
  t     %   Duplicate a(n-1)
  4*    %   Multiply by 4
  b+    %   Bubble up a(n-2) and add to 4*a(n-1)
  2+    %   Add 2. Now we have 4*a(n-1)+a(n-2)+2 as a(n), on top of a(n-1)
]       % End
x       % Delete last value, a(n). Implicitly display the remaining value, a(n-1)
Luis Mendo
źródło
2

Partia, 80 bajtów

@set/at=x=0,y=1
@for /l %%i in (2,1,%1)do @set/az=x+y,y=z+x,t+=x=y+z
@echo %t%

Wykorzystuje fakt, że co trzecia liczba Fibonacciego jest parzysta, i po prostu oblicza je trzy na raz (obliczanie więcej niż jednej na raz jest w rzeczywistości łatwiejsze, ponieważ nie trzeba zamieniać wartości). Próbowałem (Fibonacci(3*n+2)-1)/2sformułowania, ale tak naprawdę jest on o kilka bajtów dłuższy ( t+=okazuje się być dość wydajny pod względem rozmiaru kodu).

Neil
źródło
2

C, 82 38 36 bajtów

2 bajty zapisane dzięki @BrainSteel

Formuły na stronie OEIS znacznie skróciły:

a(n){return--n<1?0:4*a(n)+a(n-1)+2;}

Wypróbuj online!

82 bajty:

x,s,p,n,c;f(N){s=0;p=n=1;c=2;while(n<N){if(~c&1)s+=c,n++;x=p+c;p=c;c=x;}return s;}

Pierwsza wersja ma 75 bajtów, ale tej funkcji nie można ponownie użyć, chyba że zawsze wywołujesz numer fwiększy Nniż poprzednie :-)

x,s,p=1,n=1,c=2;f(N){while(n<N){if(~c&1)s+=c,n++;x=p+c;p=c;c=x;}return s;}

Moja pierwsza odpowiedź tutaj. Nie sprawdziłem żadnych innych odpowiedzi ani OEIS. Sądzę, że jest kilka sztuczek, które mogę zastosować, aby skrócić :-)

Szymon
źródło
1
Możesz to zrobić odrobinę krócej, a(n){return--n<1?0:4*a(n)+a(n-1)+2;}
tasując
1

Haskell ( 32 31 bajtów)

Oszczędność jednego bajtu dzięki @ChristianSievers.

Korzystając ze wzoru podanego w OEIS: a(n) = 4*a(n-1)+a(n-2)+2, n>1Gary Detlefs

a n|n>1=4*a(n-1)+a(n-2)+2|n<2=0

Dylan Meeus
źródło
Golfist to sposób na określenie n<=1liczb całkowitych n<2. Ponadto, drugim warunkiem nie musi być negacja pierwszego (idiomatyczny otherwisejest po prostu True), więc zwykle w golfa 1<2stosuje się coś podobnego .
Christian Sievers
@ChristianSievers rzeczywiście n <2 to oczywista poprawa, dziękuję. Drugi działa również, choć w tym przypadku nic mnie nie oszczędza. Wciąż uczę się Haskella i nie zdawałem sobie sprawy, że mogę mieć takiego strażnika. Dziękuję Ci!
Dylan Meeus
1

Mathematica, 32 27 bajtów

Fibonacci[3Input[]-1]/2-1/2

Podziękowania dla Xnor . Zaoszczędź 5 bajtów dzięki JungHwan Min.

devRicher
źródło
Z pewnością Mathematica ma Fibonacciego i krócej jest (Fibonacci(3*n+2) - 1)/2napisać sumi?
xnor
@JungHwanMin To nie jest plagiat; wspomina o stronie OEIS. Ponadto nie jest to kandydat na wiki społeczności. Zobacz Jak korzystać z Wiki społeczności? .
Dennis
@devRichter Przepraszamy za cofnięcie usunięcia posta, ale konieczna była rozmowa. Jeśli chcesz go usunąć, daj mi znać, a ja przeniosę tę rozmowę do pokoju rozmów.
Dennis
@Dennis nadal uważam, że Vincenzo Librandi należy wyraźnie przyznać - (przypadkowo usunąłem mój ostatni komentarz ... czy można go cofnąć?) Jeśli chodzi o sugestie społeczności, jestem poprawiony.
JungHwan Min
Miałem na myśli wspomnienie jego nazwiska w poście ... (a może w komentarzu Mathematica (* Vincenzo Librandi, Mar 15 2014 *), tak jak w OEIS.)
JungHwan Min
1

R, 42 bajty

Rozwiązanie nierekurencyjne, w przeciwieństwie do wcześniejszego rozwiązania @rtrunbull tutaj .

for(i in 1:scan())F=F+gmp::fibnum(3*i-3);F

Wykorzystuje właściwość, że każda trzecia wartość sekwencji Fibonacciego jest parzysta. Nadużywa również Fdomyślnie zdefiniowanego jako FALSE=0, pozwalając jako podstawa do dodania wartości.

JAD
źródło
1

R, 42 41 bajtów

sum(DescTools::Fibonacci(3*(scan():2-1)))

scan(): weź nze standardowego.

scan():2-1: Generuje liczby całkowite od nsię 2, ubytek przez 1uzyskując n-1dzięki 1.

3*(scan():2-1) : pomnóż przez 3, ponieważ co trzecia liczba Fibonacciego jest parzysta.

DescTools::Fibonacci(3*(scan():2-1)): Zwróć te liczby Fibonacciego (tj. 3Przez (n-1)*3).

sum(DescTools::Fibonacci(3*(scan():2-1))) : Zsumuj wynik.

Wcześniej miałem to nieciekawe rozwiązanie, korzystając z jednej z formuł z OEIS:

a=function(n)`if`(n<2,0,4*a(n-1)+a(n-2)+2)
rturnbull
źródło
Udało mi się dopasować liczbę bajtów bez rekurencji :)
JAD
@JarkoDubbeldam Nicea!
Porzuciłem
Fajnie, co dokładnie to desctools::fibonaccirobi numbers::fibonacci? Ponieważ ta mgła będzie nieco krótsza.
JAD
Och, nieważne, znalazłem to. Sweet, inne implementacje, które znalazłem, nie obsługują proszenia o wiele numerów na raz.
JAD
1
@JarkoDubbeldam Tak, `` gmp :: fibnum '' zwraca obiekty typu bigz, które *applyklasa funkcji konwertuje na typ z rawpowodów ...
rturnbull
1

PHP, 73 70 bajtów

for(${0}=1;$i++<$argv[1];$$x=${0}+${1})${$x^=1}&1?$i--:$s+=$$x;echo$s;

prezentowanie zmiennych zmiennych . Na). Uruchom z -nr.

awaria

for(${0}=1;         # init first two fibonaccis (${1}=NULL evaluates to 0 in addition)
                    # the loop will switch between $0 and $1 as target.
    $i++<$argv[1];  # loop until $i reaches input
    $$x=${0}+${1}       # 3. generate next Fibonacci
)
    ${$x^=1}            # 1. toggle index (NULL => 1 => 0 => 1 ...)
    &1?$i--             # 2. if current Fibonacci is odd, undo increment
    :$s+=$$x;           #    else add Fibonacci to sum
echo$s;             # print result

Liczby są doskonale poprawnymi nazwami zmiennych w PHP.
Ale dla literałów wymagają aparatów ortodontycznych; tzn . ${0}nie $0.

36 bajtów, O (1)

<?=(7-$c=2+5**.5)*$c**$argv[1]/20|0;

port odpowiedzi xnora

Tytus
źródło
0

PARI / GP, 21 bajtów

n->fibonacci(3*n-1)\2

\ jest ilorazem liczby całkowitej.

alephalpha
źródło