뒤에 오는 0의 예상 개수
입력
경계 m <= 4294967295.
산출
0에서 m (포함) 범위의 정수에서 무작위로 균일하게 샘플링 된 값을 고려하십시오.
출력은 샘플링 된 값의 이진 표현에서 예상되는 (평균) 후행 제로 수 여야합니다. 답은 정확해야합니다 (예 : 분수로 제공).
예
- m = 0. 답은 1입니다. 0은 prob 1로 샘플링됩니다.
- m = 1. 답은 1/2입니다. 0은 prob 1/2이고 1은 prob 1/2입니다.
- m = 2. 답은 2/3입니다. 0과 2에는 하나의 후행 0이 있습니다.
- m = 3. 답은 1/2입니다. 0과 2에는 하나의 후행 0이 있습니다.
답변
Python , 36 바이트
lambda m:(m+1-bin(m).count('1'),m+1)
온라인으로 시도하십시오!
공식!
$$ 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 바이트
{1+⍵,+/⌊⍵÷2*⍳32}
온라인으로 시도하십시오!
\$\frac{1+\sum_{i=1}^{32}\left\lfloor\frac{m}{2^i}\right\rfloor}{1+m}\$. 분모, 분자를 반환합니다. 를 사용합니다 ⎕io=1.
MATL , 14 바이트
:B!P&X>qtswnhQ
이 코드는 무차별 대입을 사용합니다. 지정된 범위에있는 모든 숫자의 이진 확장을 계산하고 후행 0을 계산합니다.
출력은 분자와 분모입니다.
온라인으로 시도하십시오! . 첫 번째 출력 을 보거나 흥미로운 추세를 확인 하기 위해 플로팅 할 수도 있습니다 (자세한 내용은 아래 참조).
코드 작동 방식
: % 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
시퀀스의 흥미로운 속성
하자 \$a(m)\$순서를 나타냅니다. 그때
- \$a(m) = m/(m+1)\$때 \$m\$\ 의 거듭 제곱입니다$2\$.
- 만약 \$m\$\ 의 거듭 제곱입니다$2\$, \$a(n) < a(m)\$모든 \$n\ < 2m, n \neq m\$.
- \$\lim\sup_{m \rightarrow \infty} a(m) = 1\$.
1 증명
하자 \$m\$\ 의 힘$2\$. 세트 고려 \$\{1,2,\ldots,m\}\$. 이 세트에서 \$m/2\$멤버는 \의 배수입니다.$2\$, 따라서 동쪽에 후행 0이 있습니다. \$m/4\$멤버는 \의 배수입니다.$4\$, 추가 후행 0 등을 추가합니다. \의 배수는 하나뿐입니다.$m\$. 따라서 후행 0의 총 수는 \$m/2 + m/4 + \cdots + 1 = m-1\$, 세트에서 후행 0의 비율 \$\{1,2,\ldots,m\}\$이다 \$(m-1)/m\$. 따라서 세트 \$\{0,1,2,\ldots,m\}\$그것은 \$m/(m+1)\$.
2 증명
증명은 수학적 귀납법을 사용합니다.
대한 \$m=2\$ 청구 된 재산이 보유합니다.
하자 \$m\$\ 의 임의의 힘$2\$. 속성이 \$m/2\$. 속성 1과 결합하면 모든 \$k<m\$, \$a(k) \leq a(m/2) = m/(m+2) < m/(m+1)\$.
숫자 고려 \$m+1, m+2, \ldots, 2m-1\$. 후행 0은 \의 0과 동일합니다.$1, 2, \ldots, m-1\$각각 (이진 확장은 영향을 미치지 않는 1과 0으로 형성된 선행 문자열에서만 다릅니다). 대한 \$k<m\$, 속성 1을 다시 사용하여 용어 \$a(m+k)\$다음과 같이 표현 될 수있다 \$(m+j)/(m+1+k)\$, 여기서 \$j\$\ 에있는 후행 0의 총 수입니다.$\{m+1,\ldots,m+k\}\$, 또는 동등하게 \$\{1,\ldots,k\}\$. \ 이후$a(k) = j/k < m/(m+1)\$, 그것은 \$(m+j)/(m+1+k) < m/(m+1)\$.
따라서 속성은 \$m\$.
3의 증명
속성 1과 2에서 \$\lim\sup_{n \rightarrow \infty} a(n) = \lim_{m \rightarrow \infty} m/(m+1) = 1\$.
K (ngn / k) , 13 12 바이트
{1+x,x-/2\x}
온라인으로 시도하십시오!
xnor 's 처럼
{ } 인수가있는 함수 x
2\ 이진수
x-/마이너스로 감소, x초기 값으로 사용
x, 앞에 추가 x
1+ 쌍의 둘 다에 1을 더하십시오
J , 13 12 10 바이트
1-+/@#:%>:
온라인으로 시도하십시오!
-xnor의 포럼 덕분에 12 바이트
-2 바이트는 내 동사 내부에서 변환하는 대신 입력을 확장 정밀도로 만드는 Bubbler의 아이디어 덕분에
어떻게
1 빼기 입력의 이진 표현의 1-합을 입력에 1을 더한 +/@값 #:으로 나눈 값 입니다.%>:
실물
J , 24 바이트
(,1#.i.&1@|.@#:"0@i.)@>:
온라인으로 시도하십시오!
(분모, 분자)로 출력
APL (Dyalog 확장) , 9 바이트
-\1∘+,1⊥⊤
온라인으로 시도하십시오!
xnor의 Python 답변의 또 다른 포트 . 를 가져 n오고 반환 하는 암묵적인 함수입니다 (denom, num).
작동 원리
-\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 바이트
분수를 [numerator, denominator].
n=>[(g=k=>k?g(k&k-1)-1:++n)(n),n]
온라인으로 시도하십시오!
분자에 대한 재귀 공식은 처음에 A101925 에서 파생되었으며 그 자체는 A005187 (n) + 1 로 정의됩니다 .
(g=n=>n&&g(n>>1)+n)(n)-n+1
좀 더 골프를 치면 @xnor의 공식 과 동일합니다 .
05AB1E , 7 바이트
!Ò2¢s‚>
온라인으로 시도하십시오!
후행 0의 수는 \ 의 다중 도와 동일합니다.$2\$소인수 분해 ( \$n \ne 0\$). 이 방법은 우리는 단지 횟수를 계산해야합니다 \$2\$나눈다 \$m!\$.
! factorial
Ò prime factorization
2¢ count 2's
s‚ swap and pair (with input)
> increment both
[denominator, numerator]정상적으로 출력되면 !Ò2¢‚>6 바이트에서 작동합니다.
05AB1E , 8 바이트
xnor의 공식 구현 .
b1¢(0‚>+
온라인으로 시도하십시오!
보다 짧은 설정 비트 계산 방법이있을 수 있습니다 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 바이트
lambda m:(sum(bin(i+1)[:1:-1].find('1')for i in range(m))+1,m+1)
온라인으로 시도하십시오!
분수를 tuple로 반환합니다 (denominator, numerator).
Wolfram 언어 (Mathematica) , 26 바이트
1-DigitCount[#,2,1]/(#+1)&
온라인으로 시도하십시오!
Pyth , 12 바이트
,KhQ-K/.BQ"1
온라인으로 시도하십시오!
설명:
, // 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
출력 [denominator, numerator]
> <> , 37 바이트
1&l:{:})?\:2%0=?v&!
;n,+1{&/,2&+1&<
온라인으로 시도하십시오!
바이너리 표현을 처리하기위한 내장 기능이 없으므로 값 비싼 mod %루프가 필요합니다.
여기서 사용되는 트릭은 스택이 커지도록하는 것 l입니다. 단일 명령 으로 카운터를 즉시 사용할 수 있기 때문입니다 .
PHP , 44 바이트
fn($m)=>[$m-substr_count(decbin($m++),1),$m]
온라인으로 시도하십시오!
그것은이다 XNOR의 공식 @ 미성년자의 최적화.
젤리 , 6 바이트
BS’ạ,‘
한 쌍의 정수를 생성하는 정수를받는 모나 딕 링크, [numerator, denominator].
온라인으로 시도하십시오! 또는 0-40 포함을 참조하십시오.
또는 6 :
!Ḥọ2,‘
x86_64 기계어 코드, 15 바이트
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
입력 : min rdi, 출력 : [ rsi, rdi ]. 가치를 위해 작동합니다 m <= 4294967295.
온라인으로 시도하십시오!
또는 원래 16 비트 버전 ...
x86-16 기계 코드, 19 17 바이트
바이너리 :
00000000: 8bd0 33db d1e8 7301 4375 f942 8bc2 2bc3 ..3...s.Cu.B..+.
00000010: c3 .
목록 :
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
호출 함수 입력 m에서 AX출력 [ AX, DX ]. 값에 대해 작동합니다 m <= 65534(플랫폼 최대 int).
테스트 프로그램 출력 :
Husk , 6 바이트
A:1↑İr
온라인으로 시도하십시오! 이 함수는 눈금자 시퀀스 시작의 평균을 취합니다 .
Python 3 , 76 바이트
lambda m:(sum(len(bin(i))-len(bin(i).strip("0"))-1 for i in range(m+1)),m+1)
분수는 튜플로 반환됩니다. (numerator,denominator)
비 골프 버전 :
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)
온라인으로 시도하십시오!
목탄 , 11 바이트
Ｉ⟦⁻⊕θΣ⍘Ｎ²⊕θ
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다. @xnor의 Python 답변 포트. 설명:
θ 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 바이트
method(I,list(I-I toBase(2)occurancesOfSeq("1")+1,I+1))
온라인으로 시도하십시오!
자바 8, 27 바이트
n->-n.bitCount(n++)+n+"/"+n
@xnor 의 Python 답변 포트이므로 그를 찬성 하십시오!
온라인으로 시도하십시오.
설명:
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 바이트
âΣ~bα⌠+
@xnor 의 Python 답변 포트이므로 그를 찬성 하십시오!
온라인으로 시도하십시오.
설명:
â # 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 바이트
Mukundan314 덕분에 3 바이트 절약 !!!
f(int*m,int*n){*n=++*m-__builtin_popcount(*m-1);}
온라인으로 시도하십시오!
xnor 의 Python 답변 포트 .
Japt , 10 바이트
에서 적응 XNOR의 솔루션 . 입력은 단일 정수 배열이고 출력은 [numerator, denominator].
ËÒ-¤è1Ãp°U
시도 해봐