Sabar, Padovan muda

44

Semua orang tahu urutan Fibonacci:
Anda mengambil kotak, lampirkan kotak sama dengan itu, lalu berulang kali melampirkan kotak yang panjang sisinya sama dengan panjang sisi terbesar dari persegi panjang yang dihasilkan.
Hasilnya adalah spiral kotak yang indah yang urutan bilangannya adalah deret Fibonacci :

Tetapi, bagaimana jika kita tidak ingin menggunakan kotak?

Jika kita menggunakan segitiga sama sisi — alih-alih kuadrat — dengan cara yang serupa, kita mendapatkan spiral segitiga yang sama indahnya dan urutan baru: urutan Padovan , alias A000931 :

Tugas:

Diberikan bilangan bulat positif, , output , istilah N dalam urutan Padovan ATAU persyaratan N pertama .NaNNN

Asumsikan bahwa tiga syarat pertama dari urutan semuanya adalah . Dengan demikian, urutannya akan dimulai sebagai berikut: 1

1,1,1,2,2,3,...

Memasukkan:

  • Setiap bilangan bulat positifN0

  • Input yang tidak valid tidak harus diperhitungkan

Keluaran:

  • Istilah dalam urutan Padovan ATAU istilah pertama dari urutan Padovan.NNN

  • Jika istilah pertama dicetak, hasilnya bisa apa saja yang nyaman (list / array, string multi-line, dll.)N

  • Dapat berupa -indeks atau -indeks01

Test Cases:
(0-diindeks, term )N

Input | Output
--------------
0     | 1
1     | 1
2     | 1
4     | 2
6     | 4
14    | 37
20    | 200
33    | 7739

(1-diindeks, istilah pertama )N

Input | Output
--------------
1     | 1
3     | 1,1,1
4     | 1,1,1,2
7     | 1,1,1,2,2,3,4
10    | 1,1,1,2,2,3,4,5,7,9
12    | 1,1,1,2,2,3,4,5,7,9,12,16

Aturan:

Tau
sumber
2
14(0-diindeks) ditampilkan sebagai keluaran 28sementara saya percaya itu akan menghasilkan37
Jonathan Allan
@ Jonathan. Allan ya, Anda benar. Saya memperbaiki dua test case terakhir untuk term tetapi bukan yang itu. Pos telah diedit. N
Tau
@LuisMendo, saya yakin begitu. Saya akan mengedit posting.
Tau
1
@sharur definisi ini untuk deret Fibonacci adalah definisi visual . Setiap bujur sangkar yang ditambahkan memiliki panjang istilah itu dalam urutan. Urutan yang Anda gambarkan adalah alasan numerik di belakangnya. Kedua urutan bekerja sama baiknya dengan yang lainnya.
Tau
1
Perhatikan bahwa urutan OEIS yang Anda tautkan sedikit berbeda, karena digunakan a_0=1, a_1=0, a_2=0. Akhirnya sedikit berubah karena itua_5=a_6=a_7=1
Carmeister

Jawaban:

59

Jelly , 10 byte

9s3’Ẓæ*³FṀ

Cobalah online!

1-diindeks. Menghitung elemen terbesar dari: mana matriks biner dengan mudah dihitung sebagai:

[001101010]n
[isprime(0)isprime(1)isprime(2)isprime(3)isprime(4)isprime(5)isprime(6)isprime(7)isprime(8)]

(Ini adalah kebetulan total.)

9s3         [[1,2,3],[4,5,6],[7,8,9]]    9 split 3
   ’        [[0,1,2],[3,4,5],[6,7,8]]    decrease
    Ẓ       [[0,0,1],[1,0,1],[0,1,0]]    isprime
     æ*³    [[0,0,1],[1,0,1],[0,1,0]]^n  matrix power by input
        FṀ                               flatten, maximum
Lynn
sumber
33
ini jelas semacam voodoo
Pureferret
7
Ini harus dipublikasikan.
YSC
6
@YSC Sudah diterbitkan di A000931 . Saya tidak akan pernah menebak trik primes :)
flawr
1
... buat itu "kecuali seseorang bisa bermain golf dua byte dari yang satu ini" :) (sekarang saya punya 9 byter )
Jonathan Allan
1
Saya sangat terbiasa melihat jawaban yang sangat kecil di sini, sehingga saya pikir koma setelah 'Jelly' sebenarnya adalah kode untuk masalah ini
Tasos Papastylianou
28

Oasis , 5 byte

Istilah ke -0 diindeks

cd+1V

Cobalah online!

Penjelasan

   1V   # a(0) = 1
        # a(1) = 1
        # a(2) = 1
        # a(n) =
c       #        a(n-2)
  +     #              +
 d      #               a(n-3)
Emigna
sumber
26

Jelly ,  10 9  8 byte

ŻṚm2Jc$S

Tautan monadik yang menerima n(diindeks 0) yang menghasilkan P(n).

Cobalah online!

Bagaimana?

ImplementsP(n)=i=0n2(i+1n2i)

ŻṚm2Jc$S - Link: integer, n       e.g. 20
Ż        - zero range                  [0, 1, 2, 3, 4, ..., 19, 20]
 Ṛ       - reverse                     [20, 19, ..., 4, 3, 2, 1, 0]
  m2     - modulo-slice with 2         [20, 18, 16, 14, 12, 10,  8,  6,  4,  2,  0]  <- n-2i
      $  - last two links as a monad:
    J    -   range of length           [ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11]  <- i+1
     c   -   left-choose-right         [ 0,  0,  0,  0,  0,  0,  0, 28,126, 45,  1]
       S - sum                         200

Dan di sini ada "twofer"
... metode yang sama sekali berbeda untuk 8 byte (yang ini diindeks 1, tetapi jauh lebih lambat):

3ḊṗRẎ§ċ‘ - Link: n
3Ḋ       - 3 dequeued = [2,3]
   R     - range = [1,2,3,...,n]
  ṗ      -   Cartesian power         [[[2],[3]],[[2,2],[2,3],[3,2],[3,3]],[[2,2,2],...],...]
    Ẏ    - tighten                   [[2],[3],[2,2],[2,3],[3,2],[3,3],[2,2,2],...]
     §   - sums                      [ 2,  3,   4,    5,    5,    6,     6,...]
       ‘ - increment                 n+1
      ċ  - count occurrences         P(n)
Jonathan Allan
sumber
18

Haskell , 26 byte

(l!!)
l=1:1:1:2:scanl(+)2l

Cobalah online! Menghasilkan istilah ke-nol yang diindeks nol.

Saya pikir solusi rekursif "nyata" di bawah ini tidak akan ada duanya, tetapi kemudian saya menemukan ini. Ini mirip dengan ekspresi golf klasik l=1:scanl(+)1luntuk daftar Fibonacci yang tak terbatas, tetapi di sini perbedaan antara elemen-elemen yang berdekatan adalah istilah posisi 4 kembali. Kita bisa lebih langsung menulis l=1:1:zipWith(+)l(0:l), tapi itu lebih lama.

Jika tantangan ini memungkinkan output daftar tanpa batas, kita dapat memotong baris pertama dan memiliki 20 byte.

27 byte

f n|n<3=1|1>0=f(n-2)+f(n-3)

Cobalah online!

Tidak
sumber
11

Python 2 , 30 byte

f=lambda n:n<3or f(n-2)+f(n-3)

Cobalah online!

Mengembalikan istilah ke-nol yang diindeks. Output Trueuntuk 1.

Tidak
sumber
6

Oktaf / MATLAB, 35 33 byte

@(n)[1 filter(1,'cbaa'-98,2:n<5)]

Menghasilkan n istilah pertama .

Cobalah online!

Bagaimana itu bekerja

Fungsi anonim yang mengimplementasikan filter rekursif .

'cbaa'-98adalah bentuk yang lebih pendek untuk diproduksi [1 0 -1 -1].

2:n<5adalah bentuk yang lebih pendek untuk diproduksi [1 1 1 0 0 ··· 0]( n −1 istilah).

filter(1,[1 0 -1 -1],[1 1 1 0 0 ··· 0])meneruskan input [1 1 1 0 0 ··· 0]melalui filter waktu diskrit yang ditentukan oleh fungsi transfer dengan koefisien pembilang 1dan koefisien penyebut [1 0 -1 -1].

Luis Mendo
sumber
6

J , 22 byte

-2 byte terima kasih kepada ngn dan Galen

formulir tertutup, 26 byte

0.5<.@+1.04535%~1.32472^<:

Cobalah online!

berulang, 22 byte

(],1#._2 _3{ ::1])^:[#

Cobalah online!

Jonah
sumber
1
Solusi 24 byte lainnya (membosankan): (1 # .2 3 $: @ - ~]) `1: @. (3 &>) Cobalah online!
Galen Ivanov
23 byte berkat ngn 1:-> #: Cobalah online!
Galen Ivanov
@ GalenIvanov tyvm, itu trik yang bagus.
Jonah
2
1:-> 1. "merugikan" bekerja dengan kata benda di sebelah kanan, tampaknya
ngn
@ngn TIL ... ty lagi!
Jonah
5

Retina , 47 42 byte

K`0¶1¶0
"$+"+`.+¶(.+)¶.+$
$&¶$.(*_$1*
6,G`

Cobalah online! Menghasilkan nistilah pertama pada baris yang berbeda. Penjelasan:

K`0¶1¶0

Ganti input dengan ketentuan untuk -2, -1dan 0.

"$+"+`.+¶(.+)¶.+$
$&¶$.(*_$1*

Hasilkan nistilah berikutnya menggunakan relasi perulangan. *_di sini adalah kependekan $&*_yang mengkonversi nomor (pertama) dalam pertandingan ke unary, sedangkan $1*kependekan $1*_yang mengkonversi nomor tengah ke unary. The $.(pengembalian jumlah desimal argumen unary nya, yaitu jumlah dari angka pertama dan menengah.

6,G`

Buang enam karakter pertama, yaitu tiga baris pertama.

Neil
sumber
5

Cubix , 20 byte

Ini adalah 0 yang diindeks dan menghasilkan istilah ke- N

;@UOI010+p?/sqq;W.\(

Cobalah online!

Bungkus ke sebuah kubus dengan panjang sisi 2

    ; @
    U O
I 0 1 0 + p ? /
s q q ; W . \ (
    . .
    . .

Lihat saja

  • I010 - Memulai tumpukan
  • +p? - Tambahkan bagian atas tumpukan, tarik penghitung dari bagian bawah tumpukan dan tes
  • /;UO@ - Jika penghitung adalah 0, refleksikan ke permukaan atas, hapus TOS, putar balik, keluaran, dan berhenti
  • \(sqq;W - Jika penghitung positif, pantulkan, penghitung penurunan, tukar TOS, tekan atas ke bawah dua kali, hapus TOS dan geser lajur kembali ke loop utama.
MickyT
sumber
4

Perl 6 , 24 byte

{(1,1,1,*+*+!*...*)[$_]}

Cobalah online!

Urutan yang dihasilkan standar cantik, dengan setiap elemen baru dihasilkan oleh ekspresi * + * + !*. Itu menambahkan elemen ketiga sebelumnya, elemen kedua sebelumnya, dan negasi logis dari elemen sebelumnya, yang selalu False, yang secara numerik nol.

Sean
sumber
Mengapa wiki komunitas ini?
Jo King
@ JoKing Mengalahkan saya. Jika saya melakukannya, itu tidak sengaja.
Sean
4

05AB1E , 8 byte

1Ð)λ£₂₃+

Cobalah online!

Bersabarlah, saya belum bermain golf sebentar. Saya ingin tahu apakah ada pengganti yang lebih pendek 1Ð)yang berfungsi dalam kasus ini (saya sudah mencoba 1D), 3Å1dll. Tetapi tidak ada yang menyimpan byte). Menghasilkan pertama istilah urutan. Atau, tanpa , itu akan menghasilkan aliran tak terbatas dari ketentuan urutan.n£

Bagaimana?

1Ð)λ£₂₃+ | Full program.
1Ð)      | Initialize the stack with [1, 1, 1].
   λ     | Begin the recursive generation of a list: Starting from some base case,
         | this command generates an infinite list with the pattern function given.
    £    | Flag for λ. Instead of outputting an infinite stream, only print the first n.
     ₂₃+ | Add a(n-2) and a(n-3).
Tuan Xcoder
sumber
Saya tidak berpikir 1Ð)bisa 2 byte tbh. Saya dapat memikirkan enam alternatif 3-byte yang berbeda , tetapi tidak ada 2-byters.
Kevin Cruijssen
4

APL (Dyalog Unicode) , 20 18 17 byte SBCS

Kode ini 1-diindeks. Jumlah byte yang sama untuk mendapatkan nitem dari urutan Padovan, karena Anda harus menjatuhkan beberapa anggota tambahan terakhir. Ini juga jumlah byte yang sama untuk mendapatkan pengindeksan 0.

Edit: -2 byte terima kasih kepada ngn. -1 byte terima kasih kepada ngn

4⌷2(⊢,⍨2⌷+/)⍣⎕×⍳3

Cobalah online!

Penjelasan

4⌷2(⊢,⍨2⌷+/)⍣⎕×⍳3

  ⍺(. . . .)⍣⎕⍵   This format simply takes the input ⎕ and applies the function
                   inside the brackets (...) to its operands (here marked ⍵ and ⍺).
  2(. . .+/)⍣⎕×⍳3  In this case, our ⍵, the left argument, is the array 1 1 1,
                   where we save our results as the function is repeatedly applied
                   and our ⍺, 2, is our right argument and is immediately applied to +/,
                   so that we have 2+/ which will return the pairwise sums of our array.
       2⌷          We take the second pairwise sum, f(n-2) + f(n-3)
    ⊢,⍨            And add it to the head of our array.
4⌷                 When we've finished adding Padovan numbers to the end of our list,
                   the n-th Padovan number (1-indexed) is the 4th member of that list,
                   and so, we implicitly return that.
Sherlock9
sumber
4

K (ngn / k) , 24 20 byte

-4 byte terima kasih kepada ngn!

{$[x<3;1;+/o'x-2 3]}

Cobalah online!

Diindeks, istilah N pertama

Galen Ivanov
sumber
1
f[x-2]+f[x-3]-> +/o'x-2 3( ois "recur")
ngn
@ ngn Terima kasih! Saya mencobanya (tanpa hasil) di J; elegan di sini.
Galen Ivanov
@ngn Sebenarnya inilah salah satu kemungkinan tampilannya di J: (1 # .2 3 $: @ - ~]) `1: @. (3 &>)
Galen Ivanov
ah, benar, basis-1 decode adalah cara yang ramah kereta untuk menjumlahkan :)
ngn
2
1:-> #dalam solusi j
ngn
4

x86 kode mesin 32-bit, 17 byte

53 33 db f7 e3 43 83 c1 04 03 d8 93 92 e2 fa 5b c3

Membongkar:

00CE1250 53                   push        ebx  
00CE1251 33 DB                xor         ebx,ebx  
00CE1253 F7 E3                mul         eax,ebx  
00CE1255 43                   inc         ebx  
00CE1256 83 C1 04             add         ecx,4  
00CE1259 03 D8                add         ebx,eax  
00CE125B 93                   xchg        eax,ebx  
00CE125C 92                   xchg        eax,edx  
00CE125D E2 FA                loop        myloop (0CE1259h)  
00CE125F 5B                   pop         ebx  
00CE1260 C3                   ret

Diindeks 0. Inisialisasi mudah dicapai dengan menghitung eax * 0. Hasil 128-bit adalah 0, dan berjalan di edx: eax.

Pada awal setiap iterasi, urutan register adalah ebx, eax, edx. Saya harus memilih urutan yang tepat untuk memanfaatkan pengodean untuk xchg eaxinstruksi - 1 byte.

Saya harus menambahkan 4 ke penghitung lingkaran agar keluaran mencapai eax, yang menyimpan nilai fungsi kembali dalam fastcallkonvensi.

Saya dapat menggunakan beberapa konvensi panggilan lain, yang tidak memerlukan penyimpanan dan pemulihan ebx, tetapi fastcalltetap menyenangkan :)

anatolyg
sumber
2
Saya suka melihat jawaban kode mesin pada PP&CG! +1
Tau
3

Lua 5.3,49 48 byte

function f(n)return n<4 and 1or f(n-2)+f(n-3)end

Cobalah online!

Vanilla Lua tidak memiliki paksaan boolean ke string (bahkan tonumber(true)kembali nil), jadi Anda harus menggunakan operator pseudo-ternary. Versi ini 1-diindeks, seperti semua Lua. Bagian 1oritu harus diubah ke 1 ordalam Lua 5.1, yang memiliki cara berbeda untuk nomor lexing.

pengendara sepeda
sumber
3

JavaScript (ES6), 23 byte

a(0)=a(1)=a(2)=1

N

f=n=>n<3||f(n-2)+f(n-3)

Cobalah online!

Arnauld
sumber
Saya tidak berpikir masuk akal untuk mengatakan bahwa pengembalian trueitu sama dengan pengembalian 1jika sisa outputnya adalah angka.
Nit
2
@Nit meta postingan yang relevan .
Arnauld
Saya pikir Anda kehilangan beberapa persyaratan: Lihat modifikasi saya (versi di Jawa) di sini .
Shaq
@Shaq Tantangan dengan jelas menetapkan bahwa tiga syarat pertama dari urutan semuanya adalah 1 . Jadi, ini bukan urutan yang ditentukan dalam A000931 (tetapi rumusnya sama).
Arnauld
@Arnauld ya saya bisa melihatnya sekarang. Maaf!
Shaq
2

Japt -N , 12 byte

<3ªßUµ2 +ß´U

Cobalah

Perwujudan Ketidaktahuan
sumber
Sepertinya 12 adalah yang terbaik yang bisa kita lakukan: \
Shaggy
Saya berdiri dikoreksi!
Shaggy
2

TI-BASIC (TI-84), 34 byte

[[0,1,0][0,0,1][1,1,0]]^(Ans+5:Ans(1,1

N

Input di Ans.
Keluaran dalam Ansdan secara otomatis dicetak.

Saya pikir sudah cukup waktu berlalu, ditambah beberapa jawaban telah diposting, yang mana ada banyak yang mengabaikan jawaban ini.

Contoh:

0
               0
prgmCDGFD
               1
9
               9
prgmCDGFD
               9
16
              16
prgmCDGFD
              65

Penjelasan:

[[0,1,0][0,0,1][1,1,0]]^(Ans+5:Ans(1,1      ;full program (example input: 6)

[[0,1,0][0,0,1][1,1,0]]                     ;generate the following matrix:
                                            ; [0 1 0]
                                            ; [0 0 1]
                                            ; [1 1 0]
                       ^(Ans+5              ;then raise it to the power of: input + 5
                                            ; [4  7 5]
                                            ; [5  9 7]
                                            ; [7 12 9]
                               Ans(1,1      ;get the top-left index and leave it in "Ans"
                                            ;implicitly print Ans
Tau
sumber
2

Pyth, 16 byte

L?<b3!b+y-b2y-b3

Ini mendefinisikan fungsi y. Coba di sini!

Inilah solusi yang lebih menyenangkan, meskipun lebih lama 9 byte; byte bisa dicukur.

+l{sa.pMf.Am&>d2%d2T./QY!

Ini menggunakan definisi yang diberikan oleh David Callan pada halaman OEIS: "a (n) = jumlah komposisi n menjadi bagian-bagian yang ganjil dan> = 3." Coba di sini! Dibutuhkan input secara langsung alih-alih mendefinisikan suatu fungsi.

RK.
sumber
y-b2y-b3mungkin bisa di refactored dengan dab dua atau L? Padahal mendeklarasikan array 2 elemen itu mahal. yL-Lb2,3lebih panjang :(
Ven
@Ven saya bisa mengganti +y-b2y-b3dengan smy-bdhB2jumlah byte yang sama; hB2hasil dalam array[2, 3]
RK.
Dilakukan dengan baik hB2. Sayang sekali itu jumlah byte yang sama.
Ven
Ya, meskipun saya bertanya-tanya apakah ada cara untuk menyingkirkan ddi peta.
RK.
2

Java, 41 byte

Tidak dapat menggunakan lambda (kesalahan runtime). Port jawaban Javascript ini

int f(int n){return n<3?1:f(n-2)+f(n-3);}

TIO

Benjamin Urquhart
sumber
Saya pikir Anda kehilangan beberapa persyaratan: Lihat modifikasi saya di sini .
Shaq
Harap abaikan komentar Shaq: jawaban Anda benar dan mungkin jawaban Java terpendek (per Java 12).
Olivier Grégoire
Baiklah kalau begitu. Saya tidak yakin apa yang saya "lewatkan" tetapi ok. Sunting: nvm Saya membaca jawaban JS.
Benjamin Urquhart
2

R + pryr , 38 36 byte

Fungsi rekursif tanpa indeks.

f=pryr::f(`if`(n<3,1,f(n-2)+f(n-3)))

Cobalah online!

Terima kasih kepada @Giuseppe karena menunjukkan dua byte yang jelas tidak perlu.

rturnbull
sumber
2
Jika Anda akan menggunakan pryr, bahasanya harus R + pryrdan ini bisa 36 byte
Giuseppe
@Giuseppe terima kasih! Diperbarui sekarang.
rturnbull