Numero previsto di zeri finali
Ingresso
A legato m <= 4294967295.
Produzione
Considera i valori campionati in modo uniforme e casuale da numeri interi compresi tra 0 e m, inclusi.
Il tuo output dovrebbe essere il numero previsto (medio) di zeri finali nella rappresentazione binaria del valore campionato. La tua risposta dovrebbe essere esatta, ad esempio data come frazione.
Esempio
- m = 0. La risposta è 1. 0 verrà campionato con prob 1.
- m = 1. La risposta è 1/2. 0 con prob 1/2 e 1 con prob 1/2.
- m = 2. La risposta è 2/3. 0 e 2 hanno uno zero finale.
- m = 3. La risposta è 1/2. 0 e 2 hanno uno zero finale.
Risposte
Python , 36 byte
lambda m:(m+1-bin(m).count('1'),m+1)
Provalo online!
Una 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}
Provalo online!
\$\frac{1+\sum_{i=1}^{32}\left\lfloor\frac{m}{2^i}\right\rfloor}{1+m}\$. restituisce denominatore, numeratore. usi ⎕io=1.
MATL , 14 byte
:B!P&X>qtswnhQ
Il codice utilizza la forza bruta: calcola l'espansione binaria di tutti i numeri nell'intervallo specificato e conta gli zeri finali.
L'output è numeratore, quindi denominatore.
Provalo online! . Puoi anche vedere i primi output o tracciarli per vedere alcune tendenze interessanti (più su questo di seguito).
Come funziona il codice
: % 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
Alcune proprietà interessanti della sequenza
Let \$a(m)\$denota la sequenza. Poi
- \$a(m) = m/(m+1)\$quando \$m\$è un potere di \$2\$.
- Se \$m\$è un potere di \$2\$, \$a(n) < a(m)\$per tutti \$n\ < 2m, n \neq m\$.
- \$\lim\sup_{m \rightarrow \infty} a(m) = 1\$.
Prova di 1
Let \$m\$essere un potere di \$2\$. Considera l'insieme \$\{1,2,\ldots,m\}\$. In questo set, \$m/2\$i membri sono multipli di \$2\$, e quindi hanno ad est uno zero finale. \$m/4\$i membri sono multipli di \$4\$e aggiungere un ulteriore zero finale, ecc. C'è solo un multiplo di \$m\$. Quindi il numero totale di zeri finali è \$m/2 + m/4 + \cdots + 1 = m-1\$e la frazione degli zeri finali nell'insieme \$\{1,2,\ldots,m\}\$è \$(m-1)/m\$. Pertanto nel set \$\{0,1,2,\ldots,m\}\$è \$m/(m+1)\$.
Prova di 2
La dimostrazione usa l'induzione matematica.
Per \$m=2\$ la proprietà rivendicata detiene.
Let \$m\$essere un potere arbitrario di \$2\$. Supponiamo che la proprietà valga per \$m/2\$. Combinato con la proprietà 1, ciò implica che, per tutti \$k<m\$, \$a(k) \leq a(m/2) = m/(m+2) < m/(m+1)\$.
Considera i numeri \$m+1, m+2, \ldots, 2m-1\$. I loro zeri finali sono gli stessi di \$1, 2, \ldots, m-1\$rispettivamente (le espansioni binarie differiscono solo per una stringa iniziale formata da uno e da alcuni zeri, il che non influisce). Per \$k<m\$, utilizzando nuovamente la proprietà 1 il termine \$a(m+k)\$può essere espresso come \$(m+j)/(m+1+k)\$, dove \$j\$è il numero totale di zeri finali in \$\{m+1,\ldots,m+k\}\$, o equivalentemente in \$\{1,\ldots,k\}\$. Poiché \$a(k) = j/k < m/(m+1)\$, mantiene che \$(m+j)/(m+1+k) < m/(m+1)\$.
Pertanto la proprietà è soddisfatta per \$m\$.
Prova di 3
Dalle proprietà 1 e 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}
Provalo online!
come quello di xnor
{ } funzione con argomento x
2\ cifre binarie
x-/riduzione con meno, utilizzando xcome valore iniziale
x, anteporre x
1+ aggiungi 1 a entrambi nella coppia
J , 13 12 10 byte
1-+/@#:%>:
Provalo online!
-12 byte grazie alla forumula di xnor
-2 byte grazie all'idea di Bubbler di rendere l'input con precisione estesa piuttosto che convertirlo all'interno del mio verbo
Come
Uno meno 1-la somma della +/@rappresentazione binaria dell'input #:diviso per %l'input più uno >:.
originale
J , 24 byte
(,1#.i.&1@|.@#:"0@i.)@>:
Provalo online!
Emette come (denominatore, numeratore)
APL (Dyalog Extended) , 9 byte
-\1∘+,1⊥⊤
Provalo online!
Ancora un altro port della risposta Python di xnor . Una funzione tacita che prende ne restituisce (denom, num).
Come funziona
-\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
Restituisce la frazione come [numerator, denominator].
n=>[(g=k=>k?g(k&k-1)-1:++n)(n),n]
Provalo online!
La formula ricorsiva per il numeratore è stata inizialmente derivata da A101925 , che a sua volta è definito come A005187 (n) + 1:
(g=n=>n&&g(n>>1)+n)(n)-n+1
Una volta giocato un po 'di più, risulta essere equivalente alla formula di @ xnor .
05AB1E , 7 byte
!Ò2¢s‚>
Provalo online!
Il numero di zeri finali è uguale alla molteplicità di \$2\$nella scomposizione in fattori primi (per \$n \ne 0\$). Ciò significa che dobbiamo solo contare il numero di volte \$2\$divide \$m!\$.
! factorial
Ò prime factorization
2¢ count 2's
s‚ swap and pair (with input)
> increment both
Se l'output [denominator, numerator]va bene, !Ò2¢‚>funziona a 6 byte.
05AB1E , 8 byte
Un'implementazione della formula di xnor .
b1¢(0‚>+
Provalo online!
Potrebbe esserci un modo più breve per contare i bit impostati rispetto a 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)
Provalo online!
Restituisce la frazione come tupla (denominator, numerator).
Wolfram Language (Mathematica) , 26 byte
1-DigitCount[#,2,1]/(#+1)&
Provalo online!
Pyth , 12 byte
,KhQ-K/.BQ"1
Provalo online!
Spiegazione:
, // 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
Uscite [denominator, numerator]
> <> , 37 byte
1&l:{:})?\:2%0=?v&!
;n,+1{&/,2&+1&<
Provalo online!
Nessun built-in per gestire le rappresentazioni binarie, quindi %è necessario un costoso mod loop.
Un trucco usato qui è quello di far crescere lo stack, poiché ciò rende immediatamente disponibile un contatore con un solo lcomando.
PHP , 44 byte
fn($m)=>[$m-substr_count(decbin($m++),1),$m]
Provalo online!
È la formula di @ xnor con una piccola ottimizzazione.
Gelatina , 6 byte
BS’ạ,‘
Un collegamento monadica accettare un numero intero che produce una coppia di numeri interi, [numerator, denominator].
Provalo online! Oppure vedi 0-40 inclusi .
Oppure, anche per 6:
!Ḥọ2,‘
x86_64 codice macchina, 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
Ingresso: ma rdi, uscita: [ rsi, rdi ]. Funziona per i valori m <= 4294967295.
Provalo online!
O versione originale a 16 bit ...
codice macchina x86-16, 19 17 byte
Binario:
00000000: 8bd0 33db d1e8 7301 4375 f942 8bc2 2bc3 ..3...s.Cu.B..+.
00000010: c3 .
Inserzione:
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
Funzione richiamabile, input min AXoutput [ AX, DX ]. Funziona per i valori m <= 65534(platform max int).
Output del programma di test:
Buccia , 6 byte
A:1↑İr
Provalo online! Questa funzione prende solo la media dell'inizio della sequenza del righello .
Python 3 , 76 byte
lambda m:(sum(len(bin(i))-len(bin(i).strip("0"))-1 for i in range(m+1)),m+1)
La frazione viene restituita come una tupla (numerator,denominator)
Versione non golfistica:
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)
Provalo online!
Carbone di legna , 11 byte
Ｉ⟦⁻⊕θΣ⍘Ｎ²⊕θ
Provalo online! Il collegamento è alla versione dettagliata del codice. Port della risposta Python di @ xnor. Spiegazione:
θ Input `m` as a string
⊕ Cast to integer and increment
Ｎ 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
Ｉ Cast to string
Implicitly print on separate lines
Io , 55 byte
method(I,list(I-I toBase(2)occurancesOfSeq("1")+1,I+1))
Provalo online!
Java 8, 27 byte
n->-n.bitCount(n++)+n+"/"+n
Port della risposta Python di @xnor , quindi assicurati di votare anche lui!
Provalo online.
Spiegazione:
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 della risposta Python di @xnor , quindi assicurati di votare anche lui!
Provalo online.
Spiegazione:
â # 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
Salvati 3 byte grazie a Mukundan314 !!!
f(int*m,int*n){*n=++*m-__builtin_popcount(*m-1);}
Provalo online!
Porto di XNOR 's risposta Python .
Japt , 10 byte
Adattato dalla soluzione di xnor . L'input è un singolo array di numeri interi, l'output è [numerator, denominator].
ËÒ-¤è1Ãp°U
Provalo