Jumlah yang diharapkan dari nol di belakang
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
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}$$
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
.
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
- \$a(m) = m/(m+1)\$kapan \$m\$adalah kekuatan dari \$2\$.
- Jika \$m\$adalah kekuatan dari \$2\$, \$a(n) < a(m)\$untuk semua \$n\ < 2m, n \neq m\$.
- \$\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\$.
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 x
sebagai nilai awal
x,
prepend x
1+
tambahkan 1 ke keduanya pada pasangan
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)
APL (Dyalog Extended) , 9 byte
-\1∘+,1⊥⊤
Cobalah secara online!
Namun port lain dari jawaban Python xnor . Fungsi diam-diam yang mengambil n
dan 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)
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 .
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
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)
.
Bahasa Wolfram (Mathematica) , 26 byte
1-DigitCount[#,2,1]/(#+1)&
Cobalah secara online!
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]
> <> , 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 l
perintah.
PHP , 44 byte
fn($m)=>[$m-substr_count(decbin($m++),1),$m]
Cobalah secara online!
Ini rumus @ xnor dengan sedikit pengoptimalan.
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,‘
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: m
di 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 m
dalam AX
keluaran [ AX, DX ]
. Berfungsi untuk nilai m <= 65534
(platform max int).
Keluaran program uji:

Husk , 6 byte
A:1↑İr
Cobalah secara online! Fungsi ini hanya mengambil rata-rata awal urutan penggaris .
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!
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
Io , 55 byte
method(I,list(I-I toBase(2)occurancesOfSeq("1")+1,I+1))
Cobalah secara online!
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`
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)
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 .
Japt , 10 byte
Diadaptasi dari solusi xnor . Input adalah array integer tunggal, outputnya adalah [numerator, denominator]
.
ËÒ-¤è1Ãp°U
Cobalah