Wythoff Atas atau Bawah?

20

Pertama, mari kita bicara tentang urutan Beatty . Diberikan bilangan irasional positif r , kita dapat membangun urutan tak terbatas dengan mengalikan bilangan bulat positif menjadi r dalam urutan dan mengambil dasar setiap perhitungan yang dihasilkan. Sebagai contoh,
Urutan Beatty dari r

Jika r > 1, kami memiliki kondisi khusus. Kita dapat membentuk nomor lain irasional s sebagai s = r / ( r - 1). Ini kemudian dapat menghasilkan urutan Beatty sendiri, B s . Trik rapi adalah bahwa B r dan B s adalah saling melengkapi , yang berarti bahwa setiap bilangan bulat positif adalah persis salah satu dari dua sekuens.

Jika kita menetapkan r = ϕ, rasio emas, maka kita mendapatkan s = r + 1, dan dua urutan khusus. The rendah Wythoff urut untuk r :

1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... 

dan urutan Wythoff atas untuk s :

2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... 

Ini adalah urutan A000201 dan A001950 di OEIS, masing-masing.

Tantangan

Diberikan integer input positif 1 <= n <= 1000, output salah satu dari dua nilai berbeda yang menunjukkan apakah input berada di urutan Wythoff yang lebih rendah atau urutan atas . Nilai output dapat berupa -1dan 1, truedan false, upperdan lower, dll.

Meskipun algoritme yang Anda kirim harus bekerja secara teoritis untuk semua input, dalam praktiknya hanya bekerja dengan 1000 angka input pertama.

I / O dan Aturan

  • Input dan output dapat diberikan dengan metode apa pun yang mudah .
  • Input dan output dapat dianggap sesuai dengan jenis nomor asli bahasa Anda.
  • Program lengkap atau fungsi dapat diterima. Jika suatu fungsi, Anda dapat mengembalikan output daripada mencetaknya.
  • Celah standar dilarang.
  • Ini adalah sehingga semua aturan golf biasa berlaku, dan kode terpendek (dalam byte) menang.
AdmBorkBork
sumber
1
Ini pada dasarnya "golf urutan Wythoff yang lebih rendah" karena urutan Wythoff atas membutuhkan 1 op lebih dari yang lebih rendah (kuadrat phi).
Magic Gurita Guci

Jawaban:

12

JavaScript (ES6), 50 35 byte

f=(n,s="1",t=0)=>s[n-1]||f(n,s+t,s)
<input type=number min=1 oninput=o.textContent=this.value&amp;&amp;f(this.value)><pre id=o>

Output 1untuk yang lebih rendah dan yang lebih 0tinggi. Penjelasan: daftar Partial nilai boolean dapat dibangun menggunakan Fibonacci seperti identitas: diberikan dua daftar, dimulai dengan 1dan 10, setiap daftar berikutnya adalah gabungan dari dua sebelumnya, sehingga 101, 10110, 10110101dll Dalam hal ini itu sedikit Golfier untuk memiliki entri 0 palsu 0dan menggunakannya untuk membangun elemen kedua dari daftar.

Neil
sumber
4
Bagaimana apa ...
AdmBorkBork
4
Saya suka bagaimana penjelasannya membuat saya kurang mengerti +1. Whooits boolean parsial mencuri identitas seorang pria bernama Fibbonacci, yang kemudian dihubungkan bersama dengan cucunya untuk memalsukan masuknya konstruksi.
Magic Gurita Guci
Saya ingin tahu sejauh mana versi 33-byte ini dapat bekerja dengan menggunakan perkiraan. Jawabannya tampaknya hingga n = 375 .
Arnauld
7

Haskell , 26 byte

(l!!)
l=0:do x<-l;[1-x..1]

Cobalah online!

Tidak ada pelampung, presisi tak terbatas. Terima kasih atas H.PWiz untuk dua byte.

Tidak
sumber
Ini juga akan menjadi 26 byte, tapi saya tidak mengerti mengapa itu tidak berhasil
H.PWiz
@ H. WWW Saya pikir itu karena daftar kosong adalah titik tetap.
xnor
Ah, saya tidak mempertimbangkan itu, dan membandingkannya dengan metode "setara" yang digunakan ~(x:t). Terima kasih
H.PWiz
@ H.PWiz / xnor Secara teknis di Haskell titik tetap yang digunakan adalah yang terkecil secara denotasional, di sini bawah / undefined. Fakta bahwa ada dua definisi yang berbeda juga hanya kebetulan.
Ørjan Johansen
7

Python , 25 byte

lambda n:-n*2%(5**.5+1)<2

Cobalah online!

Gunakan kondisi yang sangat sederhana:

nada di urutan Wythoff yang lebih rendah tepatnya jika -n%phi<1.

Perhatikan bahwa hasil modulo positif meskipun -nnegatif, cocok dengan bagaimana Python melakukan modulo.

Bukti: Biarkan a = -n%phi, yang terletak di kisaran 0 <= a < phi. Kita bisa membagi -nmodulo phisebagai -n = -k*phi + auntuk beberapa bilangan bulat positif k. Atur ulang itu menjadi n+a = k*phi.

Jika a<1, maka n = floor(n+a) = floor(k*phi), dan begitu juga dalam urutan Wythoff yang lebih rendah.

Jika tidak, kita memiliki 1 <= a < phibegitu

n+1 = floor(n+a) = floor(k*phi)
n > n+a-phi = k*phi - phi = (k-1)*phi

jadi njatuh di celah antara floor((k-1)*phi)dan floor(k*phi) dan dilewatkan oleh urutan Wythoff yang lebih rendah.

Ini sesuai dengan kode ini:

lambda n:-n%(5**.5/2+.5)<1

Cobalah online!

Kami menyimpan byte dengan menggandakan ke -(n*2)%(phi*2)<2.

Tidak
sumber
Bisakah Anda menjelaskan bagaimana formula itu muncul? Saya mencoba untuk menurunkannya dari definisi urutan, tetapi tersesat di hutan.
sundar - Reinstate Monica
@sundar Menambahkan bukti.
xnor
5

05AB1E , 9 byte

L5t>;*óså

Cobalah online!


0 berarti atas, 1 berarti lebih rendah. Coba 100 yang pertama: Coba online!


    CODE   |      COMMAND      # Stack (Input = 4)
===========+===================#=======================
L          | [1..a]            # [1,2,3,4]
 5t>;      | (sqrt(5) + 1)/2   # [phi, [1,2,3,4]]
     *     | [1..a]*phi        # [[1.6,3.2,4.8,6.4]]
      ó    | floor([1..a]*phi) # [[1,3,4,6]]
       så  | n in list?        # [[1]]

Dump Perintah Baku:

----------------------------------
Depth: 0
Stack: []
Current command: L

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4]]
Current command: 5

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], '5']
Current command: t

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], 2.23606797749979]
Current command: >

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], 3.23606797749979]
Current command: ;

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], 1.618033988749895]
Current command: *

----------------------------------
Depth: 0
Stack: [[1.618033988749895, 3.23606797749979, 4.854101966249685, 6.47213595499958]]
Current command: ó

----------------------------------
Depth: 0
Stack: [[1, 3, 4, 6]]
Current command: s

----------------------------------
Depth: 0
Stack: [[1, 3, 4, 6], '4']
Current command: å
1
stack > [1]
Guci Gurita Ajaib
sumber
Saya memiliki hal yang sama, tetapi menggunakan ï:)
Emigna
@ emigna saya terkejut phi tidak ada dalam konstanta matematika. 5t>;untuk byter 2 mungkin tidak sepadan ...
Magic Octopus Mm
Ya, saya setengah ingat bahwa itu mungkin (tapi tidak). Sepertinya sesuatu yang harus kita tambahkan.
Emigna
@Emigna Saya cukup yakin jawaban Jelly benar tetapi dengan phi built-in hahah.
Magic Gurita Guci
Haha saya memiliki hal yang sama tetapi menggunakan ïdan ¢lol :) Semua solusi kami sangat erat terkait
Tn. Xcoder
5

Jelly , 5 byte

N%ØpỊ

Cobalah online!

Disimpan 1 byte berkat xnor's Python golf .


Jelly , 6 byte

×€ØpḞċ

Cobalah online!

Mengembalikan 1 untuk lebih rendah dan 0 untuk atas.

×€ØpḞċ – Full Program / Monadic Link. Argument: N.
×€     – Multiply each integer in (0, N] by...
  Øp   – Phi.
    Ḟ  – Floor each of them.
     ċ – And count the occurrences of N in that list.

(0,N]Zφ>1N>00<N<Nφ

Tuan Xcoder
sumber
Saya menduga salah satunya adalah konstanta 1-byte untuk phi: P?
Magic Gurita Guci
2
Tidak, satu dua byte:Øp
Tn. Xcoder
Hehe, lebih baik daripada 4-byte saya di 05AB1E:5t>;
Magic Octopus Mm
4

Brain-Flak , 78 byte

([{}]()){<>{}((([()]))){{<>({}())}{}(([({})]({}{})))}<>([{}]{}<>)}<>({}()){{}}

Cobalah online!

Output apa-apa untuk yang lebih rendah dan 0atas. Mengubah skema output yang lebih masuk akal akan menelan biaya 6 byte.

Nitrodon
sumber
4

Python 2 , 39 33 32 byte

-6 byte terima kasih kepada Tn. Xcoder
-1 byte terima kasih kepada Zacharý

lambda n,r=.5+5**.5/2:-~n//r<n/r

Cobalah online!

Pengembalian Falseuntuk yang lebih rendah dan Trueatas

tongkat
sumber
lambda n,r=(1+5**.5)/2:-~n//r<n/rmenghemat 6 byte.
Tn. Xcoder
1
Juga, lambda n,r=.5+5**.5/2:-~n//r<n/rharus bekerja juga untuk mencukur satu byte
Zacharý
3

Julia 0,6 , 16 byte

n->n÷φ<-~n÷φ

Cobalah online!

Sambil bermain-main dengan angka-angka, saya menemukan properti ini: lantai (n / φ) == lantai ((n + 1) / φ) jika n berada di urutan Wythoff atas, dan lantai (n / φ) <lantai ( (n + 1) / φ) jika n berada di urutan Wythoff yang lebih rendah. Saya belum menemukan bagaimana properti ini muncul, tetapi memberikan hasil yang benar setidaknya hingga n = 100000 (dan mungkin di luar).


Jawaban lama:

Julia 0,6 , 31 byte

n->n∈[floor(i*φ)for i1:n]

Cobalah online!

Mengembalikan trueuntuk falseurutan Wythoff yang lebih rendah dan atas.

sundar - Pasang kembali Monica
sumber
Karena n / φ dari angka hingga n lebih rendah dan yang lain di atas, perbedaan rata-rata antara angka lebih rendah berturut-turut adalah φ; membagi angka yang lebih rendah dengan φ memberi Anda urutan di mana perbedaan rata-rata adalah 1; ini memungkinkan lantai urutan itu menjadi bilangan bulat. Matematika saya tidak cukup baik untuk melanjutkannya.
Neil
1

Bahasa Wolfram (Mathematica) , 26 byte

#~Ceiling~GoldenRatio<#+1&

Cobalah online!

Integer nada di Wythoff Sequence iff ceil(n/phi) - 1/phi < n/phi.

Bukti itu ceil(n/phi) - 1/phi < n/phiadalah ...

Cukup:

  1. Mari ceil(n/phi) - 1/phi < n/phi.

  2. Lalu ceil(n/phi) * phi < n + 1,.

  3. Catatan n == n/phi * phi <= ceil(n/phi) * phi.

  4. Karenanya n <= ceil(n/phi) * phi < n + 1,.

  5. Karena ndan ceil(n/phi)bilangan bulat, kami menerapkan definisi lantai dan negara bagian floor(ceil(n/phi) * phi) == n, dan nberada dalam urutan Wythoff yang lebih rendah.

Perlu; bukti oleh kontrapositif:

  1. Mari ceil(n/phi) - 1/phi >= n/phi.

  2. Lalu ceil(n/phi) * phi >= n + 1,.

  3. Catatan n + phi > (n/phi + 1) * phi > ceil(n/phi) * phi

  4. Oleh karena itu n > (ceil(n/phi) - 1) * phi.

  5. Karena (ceil(n/phi) - 1) * phi < n < n + 1 <= ceil(n/phi) * phi, ntidak dalam urutan Wythoff yang lebih rendah.

JungHwan Min
sumber
Ini juga tidak memiliki kesalahan pembulatan.
user202729
1

Japt , 10 byte

Mengembalikan nilai true untuk lower dan false untuk upper.

õ_*MQ fÃøU

Cobalah online!

Penjelasan:

õ_*MQ fÃøU
             // Implicit U = Input
õ            // Range [1...U]
 _           // Loop through the range, at each element:
  *MQ        //   Multiply by the Golden ratio
      f      //   Floor
       Ã     // End Loop
        øU   // Return true if U is found in the collection
Oliver
sumber
1
Saya punya ini untuk 10 byte juga.
Shaggy
1

Java 10, 77 53 52 byte

n->{var r=Math.sqrt(5)/2+.5;return(int)(-~n/r)<n/r;}

Pelabuhan @ Rod's Python 2 menjawab .
-1 byte terima kasih kepada @ Zacharý .

Cobalah online.


Tua Jawaban 77 76 byte:

n->{for(int i=0;i++<n;)if(n==(int)((Math.sqrt(5)+1)/2*i))return 1;return 0;}

-1 byte terima kasih @ovs untuk sesuatu yang saya rekomendasikan sendiri minggu lalu .. xD

Pengembalian 1untuk yang lebih rendah; 0untuk atas.

Cobalah online.

Penjelasan:

n->{                    // Method with integer as both parameter and return-type
  for(int i=0;++i<=n;)  //  Loop `i` in the range [1, `n`]
    if(n==(int)((Math.sqrt(5)+1)/2*i))
                        //   If `n` is equal to `floor(Phi * i)`:
      return 1;         //    Return 1
  return 0;}            //  Return 0 if we haven't returned inside the loop already

i*Phidihitung dengan mengambil (sqrt(5)+1)/2 * i, dan kami kemudian lantai itu dengan melemparkannya ke integer untuk memotong desimal.

Kevin Cruijssen
sumber
1
++i<=npada jawaban lama Anda bisa i++<n.
Ov
1
@ovs tentu saja ..>. < Saya sebenarnya merekomendasikan golf ini kepada orang lain minggu lalu , lol .. Terima kasih.
Kevin Cruijssen
1
Saya pikir ini harus bekerja untuk -1 byte:n->{var r=Math.sqrt(5)/2+.5;return(int)(-~n/r)<n/r;}
Zacharý
@ Zacharý Memang, terima kasih!
Kevin Cruijssen
1

Haskell , 153 139 126 79 byte

Presisi Tanpa Batas!

l=length
f a c|n<-2*l a-c,n<0||l a<a!!n=c:a|1>0=a
g x=x==(foldl f[][1..x+1])!!0

Cobalah online!

Penjelasan

Alih-alih menggunakan perkiraan rasio emas untuk menghitung makna hasil, mereka cenderung mengalami kesalahan saat ukuran input naik. Jawaban ini tidak. Sebaliknya ia menggunakan rumus yang disediakan pada OEIS yang amerupakan urutan unik sehingga

n . b(n) = a(a(n))+1

di mana bpujian dipesan.

Wisaya Gandum
sumber
1
"Semua" bahkan tidak benar sebelum kamu dikalahkan ...
Neil
@Neil Poin bagus. Saya pasti ketinggalan jawaban Anda.
Wheat Wizard
Meskipun jawaban Anda dibatasi oleh fakta bahwa javascript tidak memiliki tipe integral?
Wheat Wizard
Nah, itu akan kehabisan memori jauh sebelum itu ...
Neil
1

Brachylog , 8 byte

≥ℕ;φ×⌋₁?

Cobalah online!

Predikat berhasil jika input berada di urutan Wythoff yang lebih rendah dan gagal jika berada di urutan Wythoff atas.

 ℕ          There exists a whole number
≥           less than or equal to
            the input such that
  ;φ×       multiplied by phi
     ⌋₁     and rounded down
       ?    it is the input.

Jika kegagalan untuk mengakhiri adalah metode output yang valid, byte pertama dapat dihilangkan.

String yang tidak terkait
sumber
Ini mungkin pertama kalinya φdigunakan dalam program Brachylog. Akhirnya!
Fatalkan
0

MATL , 8 byte

t:17L*km

Cobalah online!

Penjelasan

t      % Implicit input. Duplicate
:      % Range
17L    % Push golden ratio (as a float)
*      % Multiply, element-wise
k      % Round down, element-wise
m      % Ismember. Implicit output
Luis Mendo
sumber
0

K (oK) , 20 byte

Larutan:

x in_(.5*1+%5)*1+!x:

Cobalah online!

Penjelasan:

x in_(.5*1+%5)*1+!x: / the solution
                  x: / save input as x
                 !   / generate range 0..x
               1+    / add 1
              *      / multiply by
     (       )       / do this together
           %5        / square-root of 5
         1+          / add 1
      .5*            / multiply by .5
    _                / floor
x in                 / is input in this list?
streetster
sumber
0

TI-BASIC (TI-84), 18 byte

max(Ans=iPart((√(5)+1)/2randIntNoRep(1,Ans

Input di Ans.
Keluaran dalam Ansdan secara otomatis dicetak.
Mencetak 1jika input berada di urutan bawah atau0 jika berada di urutan atas.

0<N<1000

Contoh:

27
             27
prgmCDGFA
              1
44
             44
prgmCDGFA
              0

Penjelasan:

max(Ans=iPart((√(5)+1)/2randIntNoRep(1,Ans    ;full program, example input: 5
                        randIntNoRep(1,Ans    ;generate a list of random integers in [1,Ans]
                                               ; {1, 3, 2, 5, 4}
              (√(5)+1)/2                      ;calculate phi and then multiply the resulting
                                              ;list by phi
                                               ; {1.618 4.8541 3.2361 8.0902 6.4721}
        iPart(                                ;truncate
                                               ; {1 4 3 8 6}
    Ans=                                      ;compare the input to each element in the list
                                              ;and generate a list based off of the results
                                               ; {0 0 0 0 0}
max(                                          ;get the maximum element in the list and
                                              ;implicitly print it

Catatan: TI-BASIC adalah bahasa tokenized. Jumlah karakter tidak sama dengan jumlah byte.

Tau
sumber
0

cQuents , 5 byte

?F$`g

Cobalah online!

Penjelasan

?         output true if in sequence, false if not in sequence
          each term in the sequence equals:

 F        floor (
  $               index * 
   `g                     golden ratio
     )                                 ) implicit
Stephen
sumber