Belum Pasangan yang Tidak Digunakan

21

Mari kita tentukan urutan bilangan bulat positif. Kami akan menentukan urutan pada angka genap menjadi dua kali lipat dari istilah sebelumnya. Indeks ganjil dari urutan akan bilangan bulat positif terkecil yang belum muncul dalam urutan.

Berikut adalah istilah pasangan pertama.

1,2,3,6,4,8,5,10,7,14,9,18,11,22,12,24,13,26,15,30

Anda juga dapat menganggap ini sebagai daftar pasangan berpasangan (n, 2n) di mana n adalah bilangan bulat positif yang paling tidak terpakai sejauh ini.

Tugas

Diberi angka n sebagai input, hitung suku ke- n dalam urutan ini.

Ini adalah kode-golf sehingga Anda harus berusaha meminimalkan ukuran kode sumber Anda yang diukur dalam byte.

OEIS A036552

code-golf sequence Wisaya Gandum
sumber
Fakta bahwa indeks ganjil dari urutan akan bilangan bulat positif terkecil belum muncul dalam urutan. tidak relevan, kan?
Adám
1
Juga, pasangan apa ?
Adám
@ Adám Tidak, ini bukan masalahnya. Saya tidak yakin apa yang memberi Anda kesan itu mungkin saya telah mengatakan ini dengan buruk.
Wheat Wizard
1
@ Adám cara lain untuk memikirkan urutan adalah terdiri dari pasangan berpasangan (n,2n)dan setiap nomor hanya muncul sekali. Setiap pasangan dipilih untuk menjadi sekecil mungkin sambil mematuhi batasan yang terakhir.
Martin Ender
3
Penilaian 2-adic dari elemen-elemen aneh dari seri selalu sama. Mungkin bermanfaat bagi seseorang.
CalculatorFeline

Jawaban:

11

Haskell, 40 byte

l(a:r)=a:2*a:l[x|x<-r,x/=2*a]
(l[1..]!!)

Berbasis nol. lsecara bertahap membangun urutan dari daftar malas dari bilangan bulat yang tersisa.

Sievers Kristen
sumber
7

JavaScript (ES6), 92 82 69 67 65 byte

n=>(F=i=>i^n?F(a[b=i&1?2*b:(g=k=>a[k]?g(k+1):k)(1)]=-~i):b)(a={})

Bagaimana?

Kami melacak:

  • Nilai yang dimasukkan terakhir b .
  • Semua nilai yang sebelumnya ditemui dalam tabel pencarian a .

Secara internal, kami menggunakan indeks berbasis 0 i . Karena itu perilaku aneh dan genap terbalik:

  • Pada posisi ganjil, nilai selanjutnya adalah sederhana 2 * b.

  • Pada posisi genap, kami menggunakan fungsi rekursif g () dan tabel pencarian a untuk mengidentifikasi nilai pencocokan terkecil:

    (g = k => a[k] ? g(k + 1) : k)(1)

Untuk menyimpan beberapa byte, saya diinisialisasi {}daripada 0. Ini memaksa kami untuk menggunakan:

  • i^nuntuk membandingkan i dengan n karena ({}) ^ n === nsedangkan ({}) - nmengevaluasi ke NaN.
  • -~iuntuk menambah i , karena ({}) + 1akan menghasilkan string.

Demo

Tampilkan cuplikan kode

Arnauld
sumber
60 byte
Shaggy
5

Python 3 , 80 72 69 byte

-7 byte terima kasih kepada Tn. Xcoder !

f=lambda n:n and[f(n-1)*2,min({*range(n+1)}-{*map(f,range(n))})][n%2]

Cobalah online!

notjagan
sumber
1
Anda dapat mengganti set(...)dengan `{* ...} untuk 78 byte
Mr. Xcoder
@ Zacharý Apakah Anda merujuk komentar saya? Jika demikian, satu set dalam Python 3 bisa {*...}bukan set(...).
Tn. Xcoder
Saya berkomentar tanpa berpikir, saya menyadari beberapa saat kemudian bahwa {...for...in...}akan ada lebih banyak ucapan selamat tinggal.
Zacharý
Sebenarnya, ini akan menghemat 4 byte, karena Anda menggunakannya dua kali
Tn. Xcoder
69 byte (dan itu tidak digunakan Trueuntuk 1)
Wheat Wizard
3

Jelly , 15 byte

Jḟ⁸ḢðḤṭṭ
0Ç¡Ḋị@

Cobalah online!

fireflame241
sumber
3

Matematika , 56 53 byte

-3 byte terima kasih JungHwan Min !

(w={};Do[w~FreeQ~k&&(w=w~Join~{k,2k}),{k,#}];w[[#]])&

Cobalah online!

Berdasarkan ekspresi Mathematica yang diberikan dalam tautan OEIS.

notjagan
sumber
1
Juga 53 byte:Nest[k=0;If[#~FreeQ~++k,#~Join~{k,2k},#]&,{},#][[#]]&
JungHwan Min
3

PHP , 64 byte

for(;$argn-$i++;)if($i&$$e=1)for(;${$e=++$n};);else$e*=2;echo$e;

Cobalah online!

PHP , 77 byte

for(;$argn-$i++;$r[]=$e)if($i&1)for(;in_array($e=++$n,$r););else$e*=2;echo$e;

Cobalah online!

PHP , 78 byte

for(;$argn-$i++;)$e=$r[]=$i&1?end(array_diff(range($i,1),$r?:[])):2*$e;echo$e;

Cobalah online!

Jörg Hülsermann
sumber
3

PHP, 56 byte

while($$n=$i++<$argn)for($n*=2;$i&$$k&&$n=++$k;);echo$n;

PHP, 75 72 byte

for($a=range(1,$argn);$i++<$argn;)$a[~-$n=$i&1?min($a):2*$n]=INF;echo$n;

Cobalah online

Titus
sumber
3

05AB1E , 16 15 14 byte

1-diindeks.
Menggunakan fakta bahwa representasi biner elemen pada indeks ganjil dalam urutan berakhir dengan angka genap genap: A003159 .

Lʒb1¡`gÈ}€x¹<è

Cobalah online!

Penjelasan

L                 # range [1 ... input]
 ʒ      }         # filter, keep only elements whose
  b               # ... binary representation
   1¡             # ... split at 1's
     `gÈ          # ... ends in an even length run
         €x       # push a doubled copy of each element in place
           ¹<è    # get the element at index (input-1)
Emigna
sumber
3

Python 2 , 59 51 49 byte

f=lambda n,k=2:2/n%-3*(1-k)or f(n+~(k&-k)%-3,k+1)

Cobalah online!

Latar Belakang

Setiap bilangan bulat n positif dapat diekspresikan secara unik karena n = 2 o (n) c (n) , di mana c (n) ganjil.

Mari ⟨a n ⟩ n> 0 menjadi urutan dari tantangan spec.

Kami mengklaim bahwa, untuk semua bilangan bulat positif n , o (a 2n-1 ) adalah genap. Karena o (a 2n ) = o (2a 2n-1 ) = o (a 2n-1 ) + 1 , ini sama dengan mengklaim bahwa o (a 2n ) selalu ganjil.

Asumsikan klaim itu salah dan biarkan 2m-1 menjadi indeks ganjil pertama dari urutan sedemikian rupa sehingga o (a 2m-1 ) ganjil. Perhatikan bahwa ini menjadikan 2m menjadi indeks genap pertama dari urutan sedemikian rupa sehingga o (a 2m-1 ) adalah genap.

o (a 2m-1 ) aneh dan 0 bahkan, sehingga sebuah 2m-1 habis dibagi 2 . Menurut definisi, sebuah 2m-1 adalah terkecil bilangan bulat positif belum muncul di urutan , yang berarti bahwa sebuah 2m-1 /2 harus telah muncul sebelumnya. Biarkan k menjadi (pertama) indeks sebuah 2m-1 /2 di sebuah .

Karena o (a k ) = o (a 2m-1 /2) = o (a 2m-1 ) - 1 adalah genap, minimal n menyiratkan bahwa k adalah ganjil. Pada gilirannya, ini berarti bahwa sebuah k + 1 = 2a k = a 2m-1 , bertentangan dengan definisi sebuah 2m-1 .

Bagaimana itu bekerja

belum datang

Dennis
sumber
3

R , 70 69 65 byte

function(n){for(i in 2*1:n)F[i-1:0]=which(!1:n%in%F)[1]*1:2
F[n]}

Cobalah online!

Fungsi anonim yang mengambil satu argumen. Fdefault ke FALSEatau0 sehingga algoritma menilai dengan benar bahwa belum ada bilangan bulat positif dalam urutan.

Algoritma menghasilkan pasangan dalam forlingkaran dengan cara berikut (di mana ipergi dari 2ke 2nby 2):

           which(!1:n%in%l)[1]     # the missing value
                              *1:2 # keep one copy the same and double the next
l[i-1:0]=                         # store into l at the indices i-1 and i
Giuseppe
sumber
2

Haskell , 63 byte

g x=[2*g(x-1),[a|a<-[1..],a`notElem`map g[1..x-1]]!!0]!!mod x 2

Cobalah online!

Yang satu ini melecehkan evaluasi malas Haskell sepenuhnya.

Wisaya Gandum
sumber
2

Perl 6 , 50 byte

{(1,{@_%2??2*@_[*-1]!!first *∉@_,1..*}...*)[$_]}

Cobalah online!

  • 1, { ... } ... *adalah urutan tak terbatas malas yang dihasilkan di mana setiap istilah setelah yang pertama disediakan oleh blok kode yang dibatasi oleh brace. Karena blok referensi@_ array, ia menerima seluruh urutan saat ini dalam array itu.
  • Jika saat ini jumlah elemen ganjil ( @_ % 2), kita menghasilkan elemen bahkan-diindeks, sehingga elemen berikutnya adalah ganda elemen terakhir kami sejauh ini: 2 * @_[*-1].
  • Jika tidak, kita mendapatkan bilangan bulat positif pertama yang belum muncul dalam urutan: first * ∉ @_, 1..*.
  • $_adalah argumen untuk fungsi luar. Itu indeks ke dalam urutan yang tak terbatas, memberikan nilai pengembalian fungsi.
Sean
sumber
1

Mathematica, 82 byte

(s={};a=1;f=#;While[f>0,If[s~FreeQ~a,s~AppendTo~{a,2a}];a++;f--];Flatten[s][[#]])&

Cobalah online!

J42161217
sumber
58 byte di Mathematica (walaupun saya mungkin harus mengirim jawaban yang terpisah karena idenya sangat berbeda).
notjagan
Apakah Anda menyalinnya dari tautan OEIS?
J42161217
Saya memodifikasinya agar sesuai dengan tugas dan untuk golf lebih banyak, tetapi lebih atau kurang sama dengan tautan OEIS.
notjagan
1
@tidak memposting jawaban baru jika Anda mau dan
beri
1

k , 27 byte

*|{x,*(&^x?!y;|2*x)2!y}/!2+

1-diindeks. Cobalah online!

Menggunakan (!y)^xalih-alih &^x?!ybekerja juga.

zgrep
sumber
1

C # (Visual C # Interactive Compiler) , 82 byte

x=>{int y=1;for(var s="";x>2;x-=2)for(s+=2*y+":";s.Contains(++y+""););return x*y;}

Cobalah online!

-6 byte terima kasih kepada @ASCIIOnly!

dana
sumber
C # 8 mungkin terlalu baru untuk menjadi umum pada penerjemah online untuk saat ini, ditambahkan ke fakta bahwa csi adalah hal Mono sehingga Anda harus menunggu Mono untuk mengimplementasikannya dan menambahkannya ke bangunan yang stabil (jika tidak ada t sudah)
ASCII-satunya
sayangnya tidak mudah untuk memeriksa ini di C #
ASCII-satunya
Gunakan ini untuk memulai? Tapi ya, sepertinya bukan hal yang mudah. docs.microsoft.com/en-us/dotnet/api/…
dana
1
86? - jangan pikir :s diperlukan karena itu akan menjadi jumlah terbesar dalam daftar
ASCII-satunya
Juga 2.0=>2f
dana
0

Clojure, 102 byte

#(nth(loop[l[0 1 2 3]i %](if(= i 0)l(recur(conj l(*(last l)2)(nth(remove(set l)(range))0))(dec i))))%)

Iterasikan nwaktu untuk membangun urutan dan mengembalikan nitem ke-1, diindeks.

NikoNyrh
sumber
0

Ruby, 60 byte

->n,*a{eval"v+=1while a[v];a[v]=a[2*v]=v+v*n%=2;"*(n/2+v=1)}

Diindeks 0. Kami mengulang n/2+1kali, menghasilkan dua nilai setiap kali dan menyimpannya dengan mengisi array di indeks mereka. v+v*n%2memberikan output, baik vatau v*2tergantung pada paritas n.

histokrat
sumber
0

Ruby , 49 byte

->n{*s=t=0;s|[t+=1]==s||s<<t<<t*2until s[n];s[n]}

Mulailah dengan [0], tambahkan pasangan ke array sampai kita memiliki setidaknya n + 1 elemen, lalu ambil n + 1 (berbasis 1)

Cobalah online!

GB
sumber
0

JavaScript (ES6), 60 65 byte

Solusi berulang.

n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

Kurang golf

n=>{
  s = {}; //hashtable for used values
  for(i=0; n; )
  {
    if ( ! s[++i] )
    {
      s[i*2] = 1; // remember i*2 is already used
      if (--n)
        if (--n)
          0;
        else
          result = i*2;
      else
        result = i;
    }
  }
  return result;  
}

Uji

F=
n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

for (a=1; a < 50; a++)
  console.log(a,F(a))
Luaskan cuplikan

edc65
sumber
0

Jelly , 13 12 10 byte

ḤRọ2ḂĠZFị@

Ini menggunakan pengamatan dari jawaban Python saya .

Cobalah online!

Bagaimana itu bekerja

ḤRọ2ḂĠZFị@  Main link. Argument: n

Ḥ           Unhalve; yield 2n.
 R          Range; yield [1, ... , 2n].
  ọ2        Compute the order of 2 in the factorization of each k in [1, ..., 2n].
    Ḃ       Bit; compute the parity of each order.
     G      Group the indices [1, ..., 2n] by the corresponding values.
      Z     Zip/transpose the resulting 2D array, interleaving the indices of 0
            with the indices of 1, as a list of pairs.
       F    Flatten. This yields a prefix of the sequence.
        ị@  Take the item at index n.
Dennis
sumber