Jumlah yang diharapkan dari nol di belakang

Aug 21 2020

Memasukkan

Sebuah m <= 4294967295.

Keluaran

Pertimbangkan nilai-nilai yang diambil sampelnya secara seragam secara acak dari bilangan bulat dalam rentang 0 hingga m, inklusif.

Keluaran Anda harus berupa jumlah (rata-rata) nol di belakang yang diharapkan dalam representasi biner dari nilai sampel. Jawaban Anda harus tepat, misalnya diberikan sebagai pecahan.

Contoh

  • m = 0. Jawabannya adalah 1. 0 akan disampel dengan prob 1.
  • m = 1. Jawabannya adalah 1/2. 0 dengan prob 1/2 dan 1 dengan prob 1/2.
  • m = 2. Jawabannya adalah 2/3. 0 dan 2 memiliki satu nol di belakangnya.
  • m = 3. Jawabannya 1/2. 0 dan 2 memiliki satu nol di belakangnya.

Jawaban

10 xnor Aug 21 2020 at 05:30

Python , 36 byte

lambda m:(m+1-bin(m).count('1'),m+1)

Cobalah secara online!

Formula!

$$ f(m) = 1 - \frac{\text{#ones in bin}(m)}{m+1} = \frac{m+1-\text{#ones in bin}(m)}{m+1}$$

5 ngn Aug 21 2020 at 05:23

APL (Dyalog Unicode) , 16 byte

{1+⍵,+/⌊⍵÷2*⍳32}

Cobalah secara online!

\$\frac{1+\sum_{i=1}^{32}\left\lfloor\frac{m}{2^i}\right\rfloor}{1+m}\$. mengembalikan penyebut, pembilang. penggunaan ⎕io=1.

5 LuisMendo Aug 21 2020 at 04:54

MATL , 14 byte

:B!P&X>qtswnhQ

Kode menggunakan brute force: menghitung ekspansi biner dari semua angka dalam kisaran yang ditentukan dan menghitung nol yang tertinggal.

Outputnya adalah pembilang, lalu penyebut.

Cobalah secara online! . Anda juga dapat melihat keluaran pertama , atau memplotnya untuk melihat beberapa tren yang menarik (lebih lanjut tentang ini di bawah).

Bagaimana kodenya bekerja

:    % Implicit input: m. Range [1 2 ... m]. Note that 0 is not included
B    % Convert to binary. Gives a matrix, with the binary expansion of each
     % number on a different row, left-padded with zeros if needed
!    % Transpose
P    % Flip vertically. Now each binary expansion if in a column, reversed
&X>  % Argmax of each column. This gives a vector with the position of the
     % first 1 (the last 1 in the non-reversed expansion) for each number
q    % Subtract 1, element-wise. This gives the number of trailing zeros
     % in the binary expansion of each number
t    % Duplicate
s    % Sum
w    % Swap
n    % Number of elements
h    % Concatenate both numbers horizontally
Q    % Add 1 to each number, to account for the fact that 0 has not been
     % considered. Implicit display

Beberapa properti urutan yang menarik

Biarkan \$a(m)\$menunjukkan urutannya. Kemudian

  1. \$a(m) = m/(m+1)\$kapan \$m\$adalah kekuatan dari \$2\$.
  2. Jika \$m\$adalah kekuatan dari \$2\$, \$a(n) < a(m)\$untuk semua \$n\ < 2m, n \neq m\$.
  3. \$\lim\sup_{m \rightarrow \infty} a(m) = 1\$.

Bukti 1

Biarkan \$m\$menjadi kekuatan dari \$2\$. Pertimbangkan set \$\{1,2,\ldots,m\}\$. Di set ini, \$m/2\$anggota adalah kelipatan dari \$2\$, dan dengan demikian di timur memiliki angka nol tertinggal. \$m/4\$anggota adalah kelipatan dari \$4\$, dan berkontribusi satu tambahan nol tambahan, dll. Hanya ada satu kelipatan \$m\$. Jadi jumlah total nol di belakang adalah \$m/2 + m/4 + \cdots + 1 = m-1\$, dan pecahan nol di belakang set \$\{1,2,\ldots,m\}\$adalah \$(m-1)/m\$. Oleh karena itu di set \$\{0,1,2,\ldots,m\}\$ini adalah \$m/(m+1)\$.

Bukti 2

Pembuktiannya menggunakan induksi matematis.

Untuk \$m=2\$ kepemilikan properti yang diklaim.

Biarkan \$m\$menjadi kekuatan sewenang-wenang dari \$2\$. Asumsikan bahwa properti memegang \$m/2\$. Dikombinasikan dengan properti 1 ini menyiratkan bahwa, untuk semua \$k<m\$, \$a(k) \leq a(m/2) = m/(m+2) < m/(m+1)\$.

Pertimbangkan angkanya \$m+1, m+2, \ldots, 2m-1\$. Nol di belakangnya sama dengan \$1, 2, \ldots, m-1\$masing-masing (ekspansi biner hanya berbeda dalam string terdepan yang dibentuk oleh satu dan beberapa nol, yang tidak mempengaruhi). Untuk \$k<m\$, menggunakan properti 1 lagi istilah \$a(m+k)\$dapat dinyatakan sebagai \$(m+j)/(m+1+k)\$, dimana \$j\$adalah jumlah total nol di belakang \$\{m+1,\ldots,m+k\}\$, atau setara di \$\{1,\ldots,k\}\$. Sejak \$a(k) = j/k < m/(m+1)\$, itu menyatakan bahwa \$(m+j)/(m+1+k) < m/(m+1)\$.

Oleh karena itu properti puas untuk \$m\$.

Bukti 3

Dari proerties 1 dan 2, \$\lim\sup_{n \rightarrow \infty} a(n) = \lim_{m \rightarrow \infty} m/(m+1) = 1\$.

4 ngn Aug 21 2020 at 06:07

K (ngn / k) , 13 12 byte

{1+x,x-/2\x}

Cobalah secara online!

seperti xnor

{ } berfungsi dengan argumen x

2\ digit biner

x-/reduksi dengan minus, gunakan xsebagai nilai awal

x, prepend x

1+ tambahkan 1 ke keduanya pada pasangan

4 Jonah Aug 21 2020 at 04:55

J , 13 12 10 byte

1-+/@#:%>:

Cobalah secara online!

-12 byte berkat forumula dari xnor

-2 byte berkat ide Bubbler untuk membuat input lebih presisi daripada mengubah kata kerja saya

bagaimana

Satu dikurangi 1-jumlah +/@representasi biner dari input #:dibagi dengan %input ditambah satu >:.

asli

J , 24 byte

(,1#.i.&1@|.@#:"0@i.)@>:

Cobalah secara online!

Dihasilkan sebagai (penyebut, pembilang)

4 Bubbler Aug 21 2020 at 07:49

APL (Dyalog Extended) , 9 byte

-\1∘+,1⊥⊤

Cobalah secara online!

Namun port lain dari jawaban Python xnor . Fungsi diam-diam yang mengambil ndan mengembalikan (denom, num).

Bagaimana itu bekerja

-\1∘+,1⊥⊤  ⍝ Input: n
      1⊥⊤  ⍝ Popcount(n)
  1∘+,     ⍝ Pair with n+1
-\         ⍝ Minus scan; convert (a,b) to (a,a-b)
3 Arnauld Aug 21 2020 at 04:32

JavaScript (ES6),  35  33 byte

Menghasilkan pecahan sebagai [numerator, denominator].

n=>[(g=k=>k?g(k&k-1)-1:++n)(n),n]

Cobalah secara online!

Rumus rekursif untuk pembilang awalnya diturunkan dari A101925 , yang dengan sendirinya didefinisikan sebagai A005187 (n) + 1:

(g=n=>n&&g(n>>1)+n)(n)-n+1

Sekali bermain golf lagi, ternyata sama dengan rumus @ xnor .

3 ovs Aug 21 2020 at 14:08

05AB1E , 7 byte

!Ò2¢s‚>

Cobalah secara online!

Jumlah nol di belakangnya sama dengan kelipatan \$2\$dalam faktorisasi prima (untuk \$n \ne 0\$). Artinya kita hanya perlu menghitung berapa kali \$2\$membagi \$m!\$.

!        factorial
 Ò       prime factorization
  2¢     count 2's
    s‚   swap and pair (with input)
      >  increment both

Jika keluaran [denominator, numerator]baik-baik saja, !Ò2¢‚>bekerja pada 6 byte.


05AB1E , 8 byte

Penerapan rumus xnor .

b1¢(0‚>+

Cobalah secara online!

Mungkin ada cara yang lebih singkat untuk menghitung bit set daripada b1¢.

          implicit input  m

b         to binary       bin(m)
 1¢       count 1's       bin(m).count('1')
   (      negative        -bin(m).count('1')
    0‚    pair with 0     [-bin(m).count('1'), 0]
      >   increment       [1-bin(m).count('1'), 1]
       +  add input       [m+1-bin(m).count('1'), m+1]

          implicit output
2 Noodle9 Aug 21 2020 at 05:17

Python 3 , 65 64 byte

lambda m:(sum(bin(i+1)[:1:-1].find('1')for i in range(m))+1,m+1)

Cobalah secara online!

Mengembalikan pecahan sebagai tupel (denominator, numerator).

2 J42161217 Aug 21 2020 at 04:59

Bahasa Wolfram (Mathematica) , 26 byte

1-DigitCount[#,2,1]/(#+1)&

Cobalah secara online!

2 Scott Aug 21 2020 at 06:50

Pyth , 12 byte

,KhQ-K/.BQ"1

Cobalah secara online!

Penjelasan:

,             // Print the following two evaluations as [X,Y]
 KhQ          // Denominator = input + 1 and store it in K
      /.BQ"1  // Convert input to binary and count 1's
    -K        // K(input + 1) - number of binary ones

Keluaran [denominator, numerator]

2 SE-stopfiringthegoodguys Aug 21 2020 at 14:53

> <> , 37 byte

1&l:{:})?\:2%0=?v&!
  ;n,+1{&/,2&+1&<

Cobalah secara online!

Tidak ada built-in untuk menangani representasi biner, jadi mod %loop yang mahal diperlukan.

Trik yang digunakan di sini adalah membiarkan tumpukan bertambah, karena itu membuat penghitung langsung tersedia hanya dengan satu lperintah.

2 640KB Aug 21 2020 at 20:45

PHP , 44 byte

fn($m)=>[$m-substr_count(decbin($m++),1),$m]

Cobalah secara online!

Ini rumus @ xnor dengan sedikit pengoptimalan.

2 JonathanAllan Aug 22 2020 at 05:28

Jelly , 6 byte

BS’ạ,‘

Tautan monadik yang menerima bilangan bulat yang menghasilkan sepasang bilangan bulat [numerator, denominator],.

Cobalah secara online! Atau lihat 0-40 inklusif .


Atau, juga untuk 6 orang:

!Ḥọ2,‘
2 640KB Aug 21 2020 at 21:32

kode mesin x86_64, 15 byte

f3 48 0f b8 c7    popcnt rax,rdi    # rax = number of 1's in m
48 ff c7          inc    rdi        # increment denominator
48 89 fe          mov    rsi,rdi    # rsi = rdi (m + 1)
48 29 c6          sub    rsi,rax    # rsi = rsi (m + 1) - rax (popcount of m)
c3                ret

Input: mdi rdi, keluaran: [ rsi, rdi ]. Bekerja untuk nilai-nilai m <= 4294967295.

Cobalah secara online!

Atau versi 16-bit asli ...

kode mesin x86-16, 19 17 byte

Biner:

00000000: 8bd0 33db d1e8 7301 4375 f942 8bc2 2bc3  ..3...s.Cu.B..+.
00000010: c3                                       .

Daftar:

8B D0       MOV  DX, AX         ; save m for denominator 
33 DB       XOR  BX, BX         ; BX is bit count of 1's 
        POP_COUNT: 
D1 E8       SHR  AX, 1          ; shift LSb into CF 
73 01       JNC  IS_ZERO        ; if a 0, don't increment count 
43          INC  BX             ; increment count of 1 bits
        IS_ZERO:
75 F9       JNZ  POP_COUNT      ; if AX not 0, keep looping 
42          INC  DX             ; increment denominator 
8B C2       MOV  AX, DX         ; AX = DX (m + 1)
2B C3       SUB  AX, BX         ; AX = AX (m + 1) - BX (popcount of m)
C3          RET

Fungsi yang dapat dipanggil, masukan mdalam AXkeluaran [ AX, DX ]. Berfungsi untuk nilai m <= 65534(platform max int).

Keluaran program uji:

2 LegionMammal978 Nov 01 2020 at 05:09

Husk , 6 byte

A:1↑İr

Cobalah secara online! Fungsi ini hanya mengambil rata-rata awal urutan penggaris .

1 aidan0626 Aug 21 2020 at 05:26

Python 3 , 76 byte

lambda m:(sum(len(bin(i))-len(bin(i).strip("0"))-1 for i in range(m+1)),m+1)

Pecahan dikembalikan sebagai tupel (numerator,denominator)

Versi non-golf:

def trailing_zeroes(m):
    #this is the running total for the total number of trailing zeroes
    total = 0
    #this loops through each the number in the range
    for i in range(m+1):
        #calculates number of trailing zeroes
        zeroes = len(bin(i))-len(bin(i).strip("0"))-1
        #adds the number of trailing zeroes to the running total
        total += zeroes
    #returns the numerator and the denominator as a tuple
    return (total, m+1)

Cobalah secara online!

1 Neil Aug 21 2020 at 07:30

Arang , 11 byte

I⟦⁻⊕θΣ⍘N²⊕θ

Cobalah secara online! Tautan adalah untuk verbose versi kode. Port jawaban Python @ xnor. Penjelasan:

    θ       Input `m` as a string
   ⊕        Cast to integer and increment
       N    Input `m` as an integer
      ⍘ ²   Convert to base 2 as a string
     Σ      Sum the digits
  ⁻         Subtract
          θ Input `m` as a string
         ⊕  Cast to integer and increment
 ⟦          Make into a list
I           Cast to string
            Implicitly print on separate lines
1 Noname Aug 21 2020 at 08:43

Io , 55 byte

method(I,list(I-I toBase(2)occurancesOfSeq("1")+1,I+1))

Cobalah secara online!

1 KevinCruijssen Aug 21 2020 at 15:11

Java 8, 27 byte

n->-n.bitCount(n++)+n+"/"+n

Port of @xnor 's Python jawaban , jadi pastikan untuk upvote dia juga!

Cobalah secara online.

Penjelasan:

n->                 // Method with Integer as parameter and String return-type
  -                 //  Take the negative value of:
   n.bitCount(n++)  //   The amount of 1-bits in integer `n`
                    //   (and increase `n` by 1 afterwards with `n++`)
    +n              //  And add (the now incremented) `n` to this
  +"/"              //  Append a "/" String
  +n                //  And append `n`
1 KevinCruijssen Aug 21 2020 at 15:23

MathGolf , 7 byte

âΣ~bα⌠+

Port of @xnor 's Python jawaban , jadi pastikan untuk upvote dia juga!

Cobalah secara online.

Penjelasan:

â        # Convert the (implicit) input-integer to a list of binary digits
 Σ       # Sum that list to get the amount of 1-bits
  ~      # Bitwise-NOT that (-n-1)
   b     # Push -1
    α    # Pair the two together
     ⌠   # Increment both values in the pair by 2
      +  # And add the (implicit) input-integer to both
         # (after which the entire stack joined together is output implicitly)
1 Noodle9 Aug 21 2020 at 06:06

C (gcc) , 52 49 byte

Disimpan 3 byte berkat Mukundan314 !!!

f(int*m,int*n){*n=++*m-__builtin_popcount(*m-1);}

Cobalah secara online!

Port of xnor 's Python jawaban .

Shaggy Aug 27 2020 at 04:58

Japt , 10 byte

Diadaptasi dari solusi xnor . Input adalah array integer tunggal, outputnya adalah [numerator, denominator].

ËÒ-¤è1Ãp°U

Cobalah