Urutan Melompat

19

Pertimbangkan urutan berikut:

0 1 3 2 5 4 8 6 7 12 9 10 11 17 13 14 15 16 23 ...

Terlihat cantik tanpa pola, kan? Begini cara kerjanya. Mulai dengan 0, lompat nbilangan bulat, dengan nmulai dari 1. Itu nomor berikutnya dalam urutan. Kemudian, tambahkan angka "dilewati" dan itu belum terlihat dalam urutan menaik. Kemudian, kenaikan ndan lompat dari nomor terakhir ditambahkan. Ulangi pola ini.

Jadi, misalnya, ketika kami mencapai 11, kami berada di n=5. Kami naik nmenjadi n=6, melompat ke atas 17, lalu menambahkan 13 14 15 16karena itu belum terlihat. Lompatan kita berikutnya adalah n=7, jadi elemen berikutnya dalam urutannya adalah 23.

Tantangan

Input yang diberikan x, output xistilah ke-5 dari urutan ini, xpersyaratan pertama dari urutan tersebut, atau membuat daftar syarat-syarat dari urutan tersebut. Anda dapat memilih pengindeksan 0 atau 1.

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 kode-golf sehingga semua aturan golf biasa berlaku, dan kode terpendek (dalam byte) menang.

code-golf sequence AdmBorkBork
sumber

Ini tampaknya belum (belum?) Di OEIS

JayCe

@JayCe Saya tidak terkejut - ini adalah urutan yang cukup arbitrer.

AdmBorkBork

Jawaban:

24

JavaScript (ES7), 41 byte

Mengembalikan istilah ke-n dari urutan, 0-diindeks.

n=>(d=(n--*8-23)**.5)%1?n:'121'[n]^n-~d/2

Cobalah online!

Bagaimana?

Kasus utama: $n > 3$

Empat istilah pertama dari urutan itu spesial, jadi mari kita kesampingkan untuk saat ini.

Untuk , urutannya terlihat seperti itu: $n > 3$

 n  | [4] 5 [6] 7 8 [ 9] 10 11 12 [13] 14 15 16 17 [18] 19 20 21 22 23 [24] 25 26 27 ...
----+------------------------------------------------------------------------------------
a(n)| [5] 4 [8] 6 7 [12]  9 10 11 [17] 13 14 15 16 [23] 18 19 20 21 22 [30] 24 25 26 ...
----+------------------------------------------------------------------------------------
 k  |  2  -  3  - -   4   -  -  -   5   -  -  -  -   6   -  -  -  -  -   7   -  -  - ...

Kita dapat melihat bahwa sebenarnya ada dua sub-urutan yang disisipkan:

Sebagian besar nilai milik sub-urutan yang kami miliki: $A$

$SEBUAH (n) = n - 1$ $A(n) = n - 1$
Beberapa nilai lain milik sub-urutan (disorot dengan tanda kurung dalam diagram di atas) yang indeksnya mengikuti urutan aritmatika 3, 3, 4, 6, 9, 13, 18, 24 ... dan yang kami miliki: $B$

$B (n, k) = n + k - 1$ $B(n,k) = n + k - 1$
di mana adalah indeks dalam urutan utama dan adalah indeks dalam sub-urutan . $n$ $k$ $B$

Indeks dalam urutan utama diberikan oleh: $B$

n_{k} = \frac{k^{2} - k + 6}{2}

$n_k = \frac{k^2 - k + 6}{2}$

Diberikan , kita tahu bahwa istilah yang sesuai dalam urutan utama milik jika adalah solusi integer dari persamaan kuadratik: $n$ $B$ $n$

x^{2} - x + 6 - 2 n = 0

$x^2 - x + 6 - 2n = 0$

yang diskriminan adalah:

Δ = 1 - 4 (6 - 2 n) = 8 n - 23

$\Delta = 1 - 4(6 - 2n) = 8n - 23$

dan yang solusi positifnya adalah:

x = \frac{1 + \sqrt{Δ}}{2}

$x = \frac{1 + \sqrt{\Delta}}{2}$

Kami berharap menjadi bilangan bulat. Karenanya tes: $\sqrt{\Delta}$

(d = (n-- * 8 - 23) ** .5) % 1

Kasus khusus: $0 \le n \le 3$

Untuk , diskriminan negatif dan mengambil hasil akar kuadratnya dalam NaN . Untuk , diskriminan adalah . Oleh karena itu, ini pertama empat hal urutan dianggap milik sub-urutan . $n < 3$ $n = 3$ $1$ $B$

Jika kita hanya menerapkan rumus standar n - ~ d / 2 , kita akan mendapatkan:

- \frac{1}{2}, \frac{1}{2}, \frac{3}{2}, 3

$-\frac 1 2, \frac 1 2, \frac 3 2, 3$

dari pada:

0, 1, 3, 2

$0, 1, 3, 2$

Itulah sebabnya kami XOR hasil ini dengan masing-masing. $0,1,2\text{ and }1$

Arnauld
sumber

10

Sekam , 12 byte

Θṁṙ_1C+ḣ2tNN

Cobalah online!

Keluaran sebagai daftar tak terbatas. Berikut adalah versi yang mencetak N pertama .

Penjelasan

Θṁṙ_1C + ḣ2tNN - Program lengkap. Tidak mengambil input, output ke STDOUT.
         tN - Bangun daftar bilangan asli tak hingga, mulai dari 2.
      + ḣ2 - Dan menambahkan [1, 2] untuk itu. Hasil [1,2,2,3,4,5,6,7,8,9,10,11, ...].
     CN - Potong daftar tak terbatas dari bilangan bulat positif menjadi beberapa bagian
               ukuran. Hasil [[1], [2,3], [4,5], [6,7,8], [9,10,11,12], ...].
 ṁ - Memetakan dan meratakan hasilnya setelahnya.
  ṙ_1 - Putar masing-masing ke kanan sebanyak 1 unit.
               Hasil [1,3,2,5,4,8,6,7,12,9,10,11, ...]
Θ - Sertakan a. Yields [0,1,3,2,5,4,8,6,7,12,9,10,11, ...]

Tuan Xcoder
sumber

7

Haskell , 43 byte

0:1:3:2:5!3
a!n=a:[a-n+2..a-1]++(a+n)!(n+1)

Cobalah online!

Menentukan daftar tanpa batas:

  0:1:3:2:(5!3)
≡ 0:1:3:2:5:4:(8!4)
≡ 0:1:3:2:5:4:8:6:7:(12!5)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:(17!6)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:17:13:14:15:16:(23!7) …

Lynn
sumber

4

Jelly , 15 byte

+‘ɼṪRṙ-œ|@
0Ç¡ḣ

Ini adalah program lengkap yang, mengingat n , mencetak n item pertama dari urutan.

Cobalah online!

Bagaimana itu bekerja

0Ç¡ḣ        Main link. Argument: n

0           Set the return value to 0.
 Ç¡         Call the helper link n times, first with argument 0, then n-1 times
            with the previous return value as argument.
   ḣ        Head; extract the first n items of the last return value.


+‘ɼṪRṙ-œ|@  Helper link. Argument: A (array)

 ‘ɼ         Increment the value in the register (initially 0) and yield it.
+           Add that value to all items in the sequence.
   Ṫ        Tail; extract the last item.
    R       Range; map k to [1, .., k].
     ṙ-     Rotate -1 units to the left, yielding [k, 1, ..., k-1].
       œ|@  Perform multiset union of A and the previous return value.

Dennis
sumber

3

C (gcc), 73 67 64 byte

t,d;f(x){for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);t=x<4?x^x/2:x-1;}

Cobalah online!

Menentukan fungsi fyang mengambil 0-diindeks ndan menghasilkan nnomor th dalam urutan.

Kita dapat menganalisis urutan sebagai berikut:

f(n)  = n   where n = 0, 1

f(2)  = 3   // 2 and 3 are swapped
f(3)  = 2

f(4)  = 5   // (+2,+3)
f(6)  = 8   // (+3,+4)
f(9)  = 12  // (+4,+5)
f(13) = 17  // (...)
...

f(n)  = n-1 // for all cases not yet covered

Pertama kita menangani bagian tengah:

for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);

Perhatikan bahwa argumen di sebelah kiri (4, 6, 9, 13, ...) mengikuti pola: pertama tambahkan dua, lalu tambahkan tiga, lalu tambahkan empat, dan seterusnya. Kami mulai t=4dan menambahkan d(yang dimulai pada 2) setiap iterasi dari loop, bertambah ddalam proses.

Tubuh loop lebih menarik. Ingatlah bahwa kami ingin memetakan 4 hingga 5, 6 hingga 8, 9 hingga 12, dll .; itu hanya menambahkan d-1jika xada t. Namun, logika ini muncul sebelum kasus terakhir f(n) = n - 1,, jadi kami tahu kami akan mengurangi 1 di akhir. Karena itu, kita cukup menambahkan dif x == t( x-t||(x+=d)). Namun, kita juga perlu untuk keluar dari loop segera setelah ini - jadi kita tambahkan bahwa untuk dmendapatkan absurd-cari d+=x+=d, yang akan selalu membuat d<xkondisi gagal.

Ini mencakup semuanya kecuali untuk empat nilai pertama. Melihat mereka dalam biner, kita mendapatkan:

00 -> 00
01 -> 01
10 -> 11
11 -> 10

Jadi, kami ingin membalik bit terakhir jika 2 <= x < 4. Ini dipenuhi dengan x^x/2. x/2memberikan bit paling signifikan kedua, jadi XORing ini dengan nomor asli membalik bit terakhir jika jumlahnya 2 atau 3.

Gagang pintu
sumber

3

Jelly , 13 10 byte

-3 Terima kasih kepada Dennis (gunakan pengindeksan 0 untuk menyimpan 2 dari pengaturan jumlah kumulatif dan penurunan akhir)

Ḷ»2Äi+_>2$

Tautan monadik yang menerima integer, 0 -indexed n , yang mengembalikan integer, a (n)

Cobalah online! Atau lihat test-suite

Jonathan Allan
sumber

Bagus! Saya pernah ḶÄ+3i+’, tetapi tidak tahu bagaimana menangani kasus tepi.

Dennis

Saya juga memiliki Ḷ»ạ¥3untuk Ḋ3,2;- terasa seperti harus ada terser untuk sedikit ini.

Jonathan Allan

Ḷ»2Äi+_>2$menghemat 3 byte, dengan pengindeksan berbasis 0.

Dennis

Oh golf yang luar biasa! Saya terjebak di tanah 1-indeks.

Jonathan Allan

2

Perl 5 dengan `-pl`, 70 byte

$"="|";push@f,$;=$f[-1]+$-++,grep!/^(@f|$;)$/,0..$;for 0..$_;$_=$f[$_]

Cobalah online!

Dom Hastings
sumber

2

MATL , 22 byte

1y:"t0)@+h5M:yX-h]qw:)

Menghasilkan nistilah pertama dari urutan.

Cobalah online!

Penjelasan

1         % Push 1
y         % Implicit input: n. Duplicate from below
":        % For each k in [1 2 ... n]
  t0)     %   Duplicate sequence so far. Get last entry, say m
  @+      %   Add k: gives m+k
  h       %   Concatenate horizontally
  5M      %   Push m+k again
  :       %   Range [1 2 ... m+k]
  y       %   Duplicate from below
  X-      %   Set difference
  h       %   Concatenate horizontally
]         % End
q         % Subtract 1, element-wise
w         % Swap. Brings original copy of n to the top
:)        % Keep the first n entries. Implicit display

Luis Mendo
sumber

Saya suka smilie pada akhirnya, sekarang saya ingin semua program MATL saya berakhir dengan senyuman. :)

sundar - Reinstate Monica

@sundar Ya, saya senang itu idiom yang relatif umum di MATL :-D

Luis Mendo

2

Haskell , 51 byte

0:1:do(a,b)<-zip=<<(1:)$scanl(+)3[2..];b:[a+1..b-1]

Cobalah online!

Agak lebih lama dari jawaban Lynn's Haskell , tetapi pendekatan yang berbeda mungkin menarik.

Laikoni
sumber

1

Ruby , 73 byte

f=->x,l,n{!l[x]&&(i=l[-1];f[x,l+[i+n]+([*(i+1...i+n)]-l),n+1])||l[0...x]}

Cobalah online!

Fungsi rekursif yang mengembalikan x angka pertama dari daftar.

crashoz
sumber

1

QBasic, 58 byte

DO
b=r+j
?b
r=b
FOR x=a+1TO b-1
?x
r=x
NEXT
a=b
j=j+1
LOOP

Output tanpa batas. Anda mungkin ingin menambahkan SLEEP 1di dalam lingkaran atau membuatnya LOOP WHILE b<100atau sesuatu seperti itu untuk melihat hasilnya.

Ini pada dasarnya hanya mengimplementasikan spek. Perhatikan bahwa angka yang kita kembalikan akan selalu berupa angka antara angka yang melompat-baru dan angka yang melompat-ke sebelum itu. Jadi kami menyimpan batasan-batasan ini sebagai adan bdan menggunakan FORlingkaran untuk mencetak semua angka di antara mereka.

DLosc
sumber

1

05AB1E , 14 byte

0)sƒ¤N+LÁ«}Ùs£

Cobalah online!

Emigna
sumber

1

R , 70 byte

function(e){for(i in 1:e)F=c(setdiff((F+i):1-1,F),F[1]+i,F);rev(F)[e]}

Cobalah online!

1-diindeks
-4 byte menggunakan F konstan berkat saran @JAD
-5 byte membalikkan daftar terima kasih atas saran @Giuseppe
-2 byte menghapus kawat gigi yang tidak berguna untuk loop berkat saran @JAD
-2 byte menggunakan setdiffsebagai gantinyax[x %in% y]

Versi sebelumnya (79 byte)

menggali semua
sumber

2

79 byte

JAD

@ JAD: Saya selalu lupa menggunakan F / T ... Saya tidak bisa menahannya, saya terlalu cenderung untuk menghindari "kode tidak aman": D

digEmAll

1

Membuat daftar secara terbalik menghemat 5 bytesdan menyebabkan banyak peringatan!

Giuseppe

Ini bahkan tidak aman jika F/Ttidak didefinisikan ulang pada definisi fungsi. Itu tidak (IIRC) mengubah nilai global untukF/T

JAD

1

72 byte

JAD

1

Python 2 , 123 byte

def f(z):[s.extend([s[-1]+n]+[x for x in range(s[-1]+1,s[-1]+n)if not x in s]) for n in range(1,z)if len(s)<z];return s

Cobalah online!

Diberikan input x, output x syarat pertama dari urutan,

Saya belajar Python dan tantangan ini membuat segalanya lebih menarik.

Sunting: mencukur spasi

Cog Sedang
sumber

Selamat datang di PPCG! Anda dapat menyingkirkan beberapa ruang lebih banyak di for n in range(1,z) if len(s) < z]; return s: for n in range(1,z)if len(s)<z];return s.

Laikoni

0

Jelly , 16 byte

RÄṬŻk²Ḋ$ṙ€-Ø.;Fḣ

Cobalah online!

Satu byte lebih lama dari jawaban Jelly yang sudah ada tetapi ini mungkin bisa sedikit golf. RÄṬŻk²Ḋ$mungkin bisa lebih pendek.

RÄṬŻk²Ḋ$‘ṙ€1FŻŻỤ’ḣ

Lebih lama tetapi berbeda.

dylnan
sumber

0

Ruby , 63 byte

->x,n=0{n+=1while 0>d=n*n+n<=>2*x-6;[0,1,3,2][x]||[x+n,x-1][d]}

Cobalah online!

Diindeks 0. Mungkin bisa bermain golf.

Pasang kembali Monica - notmaynard
sumber

0

Perl 6 , 52 byte

(0,{((^max @_)∖@_).min.?key//(1+@_[*-1]+$++)}...*)

Cobalah online!

Ini adalah ekspresi generator menggunakan ...operator. Ia mencari celah dalam urutan sebelumnya @_melalui ((^max @_)∖@_).min.?key:

      @_  # prior sequence values         [0,1,3]
  max @_  # largest prior sequence value       3
 ^        # the Range 0..max @_            0,1,2
(       )∖@_  # set subtract prior seq     -0,1  -> (2=>True)
            .min  # smallest unseen value  2=>True
                .?key  # set yields pairs  2

The ?diperlukan untuk nilai awal yang tidak memiliki .key. Jika tidak ada celah yang ditemukan, maka ia menambahkan n (di sini dalam $variabel) ke nilai terakhir dalam daftar, ditambah satu untuk mati oleh 0 kesalahan.

Phil H
sumber

0

Python 3 , 104 byte

def f(x):
 n=a=0
 l=list(range(x*x))
 while n<x:print(l[a+n],*l[a+2-(n<3):a+n],end=' ');a=a+n-(a>0);n+=1

Cobalah online!

Diberikan input x, output x "urutan" pertama

frosqh
sumber