OEIS memiliki variasi (A111439) pada urutan Golomb . Seperti dalam urutan Golomb, A(n)jelaskan seberapa sering nmuncul dalam urutan. Tetapi di samping itu, tidak ada dua angka yang berurutan yang identik. Saat membangun urutan, A(n)selalu dipilih sebagai bilangan bulat positif terkecil yang tidak melanggar dua properti ini. Karena nomor identik yang tidak diizinkan berturut-turut, seri bergetar sedikit naik dan turun saat tumbuh. Inilah 100 istilah pertama:

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 8, 9, 
10, 9, 10, 9, 10, 11, 10, 11, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 12, 
13, 12, 13, 12, 13, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 16, 15, 
16, 17, 16, 17, 16, 17, 16, 17, 16, 17, 18, 17, 18, 17, 18, 19, 18, 19, 18, 
19, 18, 19, 18, 19, 18, 19, 20, 19, 20, 21, 20, 21, 20, 21, 20, 21, 20

Daftar lengkap angka 10.000 pertama dapat ditemukan di OEIS .

Tantangannya adalah untuk menulis program atau fungsi yang menghitung A(n), diberikan n. nadalah 1berbasis untuk memastikan bahwa properti self-describing bekerja.

Aturan

Anda dapat menulis sebuah program atau fungsi dan menggunakan salah satu metode standar kami untuk menerima input dan memberikan output.

Anda dapat menggunakan bahasa pemrograman apa pun , tetapi perhatikan bahwa celah ini dilarang secara default.

Ini adalah kode-golf , sehingga jawaban terpendek yang valid - diukur dalam byte - menang.

Uji Kasus

n     A(n)
1     1
4     2
10    6
26    10
100   20
1000  86
1257  100
10000 358

Haskell , 67 byte

f k|k<4=k|p<-k-1=[n|n<-[1..],n/=f p,sum[1|a<-[1..p],f a==n]<f n]!!0

Menentukan fungsi f. Cobalah online!Sangat lambat, f 15waktu komputasi keluar pada TIO.

Penjelasan

Sesuai dengan definisi: pada setiap tahap, pilih angka positif minimal nyang memenuhi batasan (tidak sama dengan entri sebelumnya, dan belum terjadi f nkali).

f k             -- Define f k:
 |k<4=k         -- If k < 4, it's k.
 |p<-k-1=       -- Otherwise, bind k-1 to p,
  [n|           -- compute the list of numbers n where
   n<-[1..],    -- n is drawn from [1,2,3,...],
   n/=f p,      -- n is not equal to f p, and
   sum[1|       -- the number of
    a<-[1..p],  -- those elements of [1,2,3,...,p]
    f a==n]     -- whose f-image equals n
   <f n]        -- is less than f n,
  !!0           -- and take the first element of that list.

Mathematica, 69 68 byte

Terima kasih kepada Martin Ender karena menemukan ekstra –1 byte untuk saya!

Last@Nest[{##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&,{},#]&

Fungsi tanpa nama mengambil integer positif nsebagai input dan mengembalikan integer positif. Kami membangun seluruh daftar nelemen pertama dari urutan ini, lalu mengambil Lastelemen tersebut. Daftar ini dibangun dengan memulai dengan daftar kosong {}dan mengoperasikannya dengan fungsi nkali berturut-turut (viaNest ).

Fungsi yang dimaksud adalah {##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&, yang mengambil daftar sebagian dari nilai urutan (pada dasarnya ##&@@#) dan menambahkan nilai berikutnya. Nilai berikutnya dihitung dengan memulai dengan x=1, kemudian berulang kali mengganti xdengan x+1selama kondisi x==Last@#||#~Count~x==#[[x]]terpenuhi-kata lain, jika salah xadalah elemen sebelumnya, atau xsudah dalam daftar nomor yang benar kali. Fungsi ini meludah beberapa kesalahan, karena (misalnya) kita tidak boleh memanggil xelemen th dari daftar awal {}; Namun, semua nilainya benar.

Python 2, 99 86 byte

Terima kasih kepada @Dennis untuk beberapa peningkatan total sebesar 13 byte!

s=0,1,2,3
exec't=1\nwhile t==s[-1]or s.count(t)/s[t]:t+=1\ns+=t,;'*input()
print s[-4]

Program ini berlangsung dengan sangat naif: Program ini melacak daftar nilai yang telah ditentukan sejauh ini, dan terlihat menambahkan nilai berikutnya. Mencoba untuk menambahkan 1ke akhir daftar jika itu bisa; jika tidak, maka ia mencoba 2dan seterusnya sampai sesuatu diizinkan.

Sekarang, kita mulai dengan penyemaian hasil untuk 1,2,3menjadi 1,2,3. Hal ini dilakukan untuk menghindari masalah dengan daftar nilai yang sudah dihitung terlalu pendek: Saya menduga bahwa jika npaling tidak 4maka a(n)sangat kurang dari n. (Dalam program ini, s[n]sama dengan a(n). Daftar kami sebenarnya diinisialisasi [0,1,2,3]karena daftar 0-indexed dengan Python. Jadi misalnya a(1)=s[1]=1, dana(2)=s[2]=2 .)

Jadi, katakanlah kita sedang berusaha menentukan s[m], artinya daftar kami sudah termasuk s[0], s[1], ..., s[m-1]. Kami akan mulai t=1dan mencoba mengatur s[m]=1. Ketika itu tidak berhasil, kami pergi ke t=2dan mencoba untuk mengatur s[m]=2. Setiap kali kami menambah t, kami memeriksa apakah s.count(t)==s[t]... tetapi sisi kanan tidak akan menghasilkan kesalahan selama kami tidak pernah harus mencapai setinggi t=m. Dugaan tersebut mengatakan bahwa kita tidak perlu melakukannya, karena nilai pertama yang kita hitung sebenarnya s[4].

Implementasi ini menghitung 3 nilai lebih dari urutan daripada yang dibutuhkan. Sebagai contoh jika nadalah 8, itu akan menghitung melalui s[11]sebelum mengembalikan nilai s[8].

Saya akan senang melihat bukti dugaan itu. Saya percaya itu bisa dibuktikan dengan induksi (kuat?).

Sunting: Ini adalah bukti dugaan tersebut . Kami benar-benar membuktikan bentuk pernyataan yang sedikit lebih kuat, karena tidak melibatkan pekerjaan tambahan.

Teorema: Untuk semua yang nlebih besar dari atau sama dengan 4, istilahnya a(n)kurang dari atau sama dengan (n-2).

Bukti (dengan Induksi Kuat): (Basis n=4): Pernyataan ini berlaku untuk n=4, sejak a(4) = 2 = 4-2.

Sekarang asumsi a(k)kurang dari atau sama dengan k-2untuk semua kdari 4mulai n, inklusif (dan anggap nsetidaknya 4). Secara khusus, ini berarti bahwa semua ketentuan urutan sebelumnya paling banyak (n-2). Kita perlu menunjukkan itu a(n+1)paling banyak (n-1). Sekarang, menurut definisi, a(n)adalah bilangan bulat positif terkecil yang tidak melanggar kondisi apa pun, jadi kita hanya perlu menunjukkan bahwa nilainya (n-1)tidak akan melanggar salah satu kondisi.

Nilai (n-1)tidak akan melanggar kondisi "tanpa pengulangan berurutan", karena dengan hipotesis induksi entri sebelumnya paling banyak (n-2). Dan itu tidak akan melanggar kondisi " a(m)adalah berapa kali mmuncul", kecuali (n-1)sudah tercapai a(n-1)kali. Tetapi dengan asumsi induksi yang kuat, (n-1)sebelumnya telah mencapai 0waktu, dan a(n-1)tidak sama dengan 0karena a(m)positif untuk semua m.

Karena a(n+1)itu kurang dari atau sama dengan n-1 = (n+1)-2, seperti yang diinginkan. QED.

Jelly , 17 byte

Ṭ€S<;1Tḟ®Ḣ©ṭ
⁸Ç¡Ṫ

Tiga kasus tes terakhir terlalu banyak untuk TIO. Saya telah memverifikasi 1000 dan 1257 secara lokal.

Cobalah online! atau verifikasi 100 syarat pertama .

Bagaimana itu bekerja

⁸Ç¡Ṫ          Main link. No arguments.

⁸             Yield [].
 Ç¡           Execute the helper link n times (where n is an integer read from
              STDIN), initially with argument [], then with the previous return
              value as argument. Yield the last return value.
              Tail; yield the last element of the result.


Ṭ€S<;1Tḟ®Ḣ©ṭ  Helper link. Argument: A (array)

Ṭ€            Untruth each convert each k into an array of k-1 zeroes and one 1.
  S           Sum; column-wise reduce by +, counting the occurrences of all
              between 1 and max(A).
   <          Compare the count of k with A[k] (1-indexed), yielding 1 for all
              integers that still have to appear once or more times.
    ;1        Append a 1 (needed in case the previous result is all zeroes).
      T       Truth; find all indices of ones.
       ḟ®     Filter-false register; remove the value of the register (initially 0)
              from the previous result.
         Ḣ©   Head copy; yield the first (smallest) value of the result and save
              it in the register.
           ṭ  Tack; append the result to A.

Python 2 , 77 74 byte

f=lambda n,k=1:n*(n<4)or map(f,range(n)+k*[n-1]).count(k)<f(k)or-~f(n,k+1)

Ini adalah implementasi algoritma @ mathmandan secara rekursif .

Implementasinya adalah O (gila) : input 9 membutuhkan 2 detik secara lokal, input 10 52 detik, dan input 11 17 menit dan 28 detik. Namun, jika dinyatakan sebagai fungsi reguler daripada lambda, memoisasi dapat digunakan untuk memverifikasi kasus uji.

Cobalah online!

Perhatikan bahwa bahkan dengan memoisasi, TIO tidak dapat menghitung f (1257) atau f (10000) (keduanya diverifikasi secara lokal).

05AB1E , 32 31 byte

XˆXˆG[N¯2(è<›¯¤NÊsN¢¯Nè‹&&#]N.ˆ

Cobalah online!

Penjelasan

XˆXˆ                             # initialize global list as [1,1]
    G                            # input-1 times do:
     [                    #]     # loop until expression is true     
      N¯2(è<›                    # n > list[-2]-1
             ¯¤NÊ                # list[-1] != N
                 sN¢¯Nè‹         # count(list, N) < list[N]
                        &&       # logical AND of the 3 expressions
                            N.ˆ  # add N to global list 
                                   and output last value in list and end of program

Secara teknis kami berada di loop Gketika kami menambahkan N ke daftar global, tetapi semua loop di 05AB1E menggunakan variabel N yang sama dengan indeks, sehingga loop batin [...]telah menimpa N dari Gmakna yang kami dapat menambahkannya di luar loop.

Masalah dengan loop dan kondisi bersarang mencegah kita dari melakukan ini di dalam loop.

Befunge, 141 136 byte

<v9\0:p8\2:*2:-1<9
v>p1+:3\8p0\9p:#^_&
>1-:#v_1.@>$8g.@
*+2%\>1-:!|>$!:::9g!\!9g!*\:8g\!8g`
9\+1g9::< \|`g9\g8+2::p
g2+\8p2+^:<>:0\9p::8

Cobalah online!

Karena keterbatasan memori Befunge, tidak praktis untuk melacak semua entri entri sebelumnya dalam urutan, sehingga solusi ini menggunakan algoritma dengan jejak memori yang lebih rendah yang menghitung nilai lebih langsung.

Yang mengatakan, kita masih dibatasi oleh ukuran sel, yang dalam penerjemah referensi Befunge-93 adalah nilai 8-bit yang ditandatangani, sehingga angka genap tertinggi yang didukung dalam urutannya adalah A(1876) = 126, dan angka ganjil yang didukung tertinggi adalah A(1915) = 127.

Jika Anda ingin menguji nilai yang lebih besar, Anda harus menggunakan juru bahasa dengan ukuran sel yang lebih besar. Itu harus mencakup sebagian besar implementasi Befunge-98 ( Coba online! ).

Python 2, 117 byte

Ah. Tidak sesingkat itu. Solusi berulang sederhana.

L=[1,2,3]
n=input()
while len(L)<n:
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:L+=[i];break
print L[n-1]

Cobalah online

Berikut adalah upaya yang sangat buruk pada solusi rekursif (129 byte):

def f(n,L=[1,2,3]):
 if len(L)>=n:print L[n-1];exit(0)
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:f(n,L+[i])
 f(n,L)