Sekwencja Divinacciego

23

Divinacci ( OEIS )

Wykonaj sekwencję Fibonacciego, ale zamiast używać:

f(n) = f(n-1)+f(n-2)

Posługiwać się:

f(n) = sum(divisors(f(n-1))) + sum(divisors(f(n-2)))

Dla wejścia n, wyślij n-ty termin, twój program powinien mieć tylko 1 wejście.

Pierwsze 14 haseł (indeksowane 0, możesz indeksować 1; stan, którego użyłeś):

0  | 0     # Initial               | []
1  | 1     # Initial               | [1] => 1
2  | 1     # [] + [1]              | [1] => 1
3  | 2     # [1] + [1]             | [1,2] => 3
4  | 4     # [1] + [1,2]           | [1,2,4] => 7
5  | 10    # [1,2] + [1,2,4]       | [1,2,5,10] => 18
6  | 25    # [1,2,4] + [1,2,5,10]  | [1,5,25] => 31
7  | 49    # [1,2,5,10] + [1,5,25] | [1,7,49] => 57
8  | 88    # [1,5,25] + [1,7,49]   | [1, 2, 4, 8, 11, 22, 44, 88] => 180
9  | 237   # [1,7,49] + [180]      | [1, 3, 79, 237] => 320
10 | 500   # [180] + [320]         | [1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500] => 1092
11 | 1412  # [320] + [1092]        | [1, 2, 4, 353, 706, 1412] => 2478
12 | 3570  # [1092] + [2478]       | [1, 2, 3, 5, 6, 7, 10, 14, 15, 17, 21, 30, 34, 35, 42, 51, 70, 85, 102, 105, 119, 170, 210, 238, 255, 357, 510, 595, 714, 1190, 1785, 3570] => 10368
13 | 12846 # [2478] + [10368]      | [1, 2, 3, 6, 2141, 4282, 6423, 12846] => 25704
Etc...

Możesz wybrać, czy dołączyć wiodące 0. Dla tych, którzy to robią: dzielniki 0są []dla celów tego wyzwania.

Jest to gra w golfa o najniższym numerze bajtów wygrywa ...

code-golf sequence number-theory fibonacci division Urna Magicznej Ośmiornicy
źródło
15
Wszystkie liczby naturalne dzielą 0 , więc jego suma dzielnika wynosi + ∞ .
Dennis
9
@Dennis w końcu ktoś, kto nie uważa, że ​​1 + 2 + 3 + ... = -1/12.
Leaky Nun
1
@Dennis Możemy pozbyć się 0 i sprawić, że będzie to ważne: P. Lub możesz po prostu przesłać odpowiedź Mathematica, Infinityjeśli chcesz.
Urna Magicznej Ośmiornicy
Odpowiedź galaretki byłaby krótsza. : P Możesz albo zmienić sekwencję (odpowiedź prawdopodobnie również wymagałaby ulepszenia), albo zmienić jej opis (zacznij od wartości podstawowych 0, 1, 1 ).
Dennis
1
@carusocomputing Jeśli nie zmienia sekwencji, jak może wpływać na odpowiedzi?
Martin Ender

Odpowiedzi:

10

05AB1E , 9 bajtów

XÎFDŠ‚ÑOO

Wypróbuj online!

Wyjaśnienie

XÎ          # initialize stack with 1,0,input
  F         # input times do
   D        # duplicate
    Š       # move down 2 places on the stack
     ‚      # pair the top 2 elements on the stack
      Ñ     # compute divisors of each
       OO   # sum twice
Emigna
źródło
Mnóstwo zamiany heh! Ciekawy.
Magic Octopus Urn
2
Podoba mi się, jak ostatnie kilka bajtów głośno krzyczy na czytelnika.
Rohan Jhunjhunwala
1
Wygrałeś to o 2 minuty lol.
Magic Octopus Urn
8

Matematyka, 45 40 bajtów

If[#<3,1,Tr@Divisors@#0[#-i]~Sum~{i,2}]&

Funkcje związane dzielnik Mathematica jest Divisors, DivisorSumi DivisorSigmawszystkie są niezdefiniowane n = 0 (słusznie), więc zaczniemy od f(1) = f(2) = 1i nie obsługują wejście 0.

Zdefiniowanie go jako operatora zamiast używania funkcji bez nazwy wydaje się dłuższe o dwa bajty:

±1=±2=1
±n_:=Sum[Tr@Divisors@±(n-i),{i,2}]
Martin Ender
źródło
* 7 bajtów dłużej, chyba że ±1 to bajt w kodowaniu obsługiwanym przez Mathematica.
CalculatorFeline
@CalculatorFeline It Is. (Domyślne ustawienie dla $CharacterEncodingkomputerów z systemem Windows to WindowsANSI, tj. CP 1252.)
Martin Ender
1
Dobrze wiedzieć. .
CalculatorFeline
4

Haskell , 55 bajtów

f n=sum[a|n>1,k<-f<$>[n-1,n-2],a<-[1..k],mod k a<1]+0^n

Wypróbuj online!

Jeden indeksowany.

xnor
źródło
3

MATL, 16 15 bajtów

Oliq:",yZ\s]+]&

To rozwiązanie wykorzystuje indeksowanie oparte na 0.

Wypróbuj w MATL Online

Wyjaśnienie

O        % Push the number literal 0 to the stack
l        % Push the number literal 1 to the stack
i        % Explicitly grab the input (n)
q        % Subtract 1
:        % Create the array [1...(n - 1)]
"        % For each element in this array...
  ,      % Do the following twice
    y    % Copy the stack element that is 1-deep
    Z\   % Compute the divisors
    s    % Sum the divisors
  ]      % End of do-twice loop
  +      % Add these two numbers together
]        % End of for loop
&        % Display the top stack element
Suever
źródło
3

Galaretka , 10 9 bajtów

ð,ÆDẎSð¡1

Wypróbuj online!

Dzięki Dennis za -1.

Erik the Outgolfer
źródło
9 bajtów
Dennis
@Dennis To 0było ukryte?
Erik the Outgolfer
Gdy weźmiesz liczbę iteracji ze STDIN, otrzymasz łańcuch niladyczny, a 0 jest domyślnym argumentem łańcuchów niladycznych.
Dennis
@Dennis Więc ¡i inni będą po prostu starali się spierać zewsząd, nawet z Ɠ? To dość nieoczekiwane ...
Erik the Outgolfer,
O ile nie podano wyraźnie, ¡i in. weź ostatni argument wiersza poleceń i, jeśli nie ma, odczytuje wiersz ze STDIN.
Dennis
3

Python 3 , 88 83 81 bajtów

f=lambda n:+(n<3)or g(f(n-1))+g(f(n-2))
g=lambda n,i=1:n>=i and(n%i<1)*i+g(n,i+1)

Wypróbuj online!

Nie obejmuje 0

ovs
źródło
2

PHP , 97 bajtów

for($f=[0,$y=1];++$i<$argn;$x=$y,$y=$r)for($f[]=$r=$v=$n=$x+$y;--$v;)$n%$v?:$r+=$v;echo$f[$argn];

Wypróbuj online!

PHP , 101 bajtów

for($f=$d=[0,1];$i<$argn;$d[]=$r)for($f[]=$r=$v=$n=$d[$i]+$d[++$i];--$v;)$n%$v?:$r+=$v;echo$f[$argn];

Wypróbuj online!

Jörg Hülsermann
źródło
1

R, 81 bajtów

f=function(n,a=1,b=1,d=numbers::divisors)`if`(n-1,f(n-1,b,sum(d(a))+sum(d(b))),a)

1 indeksowany i wyklucza 0 na początku sekwencji. To zero sprawiło mi wiele problemów do wdrożenia, ponieważ wbudowanenumbers::divisors nie radzi sobie z tym dobrze.

Reszta to zmodyfikowana wersja standardowej funkcji rekurencyjnej, która implementuje sekwencję Fibonacciego.

> f(1)
[1] 1
> f(2)
[1] 1
> f(3)
[1] 2
> f(5)
[1] 10
> f(13)
[1] 12846
JAD
źródło