Suma moich dzielników Fibonaccified!

14

Słynna sekwencja Fibonacciego F(0) = 0; F(1) = 1; F(N+1) = F(N) + F(N-1)(dla tego wyzwania zaczynamy od 0).

Twoje wyzwanie: Biorąc pod uwagę, n , wyjście suma wszystkich d XX liczb Fibonacciego dla wszystkich dzielników d z n -tego numeru Fibonacciego. Jeśli wolisz bardziej formalną notację,

The Sum

Dane wejściowe : dodatnia liczba całkowita n

Wynik : suma

Rozważmy na przykład n=4. F(4) = 3Dzielnikami 3 są 1 i 3, więc wynik powinien być F(1) + F(3) = 1 + 2 = 3.

W przypadku n=6, F(6) = 8oraz dzielniki do 8: 1, 2, 4, 8, więc wyjście F(1) + F(2) + F(4) + F(8) = 1 + 1 + 3 + 21 = 26.

Przypadki testowe:

1 => 1
2 => 1
3 => 2
4 => 3
5 => 6
6 => 26

To jest , wygrywa najkrótsza odpowiedź w bajtach. Obowiązują standardowe luki .

Neil A.
źródło

Odpowiedzi:

2

Właściwie 5 bajtów

F÷♂FΣ

Wypróbuj online!

Jak to działa

       (implicit) Read n from STDIN.
F      Compute F(n).
 ÷     Get F(n)'s divisors.
  ♂F   Map F over the divisors.
    Σ  Take the sum.
Dennis
źródło
Nazwa języka sprawia, że ​​wydaje się pasywnie agresywny, czy to jest zamierzone?
Rohan Jhunjhunwala
1
Wątpię. Pierwsza wersja języka została nazwana Poważnie z powodu tego komentarza . W drugiej wersji autor postanowił nadal używać przymiotników.
Dennis
6

Galaretka , 7 bajtów

ÆḞÆDÆḞS

Wypróbuj online!

Wyjaśnienie:

ÆḞÆDÆḞS Main link (Arguments: z)
ÆḞ      zth Fibonacci number's
  ÆD                           divisors'
    ÆḞ                                   Fibonacci numbers'
      S                                                     sum
Erik the Outgolfer
źródło
Absolutnie oburzające! Nie znam żadnego z tych egzotycznych języków, ale wydaje mi się nadprzyrodzone, jak można napisać cały algorytm za pomocą kilku znaków.
Bogdan Alexandru
@BogdanAlexandru Widać, że większość używanych tutaj wbudowanych zużywa 2 bajty, ponieważ nie mieszczą się w 1 bajcie. Zobacz odpowiedź Dennisa na jeszcze mniej znaków. Ponadto Jelly jest „językiem golfa”, językiem stworzonym specjalnie dla golfa kodowego , i jest jednym z najbardziej wydajnych tutaj (chociaż nie ma jednego „najbardziej wydajnego” języka).
Erik the Outgolfer
Czy mówisz, że te języki nie są używane w praktyce i są przeznaczone tylko do wyzwań?
Bogdan Alexandru
4

Mathematica, 29 bajtów

f=Fibonacci;f@#~DivisorSum~f&
Martin Ender
źródło
4

Mathematica uproszczona , 14 bajtów

Fi@#~Div9`~Fi&

No cóż, ostatecznie okazało się to identyczne z rozwiązaniem @ MartinEnder ...

JungHwan Min
źródło
Cóż ... Używając krótszej wersji tego samego języka ... Myślę, że to działa.
Neil A.,
W Mathematica nie ma nazw funkcji jednoliterowych, prawda? Czy nie możesz dopasować wszystkich dwóch ciągów znaków utworzonych z wiodącej wielkiej litery i jednego bajtu? Jeśli tak, masz 26 * 256 = 6656 uproszczonych 2-bajtowych nazw funkcji, wystarczy na 6356 11.1.1 nazw z 300 do zaoszczędzenia.
Jonathan Allan
@JathanathanAllan Dobry pomysł. (ale są funkcje jednej nazwy, jak N)
JungHwan Min
2

05AB1E , 11 bajtów

!ÅFDI<èÑ<èO

Wypróbuj online!

Wyjaśnienie

!            # factorial of input
 ÅF          # get the list of fibonacci numbers (starting at 1)
             # smaller than or equal to this
   D         # duplicate list of fibonacci number
    I<è      # get the element at index (input-1)
       Ñ     # get the list of its divisors
        <    # decrement each
         è   # get the fibonacci numbers at those indices
          O  # sum
Emigna
źródło
2

Haskell, 54 bajty

f=0:scanl(+)1f
g x=sum[f!!d|d<-[1..f!!x],mod(f!!x)d<1]

Przykład użycia: g 6-> 26. Wypróbuj online!

nimi
źródło
2

Alice , 38 36 bajtów

Dzięki Leo za oszczędność 2 bajtów.

/ow;B1dt&w;31J
\i@/01dt,t&w.2,+k;d&+

Wypróbuj online!

Niemal na pewno nie optymalne. Przepływ sterowania jest dość skomplikowany i chociaż jestem całkiem zadowolony z liczby bajtów, które zapisały się w porównaniu z poprzednimi wersjami, mam wrażenie, że nadmiernie komplikuję rzeczy, które mogą być prostszym i krótszym rozwiązaniem.

Wyjaśnienie

Najpierw muszę trochę rozwinąć stos adresów zwrotnych Alice (RAS). Podobnie jak wiele innych fungeoidów, Alice ma polecenie skakania w kodzie. Ma jednak także polecenia powrotu do miejsca, z którego przybyłeś, co pozwala dość wygodnie implementować podprogramy. Oczywiście, ponieważ jest to język 2D, podprogramy naprawdę istnieją tylko zgodnie z konwencją. Nic nie stoi na przeszkodzie, abyś wszedł do podprogramu lub go opuścił w inny sposób niż polecenie powrotu (lub w dowolnym punkcie podprogramu), a w zależności od sposobu korzystania z RAS może nie istnieć czysta hierarchia skoku / powrotu.

Zasadniczo jest to realizowane za pomocą polecenia skoku, który jprzesuwa bieżący adres IP do RAS przed skokiem. Polecenie return kwyświetla adres RAS i tam skacze. Jeśli RAS jest pusty, knic nie robi.

Istnieją również inne sposoby manipulacji RAS. Dwa z nich są istotne dla tego programu:

  • wwypycha bieżący adres IP do RAS, nie skacząc gdziekolwiek Jeśli powtórzysz to polecenie, możesz dość łatwo napisać proste pętle &w...k, co zrobiłem już w poprzednich odpowiedziach.
  • Jjest jak, jale nie pamięta bieżącego adresu IP w RAS.

Należy również zauważyć, że RAS nie przechowuje żadnych informacji o kierunku IP. Zatem powrót do adresu z kzawsze zachowuje bieżący kierunek IP (a zatem także to, czy jesteśmy w trybie kardynalnym, czy zwykłym), niezależnie od tego, w jaki sposób przeszliśmy przez ten adres IP jlub wktóry go przepchnął.

W ten sposób zacznijmy od podprogramu w powyższym programie:

01dt,t&w.2,+k

Ta procedura podciąga dolny element stosu, n , do góry, a następnie oblicza liczby Fibonacciego F (n) i F (n + 1) (pozostawiając je na górze stosu). Nigdy nie potrzebujemy F (n + 1) , ale zostanie on odrzucony poza podprogramem, ze względu na to, w jaki sposób &w...kpętle oddziałują z RAS (który rodzaj wymaga, aby te pętle znajdowały się na końcu podprogramu). Powodem, dla którego bierzemy elementy od dołu zamiast od góry, jest to, że możemy traktować stos bardziej jak kolejkę, co oznacza, że ​​możemy obliczyć wszystkie liczby Fibonacciego za jednym razem, bez konieczności przechowywania ich gdzie indziej.

Oto jak działa ten podprogram:

                                                          Stack
01    Push 0 and 1, to initialise Fibonacci sequence.     [n ... 0 1]
dt,   Pull bottom element n to top.                       [... 0 1 n]
t&w   Run this loop n times...                            [... F(i-2) F(i-1)]

  .     Duplicate F(i-1).                                 [... F(i-2) F(i-1) F(i-1)]
  2,    Pull up F(i-2).                                   [... F(i-1) F(i-1) F(i-2)]
  +     Add them together to get F(i).                    [... F(i-1) F(i)]

k     End of loop.

Koniec pętli jest nieco trudny. Dopóki na stosie znajduje się kopia adresu „w”, rozpoczyna się kolejna iteracja. Po ich wyczerpaniu wynik zależy od sposobu wywołania podprogramu. Jeśli podprogram został wywołany z „j”, to ostatnie „k” powraca tam, więc koniec pętli podwaja się jako powrót podprogramu. Jeśli podprogram został wywołany z „J”, a na stosie nadal znajduje się adres z wcześniejszego stosu, przeskakujemy tam. Oznacza to, że jeśli podprogram został wywołany w samej zewnętrznej pętli, to „k” powraca na początek tej zewnętrznej pętli. Jeśli podprogram został wywołany z „J”, ale RAS jest teraz pusty, wówczas to „k” nic nie robi, a IP po prostu porusza się po pętli. Wszystkie trzy przypadki wykorzystamy w programie.

Wreszcie do samego programu.

/o....
\i@...

To tylko dwie szybkie wycieczki do trybu porządkowego, aby odczytać i wydrukować liczby całkowite dziesiętne.

Po tym ijest taki, wktóry pamięta aktualną pozycję przed przejściem do podprogramu, z powodu drugiego /. To pierwsze wywołanie podprogramu oblicza F(n)i F(n+1)na wejściu n. Potem wskakujemy tutaj, ale teraz przemieszczamy się na wschód, więc pozostali operatorzy programu pracują w trybie kardynalnym. Główny program wygląda następująco:

;B1dt&w;31J;d&+
        ^^^

Oto 31Jkolejne wywołanie podprogramu i dlatego oblicza liczbę Fibonacciego.

                                              Stack
                                              [F(n) F(n+1)]
;     Discard F(n+1).                         [F(n)]
B     Push all divisors of F(n).              [d_1 d_2 ... d_p]
1     Push 1. This value is arbitrary.        [d_1 d_2 ... d_p 1]
      The reason we need it is due to
      the fact that we don't want to run
      any code after our nested loops, so
      the upcoming outer loop over all
      divisors will *start* with ';' to
      discard F(d+1). But on the first
      iteration we haven't called the
      subroutine yet, so we need some 
      dummy value we can discard.
dt&w  Run this loop once for each element     [d_1 d_2 ... d_p 1]
      in the stack. Note that this is once    OR
      more than we have divisors. But since   [d_i d_(i+1) ... F(d_(i-1)) F(d_(i-1)+1)] 
      we're treating the stack as a queue,
      the last iteration will process the 
      first divisor for a second time. 
      Luckily, the first divisor is always 
      1 and F(1) = 1, so it doesn't matter 
      how often we process this one.

  ;     Discard the dummy value on the        [d_1 d_2 ... d_p]
        first iteration and F(d+1) of         OR
        the previous divisor on subsequent    [d_i d_(i+1) ... F(d_(i-1))]
        iterations.
  31J   Call the subroutine without pushing   [d_(i+1) ... F(d_i) F(d_i+1)]
        the current address on the RAS.
        Thereby, this doubles as our outer
        loop end. As long as there's an
        address left from the 'w', the end
        of the subroutine will jump there
        and start another iteration for the
        next divisor. Once that's done, the
        'k' at the end of the subroutine will
        simply do nothing and we'll continue
        after it.

;     Discard the final F(d_i+1).
d&+   Get the stack depth D and add the top   [final result]
      D+2 values. Of course that's two more
      than we have divisors, but the stack is
      implicitly padded with zeros, so that
      doesn't matter.
Martin Ender
źródło
1

Aksjomat, 68 bajtów

g==>fibonacci;f(x:NNI):NNI==(x<3=>1;reduce(+,map(g,divisors(g(x)))))

jakiś test

(46) -> [[i,f(i)] for i in [0,1,2,3,4,5,6,10,15] ]
   (46)
   [[0,1], [1,1], [2,1], [3,2], [4,3], [5,6], [6,26], [10,139583862540],
     [15,
      135823697912782666169062844948067355657769395021071830756126284114988028_
       12823029319917411196081011510136735503204397274473084444
     ]
   ]
                                       Type: List List NonNegativeInteger
RosLuP
źródło
1

Python 2 , 89 84 bajtów

-5 bajtów dzięki ovs

lambda n:sum(f(i)for i in range(1,f(n)+1)if f(n)%i<1)
f=lambda x:x<3or f(x-1)+f(x-2)

Wypróbuj online!

Pręt
źródło
1

R, 77 bajtów

F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)

Korzysta z biblioteki „gmp”. Ma to wbudowaną funkcję Fibonacciego i zapewnia możliwość wykonywania dużych liczb. Spowodowało to kilka problemów z sekwencjami i aplikacjami, choć wciąż jest mniejszy niż tworzenie własnej funkcji Fibonacciego.

Wyjaśnienie

F=gmp::fibnum;               # Set F as fibnum function
N=F(scan());                 # get input and set N to the fibonacci number of that index
i=n=N-N;                     # set i and n to 0 with data type bigz
while(i<N)                   # loop while i < N
   if(N%%(i=i+1)<1)          # if incremented i is divisor of N 
       n=n+F(i);             # add F(i) to rolling sum
print(n)                     # output final result

Test

> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 6
2: 
Read 1 item
Big Integer ('bigz') :
[1] 26
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 10
2: 
Read 1 item
Big Integer ('bigz') :
[1] 139583862540
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 15
2: 
Read 1 item
Big Integer ('bigz') :
[1] 13582369791278266616906284494806735565776939502107183075612628411498802812823029319917411196081011510136735503204397274473084444

Bez użycia gmp

81 bajtów , funkcja rekurencyjna, która jest beznadziejnie wolna po wybraniu dużych (9+) liczb

F=function(n)`if`(n<2,n,F(n-1)+F(n-2));sum(sapply(which((N=F(scan()))%%1:N<1),F))

88 bajtów , formuła Bineta, która będzie działać dobrze z większymi liczbami, ale nadal dość szybko osiąga limit liczb całkowitych

F=function(n)round(((5+5^.5)/10)*((1+5^.5)/2)^(n-1));sum(F(which(F(N<-scan())%%1:N<1)))
MickyT
źródło
0

Perl 6 , 49 bajtów

{my \f=0,1,*+*...*;sum f[grep f[$_]%%*,1..f[$_]]}
Sean
źródło
0

CJam , 26 bajtów

qi_[XY@{_2$+}*]_@\f%:!.*:+

Wypróbuj online!

Jestem pewien, że można to zrobić lepiej. Wyjaśnienie:

Chodzi o to, aby mieć tablicę liczb Fibonacciego i dodać iloczyn iloczynu za pomocą tablicy z 1s i 0s, jeśli ta liczba jest lub nie jest dzielnikiem wejścia.

qi                                 Read the input (n)
   [XY        ]                    Array starting with [1,2,...]
  _   @{_2$+}*                     Append n times the sum of the previous two
               _                   Duplicate the array
                @\f%               Modulo each item with n (0 if divisor, a number otherwise)
                    :!             Logical NOT everything (1 if divisor, 0 otherwise) 
                      .*:+         Dot product those two arrays
FrodCube
źródło
0

JavaScript (ES6), 76 65 bajtów

f=(n,i=k=(F=n=>n>1?F(n-1)+F(n-2):n)(n))=>i&&(k%i?0:F(i))+f(n,i-1)

Przypadki testowe

Arnauld
źródło
0

JavaScript (ES6), 105 104 103 101 97 bajtów

i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s

Spróbuj

f=
i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s
o.innerText=f(j.value=4)
oninput=_=>o.innerText=f(+j.value)
<input id=j type=number><pre id=o>

Kudłaty
źródło
Myślę , że możesz zmienić (z=g(i)/y)>~~zna (z=g(i)/y)%1, jeśli tylko sprawdzasz, że zjest to liczba całkowita.
ETHprodukcje
@ETHproductions, który tworzy przepełnienie, które można rozwiązać, zmieniając g(z)na, g(z|0)ale przywracając nas do tej samej liczby bajtów.
Kudłaty
0

Q, 75 bajtów

{f:{$[x<2;x;.z.s[x-1]+.z.s[x-2]]};sum f each m where(~)b mod m:1+til b:f x}
Daniel Plainview
źródło
0

C (gcc) , 93 90 80 bajtów

F(n){n=n<2?n:F(n-1)+F(n-2);}i,s;f(n){for(s=0,i=F(n);i;i--)s+=F(n)%i?0:F(i);n=s;}

Wypróbuj online!

cleblanc
źródło
0

Dodaj ++ , 89 bajtów

D,f,@@@@*,V$2D+G1+dAppp=0$Qp{f}p
D,r,@,¿1=,1,bM¿
D,g,@,¿1_,1_001${f},1¿{r}
D,d,@,{g}dF€gs

Wypróbuj online!

Cairney Coheringaahing
źródło