Número esperado de ceros finales
Entrada
Un límite m <= 4294967295.
Salida
Considere valores muestreados uniformemente al azar a partir de números enteros en el rango de 0 am, inclusive.
Su salida debe ser el número esperado (promedio) de ceros finales en la representación binaria del valor muestreado. Su respuesta debe ser exacta, por ejemplo, expresada como fracción.
Ejemplo
- m = 0. La respuesta es 1. Se muestreará 0 con el problema 1.
- m = 1. La respuesta es 1/2. 0 con problema 1/2 y 1 con problema 1/2.
- m = 2. La respuesta es 2/3. 0 y 2 tienen un cero final.
- m = 3. La respuesta es 1/2. 0 y 2 tienen un cero final.
Respuestas
Python , 36 bytes
lambda m:(m+1-bin(m).count('1'),m+1)
¡Pruébelo en línea!
¡Una fórmula!
$$ 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 bytes
{1+⍵,+/⌊⍵÷2*⍳32}
¡Pruébelo en línea!
\$\frac{1+\sum_{i=1}^{32}\left\lfloor\frac{m}{2^i}\right\rfloor}{1+m}\$. devuelve denominador, numerador. utiliza ⎕io=1.
MATL , 14 bytes
:B!P&X>qtswnhQ
El código usa fuerza bruta: calcula la expansión binaria de todos los números en el rango especificado y cuenta los ceros finales.
La salida es numerador, luego denominador.
¡Pruébelo en línea! . También puede ver los primeros resultados o trazarlos para ver algunas tendencias interesantes (más sobre esto a continuación).
Como funciona el codigo
: % 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
Algunas propiedades interesantes de la secuencia
Deje \$a(m)\$denotar la secuencia. Luego
- \$a(m) = m/(m+1)\$cuando \$m\$es un poder de \$2\$.
- Si \$m\$es un poder de \$2\$, \$a(n) < a(m)\$para todos \$n\ < 2m, n \neq m\$.
- \$\lim\sup_{m \rightarrow \infty} a(m) = 1\$.
Prueba de 1
Deje \$m\$ser un poder de \$2\$. Considere el conjunto \$\{1,2,\ldots,m\}\$. En este conjunto, \$m/2\$los miembros son múltiplos de \$2\$, y por lo tanto tienen al este un cero final. \$m/4\$los miembros son múltiplos de \$4\$y contribuir con un cero final adicional, etc. Solo hay un múltiplo de \$m\$. Entonces el número total de ceros finales es \$m/2 + m/4 + \cdots + 1 = m-1\$, y la fracción de ceros finales en el conjunto \$\{1,2,\ldots,m\}\$es \$(m-1)/m\$. Por lo tanto en el conjunto \$\{0,1,2,\ldots,m\}\$es \$m/(m+1)\$.
Prueba de 2
La demostración usa inducción matemática.
Para \$m=2\$ la propiedad reclamada se mantiene.
Deje \$m\$ser un poder arbitrario de \$2\$. Suponga que la propiedad se cumple para \$m/2\$. Combinado con la propiedad 1 esto implica que, para todo \$k<m\$, \$a(k) \leq a(m/2) = m/(m+2) < m/(m+1)\$.
Considere los números \$m+1, m+2, \ldots, 2m-1\$. Sus ceros finales son los mismos que los de \$1, 2, \ldots, m-1\$respectivamente (las expansiones binarias solo difieren en una cadena inicial formada por un uno y algunos ceros, lo que no afecta). Para \$k<m\$, usando la propiedad 1 nuevamente el término \$a(m+k)\$se puede expresar como \$(m+j)/(m+1+k)\$, donde \$j\$es el número total de ceros finales en \$\{m+1,\ldots,m+k\}\$, o equivalentemente en \$\{1,\ldots,k\}\$. Desde \$a(k) = j/k < m/(m+1)\$, sostiene que \$(m+j)/(m+1+k) < m/(m+1)\$.
Por lo tanto, la propiedad se satisface por \$m\$.
Prueba de 3
De las provincias 1 y 2, \$\lim\sup_{n \rightarrow \infty} a(n) = \lim_{m \rightarrow \infty} m/(m+1) = 1\$.
K (ngn / k) , 13 12 bytes
{1+x,x-/2\x}
¡Pruébelo en línea!
como el de xnor
{ } función con argumento x
2\ dígitos binarios
x-/reducción con menos, utilizando xcomo valor inicial
x, anteponer x
1+ agregue 1 a ambos en el par
J , 13 12 10 bytes
1-+/@#:%>:
¡Pruébelo en línea!
-12 bytes gracias a la forumula de xnor
-2 bytes gracias a la idea de Bubbler de hacer que la entrada sea más precisa en lugar de convertir dentro de mi verbo
cómo
Uno menos 1-la suma de +/@la representación binaria de la entrada #:dividida por %la entrada más uno >:.
original
J , 24 bytes
(,1#.i.&1@|.@#:"0@i.)@>:
¡Pruébelo en línea!
Salidas como (denominador, numerador)
APL (Dyalog Extended) , 9 bytes
-\1∘+,1⊥⊤
¡Pruébelo en línea!
Sin embargo, otro puerto de la respuesta de Python de xnor . Una función tácita que toma ny devuelve (denom, num).
Cómo funciona
-\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 bytes
Emite la fracción como [numerator, denominator].
n=>[(g=k=>k?g(k&k-1)-1:++n)(n),n]
¡Pruébelo en línea!
La fórmula recursiva para el numerador se derivó inicialmente de A101925 , que a su vez se define como A005187 (n) + 1:
(g=n=>n&&g(n>>1)+n)(n)-n+1
Una vez que se juega al golf un poco más, resulta ser equivalente a la fórmula de @ xnor .
05AB1E , 7 bytes
!Ò2¢s‚>
¡Pruébelo en línea!
El número de ceros finales es el mismo que la multiplicidad de \$2\$en la factorización prima (para \$n \ne 0\$). Esto significa que solo necesitamos contar el número de veces \$2\$divide \$m!\$.
! factorial
Ò prime factorization
2¢ count 2's
s‚ swap and pair (with input)
> increment both
Si la salida [denominator, numerator]está bien, !Ò2¢‚>funciona a 6 bytes.
05AB1E , 8 bytes
Una implementación de la fórmula de xnor .
b1¢(0‚>+
¡Pruébelo en línea!
Puede haber una forma más corta de contar los bits establecidos que 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 bytes
lambda m:(sum(bin(i+1)[:1:-1].find('1')for i in range(m))+1,m+1)
¡Pruébelo en línea!
Devuelve la fracción como tupla (denominator, numerator).
Wolfram Language (Mathematica) , 26 bytes
1-DigitCount[#,2,1]/(#+1)&
¡Pruébelo en línea!
Pyth , 12 bytes
,KhQ-K/.BQ"1
¡Pruébelo en línea!
Explicación:
, // 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
Salidas [denominator, numerator]
> <> , 37 bytes
1&l:{:})?\:2%0=?v&!
;n,+1{&/,2&+1&<
¡Pruébelo en línea!
No hay incorporados para lidiar con representaciones binarias, por lo que %es necesario un costoso bucle de modulación.
Un truco que se usa aquí es simplemente dejar que la pila crezca, ya que eso hace que un contador esté disponible instantáneamente con un solo lcomando.
PHP , 44 bytes
fn($m)=>[$m-substr_count(decbin($m++),1),$m]
¡Pruébelo en línea!
Es la fórmula de @ xnor con una pequeña optimización.
Gelatina , 6 bytes
BS’ạ,‘
A Enlace monádico aceptar un número entero que proporciona un par de enteros, [numerator, denominator].
¡Pruébelo en línea! O ver 0-40 inclusive .
O, también para 6:
!Ḥọ2,‘
código de máquina x86_64, 15 bytes
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
Entrada: men rdi, salida: [ rsi, rdi ]. Trabaja por valores m <= 4294967295.
¡Pruébelo en línea!
O versión original de 16 bits ...
código de máquina x86-16, 19 17 bytes
Binario:
00000000: 8bd0 33db d1e8 7301 4375 f942 8bc2 2bc3 ..3...s.Cu.B..+.
00000010: c3 .
Listado:
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
Función invocable, entrada men AXsalida [ AX, DX ]. Funciona por valores m <= 65534(plataforma max int).
Salida del programa de prueba:
Cáscara , 6 bytes
A:1↑İr
¡Pruébelo en línea! Esta función solo toma el promedio del inicio de la secuencia de la regla .
Python 3 , 76 bytes
lambda m:(sum(len(bin(i))-len(bin(i).strip("0"))-1 for i in range(m+1)),m+1)
La fracción se devuelve como una tupla (numerator,denominator)
Versión sin 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)
¡Pruébelo en línea!
Carbón , 11 bytes
Ｉ⟦⁻⊕θΣ⍘Ｎ²⊕θ
¡Pruébelo en línea! El enlace corresponde a la versión detallada del código. Puerto de la respuesta de Python de @ xnor. Explicación:
θ 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 bytes
method(I,list(I-I toBase(2)occurancesOfSeq("1")+1,I+1))
¡Pruébelo en línea!
Java 8, 27 bytes
n->-n.bitCount(n++)+n+"/"+n
Puerto de la respuesta de Python de @xnor , ¡así que asegúrese de votarlo también!
Pruébelo en línea.
Explicación:
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 bytes
âΣ~bα⌠+
Puerto de la respuesta de Python de @xnor , ¡así que asegúrese de votarlo también!
Pruébelo en línea.
Explicación:
â # 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 bytes
Guardado 3 bytes gracias a Mukundan314 !!!
f(int*m,int*n){*n=++*m-__builtin_popcount(*m-1);}
¡Pruébelo en línea!
Puerto de la respuesta de Python de xnor .
Japonés , 10 bytes
Adaptado de la solución de xnor . La entrada es una matriz de un solo entero, la salida es [numerator, denominator].
ËÒ-¤è1Ãp°U
Intentalo