Urutan Divinacci

23

Divinacci ( OEIS )

Lakukan urutan Fibonacci tetapi alih-alih menggunakan:

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

Menggunakan:

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

Untuk input n, output istilah ke-n, program Anda seharusnya hanya memiliki 1 input.

14 istilah pertama (0-diindeks, Anda dapat 1-indeks; sebutkan yang Anda gunakan):

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

Anda dapat memilih apakah atau tidak untuk menyertakan terkemuka 0. Bagi mereka yang melakukan: pembagi dari 0yang []untuk tujuan tantangan ini.

Ini kemenangan kode-golf terendah-hitungan byte ...

code-golf sequence number-theory fibonacci division Guci Gurita Ajaib
sumber
15
Semua bilangan asli membagi 0 , dengan demikian jumlah pembagi adalah + ∞ .
Dennis
9
@Dennis akhirnya seseorang yang tidak berpikir bahwa 1 + 2 + 3 + ... = -1/12.
Leaky Nun
1
@ Dennis Kita dapat menyingkirkan 0 dan membuatnya valid meskipun: P. Atau Anda bisa mengirimkan jawaban Mathematica Infinityjika Anda mau.
Magic Gurita Guci
Jawaban Jelly akan lebih pendek. : P Anda dapat mengubah urutan (jawabannya mungkin perlu mengubah juga) atau mengubah deskripsinya (mulai dengan nilai dasar 0, 1, 1 ).
Dennis
1
@carusocomputing Jika tidak mengubah urutan, bagaimana pengaruhnya terhadap jawaban?
Martin Ender

Jawaban:

10

05AB1E , 9 byte

XÎFDŠ‚ÑOO

Cobalah online!

Penjelasan

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
sumber
Bertukar banyak terjadi heh! Menarik.
Magic Gurita Guci
2
Saya suka bagaimana beberapa byte terakhir secara paksa berteriak pada pembaca.
Rohan Jhunjhunwala
1
Anda memenangkan ini dengan 2 menit lol.
Magic Gurita Guci
8

Mathematica, 45 40 byte

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

Fungsi terkait pembagi Mathematica Divisors, DivisorSumdan DivisorSigmasemuanya tidak terdefinisi untuk n = 0 (memang demikian), jadi kita mulai dari f(1) = f(2) = 1dan tidak mendukung input 0.

Mendefinisikannya sebagai operator alih-alih menggunakan fungsi yang tidak disebutkan namanya tampaknya dua byte lebih lama:

±1=±2=1
±n_:=Sum[Tr@Divisors@±(n-i),{i,2}]
Martin Ender
sumber
* 7 byte lebih lama kecuali ±1 byte dalam pengkodean yang didukung Mathematica.
CalculatorFeline
@CalculatorFeline Ini. (Pengaturan default untuk $CharacterEncodingpada mesin Windows adalah WindowsANSI, yaitu CP 1252.)
Martin Ender
1
Senang mendengarnya. .
CalculatorFeline
4

Haskell , 55 byte

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

Cobalah online!

Diindeks satu.

Tidak
sumber
3

MATL, 16 15 byte

Oliq:",yZ\s]+]&

Solusi ini menggunakan pengindeksan berbasis 0.

Cobalah di MATL Online

Penjelasan

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
sumber
3

Jelly , 10 9 byte

ð,ÆDẎSð¡1

Cobalah online!

Terima kasih untuk Dennis untuk -1.

Erik the Outgolfer
sumber
9 byte
Dennis
@ Dennis Ini 0implisit?
Erik the Outgolfer
Ketika Anda mengambil jumlah iterasi dari STDIN, Anda mendapatkan rantai niladik, dan 0 adalah argumen implisit rantai niladik.
Dennis
@ Dennis So ¡dan yang lainnya hanya akan mencoba mengambil argumen dari mana-mana, bahkan dengan sebuah Ɠ? Itu sangat tidak terduga ...
Erik the Outgolfer
Kecuali ditentukan secara eksplisit, ¡et al. ambil argumen baris perintah terakhir dan, jika tidak ada, bacalah baris dari STDIN.
Dennis
3

Python 3 , 88 83 81 byte

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)

Cobalah online!

Tidak termasuk 0

ovs
sumber
2

PHP , 97 byte

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

Cobalah online!

PHP , 101 byte

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

Cobalah online!

Jörg Hülsermann
sumber
1

R, 81 byte

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-diindeks, dan mengecualikan 0 pada awal urutan. Nol itu memberi saya banyak kesulitan untuk diterapkan, karena builtinnumbers::divisors tidak menanganinya dengan baik.

Sisanya adalah versi modifikasi dari fungsi rekursif standar yang mengimplementasikan urutan fibonacci.

> f(1)
[1] 1
> f(2)
[1] 1
> f(3)
[1] 2
> f(5)
[1] 10
> f(13)
[1] 12846
JAD
sumber