Angka Biner yang miring

15

Diberikan bilangan bulat n, menampilkan nangka biner miring pertama , 0 atau 1 diindeks. Mereka disebut ini karena bagaimana mereka dihasilkan:

Tulis angka dalam biner satu sama lain (dibenarkan-kanan):

........0
........1
.......10
.......11
......100
......101
......110
......111
.....1000
.........

Kemudian, Anda harus mengambil setiap diagonal dari kiri bawah ke kanan atas, sehingga setiap digit akhir adalah digit akhir dari diagonal. Inilah diagonal keempat (diindeks nol) yang ditandai dengan x's, yaitu 100:

........0
........1
.......10
.......11
......10x
......1x1
......x10
......111
.....1000
.........

Diagonal miring ke atas dalam urutan adalah:

0
11
110
101
100
1111
1010
.......

Kemudian, konversikan ke desimal, memberi 0, 3, 6, 5, 4, 15, 10, ...

OEIS A102370

Ini adalah kode-golf , jadi kode terpendek dalam byte menang.

code-golf sequence base-conversion binary mbomb007
sumber
12
Saya tidak berpikir spesifikasi ini sangat jelas. Saya harus melakukan banyak bacaan eksternal sebelum saya bisa mengerti apa yang ditanyakan di sini.
Post Rock Garf Hunter
1
Ini visualisasi, jika itu membantu. Baca "oval" dari atas ke bawah, dan di dalam oval dari kiri bawah ke kanan atas. Angka itu memberi Anda angka biner yang perlu dikonversi menjadi desimal.
Pavel
Apa maksud Anda, " baik 0 atau 1-diindeks "? Apakah maksud Anda bahwa seseorang dapat menampilkan angka pertama natau n+1angka pertama ?
sml
4
Saya pikir ini mungkin memungkinkan jawaban yang lebih menarik jika Anda hanya perlu mengembalikan nilai ke-n.
xnor
1
@ PatrickRoberts Saya tidak pernah membatasi berapa banyak yang akan dihasilkan. Saya hanya mengatakan "tulis angka dalam biner ...". Anda menghasilkan sebanyak yang Anda butuhkan.
mbomb007

Jawaban:

3

Jelly, 11 byte

ḤḶBUz0ŒDUḄḣ

Cobalah online!

Penjelasan

ḤḶBUz0ŒDUḄḣ    Main link. Argument: n
Ḥ              Double the argument. This ensures there are enough
               rows, since n + log2(n) <= 2n.
 Ḷ             Get range [0 .. 2n-1].
  B            Convert each number to binary.
   U           Reverse each list of digits. 
    z0         Transpose, padding with zeroes to a rectangle.
      ŒD       Get the diagonals of the rectangle, starting from the
               main diagonal. This gets the desired numbers, reversed,
               in binary, with some extras that'll get dropped.
        U      Reverse each diagonal.
         Ḅ     Convert each diagonal from binary to a number.
          ḣ    Take the first n numbers.

Transpos adalah cara paling sederhana untuk mengisi array agar diagonal-builtagon berfungsi. Kemudian pembalikan ditambahkan untuk mendapatkan semuanya dalam urutan yang benar.

PurkkaKoodari
sumber
Penerapan formula OEIS mungkin juga sangat singkat di Jelly.
Yytsi
@ TuukkaX Mungkin. Saya cukup lelah untuk menemukan memilih batas atas untuk jumlah yang sulit.
PurkkaKoodari
@ TuukkaX Saya mencobanya, tapi saya tidak melihat itu terjadi. Saya yakin Dennis & co akan mengimplementasikannya dalam 5 byte atau lebih.
PurkkaKoodari
Saat ini Anda beruntung ;)
geisterfurz007
7

JavaScript (ES6), 53 byte

n=>[...Array(n)].map(g=(j=1,i)=>j>i?0:j&i|g(j+j,i+1))

Diindeks 0. Tidak sering saya bisa menggunakan fungsi rekursif sebagai parameter map.

Neil
sumber
4

Mathematica, 46 byte

Plus@@@Table[BitAnd[n+k,2^k],{n,0,#},{k,0,n}]&

Fungsi yang tidak disebutkan namanya mengambil integer nonnegatif #sebagai input dan mengembalikan urutan 0-indeks hingga #istilah th. Membangun angka biner miring menggunakan BitAnd(bitwise "dan") dengan kekuatan 2 yang sesuai.

Greg Martin
sumber
2

Python3, 63 61 byte

lambda i:[sum(n+k&2**k for k in range(n+1))for n in range(i)]

Menggunakan formula dari OEIS.

-2 byte terima kasih kepada Luis Mendo ! i+1->i

Yytsi
sumber
Bisakah Anda menjelaskan bagaimana Anda beralih dari Sum_{ k >= 1 such that n + k == 0 mod 2^k } 2^kformula bitwise yang lebih sederhana itu?
smls
@smls Ini hanya menghitung diagonal ke atas secara langsung. Saya benar-benar berpikir itu lebih jelas daripada bentuk lainnya.
Neil
1

PHP, 68 byte

for(;$n++<$argv[1];print$s._)for($s=$i=0;$i<$n;)$s|=$n+$i-1&1<<$i++;

mengambil input dari argumen baris perintah, mencetak angka yang dipisahkan oleh garis bawah. Jalankan dengan -r.

Titus
sumber
1

MATL , 18 17 byte

:q"@tt:+5MW\~fWs+

Cobalah online!

Ini menggunakan rumus dari OEIS:

a(n) = n + Sum_{ k in [1 2... n] such that n + k == 0 mod 2^k } 2^k

Kode:

:q"     % For k in [0 1 2 ...n-1], where n is implicit input
  @     %   Push k
  tt    %   Push two copies
  :     %   Range [1 2 ... k]
  +     %   Add. Gives [n+1 n+2 ... n+k]
  5M    %   Push [1 2... k] again
  W     %   2 raised to that
  \     %   Modulo
  ~f    %   Indices of zero entries
  W     %   2 raised to that
  s     %   Sum of array
  +     %   Add
        % End implicitly. Display implicitly
Luis Mendo
sumber
0

Perl 6 , 59 43 byte

{map ->\n{n+sum map {2**$_ if 0==(n+$_)%(2**$_)},1..n},^$_}


{map {sum map {($_+$^k)+&2**$k},0..$_},^$_}

Menggunakan formula dari halaman OESIS.
Pembaruan: Beralih ke rumus bitwise-dan berbasis dari jawaban Python TuukkaX .

Perl 6 , 67 byte

{map {:2(flip [~] map {.base(2).flip.comb[$++]//""},$_..2*$_)},^$_}

Solusi naif.
Mengonversi angka yang merupakan bagian dari diagonal ke basis 2, mengambil digit yang benar dari masing-masing, dan mengubah hasilnya kembali ke basis 10.

seseorang
sumber
0

Jelly , 15 byte

2*ḍ+
ḶçЀḶUḄ+Ḷ’

Ini akan lebih pendek daripada jawaban Jelly lainnya jika kita harus mencetak hanya istilah ke- n .

Cobalah online!

Dennis
sumber
0

R, 66 byte

function(n,k=0:length(miscFuncs::bin(n-1)))sum(bitwAnd(k+n-1,2^k))

Fungsi tanpa nama yang menggunakan binfungsi dari miscFuncspaket untuk menghitung panjang yang ndirepresentasikan dalam biner dan kemudian menggunakan salah satu formula OEIS.

Billywob
sumber