10
\$\begingroup\$

Input

A bound m <= 4294967295.

Output

Consider values sampled uniformly at random from integers in the range 0 to m, inclusive.

Your output should be the expected (average) number of trailing zeros in the binary representation of the sampled value. Your answer should be exact, for example given as a fraction.

Example

  • m = 0. The answer is 1. 0 will be sampled with prob 1.
  • m = 1. The answer is 1/2. 0 with prob 1/2 and 1 with prob 1/2.
  • m = 2. The answer is 2/3. 0 and 2 have one trailing zero.
  • m = 3. The answer is 1/2. 0 and 2 have one trailing zero.
\$\endgroup\$
27
  • 1
    \$\begingroup\$ Why the close vote? \$\endgroup\$ – user9207 Aug 20 '20 at 21:29
  • 2
    \$\begingroup\$ @Anush why? i think 0 or ∞ make much more sense than 1. \$\endgroup\$ – ngn Aug 20 '20 at 22:00
  • 1
    \$\begingroup\$ @ngn That’s the convention I chose. There is certainly a zero to point at. \$\endgroup\$ – user9207 Aug 20 '20 at 22:02
  • 2
    \$\begingroup\$ Framing this challenge in terms of probabilities and uniform random sampling seems unnecessarily complicated. Aren't you really just asking for the average number of trailing zeros in the binary representations of all integers from \$0\$ to \$m\$? \$\endgroup\$ – Dingus Aug 20 '20 at 22:27
  • 6
    \$\begingroup\$ @Dingus Even more, I don't see the need for the challenge to use average instead of sum. The difference is that most answers just also output m+1 for the denominator. \$\endgroup\$ – xnor Aug 20 '20 at 22:40

23 Answers 23

10
\$\begingroup\$

Python, 36 bytes

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

Try it online!

A formula!

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

\$\endgroup\$
6
  • \$\begingroup\$ Nice. Why is it true? \$\endgroup\$ – Jonah Aug 20 '20 at 22:46
  • \$\begingroup\$ where did you get that formula from? \$\endgroup\$ – aidan0626 Aug 20 '20 at 22:46
  • \$\begingroup\$ oeis.org/A011371 \$\endgroup\$ – J42161217 Aug 20 '20 at 22:47
  • 1
    \$\begingroup\$ Cracked it :) Well done. \$\endgroup\$ – user9207 Aug 20 '20 at 22:48
  • 2
    \$\begingroup\$ python 3.10 (pre-release) has builtin for counting set bits \$\endgroup\$ – Mukundan314 Aug 21 '20 at 3:27
5
\$\begingroup\$

APL (Dyalog Unicode), 16 bytes

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

Try it online!

\$\frac{1+\sum_{i=1}^{32}\left\lfloor\frac{m}{2^i}\right\rfloor}{1+m}\$. returns denominator,numerator. uses ⎕io=1.

\$\endgroup\$
6
  • \$\begingroup\$ Very nice! Thank you \$\endgroup\$ – user9207 Aug 20 '20 at 22:41
  • \$\begingroup\$ Is the 32 in the limit of the sum right? If m=256 I can’t see why it would work. Should the 32 be the bit length of m? \$\endgroup\$ – user9207 Aug 20 '20 at 23:13
  • \$\begingroup\$ @Anush 2^32 is the limit you set in the challenge (m <= 4294967295). are you saying it doesn't work for 256? \$\endgroup\$ – ngn Aug 20 '20 at 23:18
  • \$\begingroup\$ Oh I see. All the terms above i = floor(log_2 (m)) + 1 are 0. \$\endgroup\$ – user9207 Aug 21 '20 at 8:53
  • 1
    \$\begingroup\$ @Anush first i realized that i have to count all trailing zeroes and divide by m+1. so i wrote down the binary representations up to some m and noticed that about half of them end with (at least a single) 0, then half of those end with 00, etc \$\endgroup\$ – ngn Aug 21 '20 at 12:16
5
\$\begingroup\$

MATL, 14 bytes

:B!P&X>qtswnhQ

The code uses brute force: computes the binary expansion of all the numbers in the specified range and counts trailing zeros.

Output is numerator, then denominator.

Try it online!. You can also see the first outputs, or plot them to see some interesting trends (more on this below).

How the code works

:    % 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

Some interesting properties of the sequence

Let \$a(m)\$ denote the sequence. Then

  1. \$a(m) = m/(m+1)\$ when \$m\$ is a power of \$2\$.
  2. If \$m\$ is a power of \$2\$, \$a(n) < a(m)\$ for all \$n\ < 2m, n \neq m\$.
  3. \$\lim\sup_{m \rightarrow \infty} a(m) = 1\$.

Proof of 1

Let \$m\$ be a power of \$2\$. Consider the set \$\{1,2,\ldots,m\}\$. In this set, \$m/2\$ members are multiples of \$2\$, and thus have at east a trailing zero. \$m/4\$ members are multiples of \$4\$, and contribute one additional trailing zero, etc. There is only one multiple of \$m\$. So the total number of trailing zeros is \$m/2 + m/4 + \cdots + 1 = m-1\$, and the fraction of trailing zeros in the set \$\{1,2,\ldots,m\}\$ is \$(m-1)/m\$. Therefore in the set \$\{0,1,2,\ldots,m\}\$ it is \$m/(m+1)\$.

Proof of 2

The proof uses mathematical induction.

For \$m=2\$ the claimed property holds.

Let \$m\$ be an arbitrary power of \$2\$. Assume that the property holds for \$m/2\$. Combined with property 1 this implies that, for all \$k<m\$, \$a(k) \leq a(m/2) = m/(m+2) < m/(m+1)\$.

Consider the numbers \$m+1, m+2, \ldots, 2m-1\$. Their trailing zeros are the same as those of \$1, 2, \ldots, m-1\$ respectively (the binary expansions only differ in a leading string formed by a one and some zeros, which doesn't affect). For \$k<m\$, using property 1 again the term \$a(m+k)\$ can be expressed as \$(m+j)/(m+1+k)\$, where \$j\$ is the total number of trailing zeros in \$\{m+1,\ldots,m+k\}\$, or equivalently in \$\{1,\ldots,k\}\$. Since \$a(k) = j/k < m/(m+1)\$, it holds that \$(m+j)/(m+1+k) < m/(m+1)\$.

Therefore the property is satisfied for \$m\$.

Proof of 3

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Pretty amazing . \$\endgroup\$ – user9207 Aug 20 '20 at 22:08
4
\$\begingroup\$

K (ngn/k), 13 12 bytes

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

Try it online!

like xnor's

{ } function with argument x

2\ binary digits

x-/ reduction with minus, using x as initial value

x, prepend x

1+ add 1 to both in the pair

\$\endgroup\$
0
4
\$\begingroup\$

J, 13 12 10 bytes

1-+/@#:%>:

Try it online!

-12 bytes thanks to the forumula of xnor

-2 bytes thanks to Bubbler's idea of making the input extended precision rather than converting inside my verb

how

One minus 1- the sum of +/@ the binary representation of the input #: divided by % the input plus one >:.

original

J, 24 bytes

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

Try it online!

Outputs as (denominator, numerator)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can remove x:@ from your 13-byter by specifying the input format to be an extended integer. \$\endgroup\$ – Bubbler Aug 20 '20 at 23:11
4
\$\begingroup\$

APL (Dyalog Extended), 9 bytes

-\1∘+,1⊥⊤

Try it online!

Yet another port of xnor's Python answer. A tacit function that takes n and returns (denom, num).

How it works

-\1∘+,1⊥⊤  ⍝ Input: n
      1⊥⊤  ⍝ Popcount(n)
  1∘+,     ⍝ Pair with n+1
-\         ⍝ Minus scan; convert (a,b) to (a,a-b)
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6),  35  33 bytes

Outputs the fraction as [numerator, denominator].

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

Try it online!

The recursive formula for the numerator was initially derived from A101925, which itself is defined as A005187(n) + 1:

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

Once golfed some more, it turns out to be equivalent to @xnor's formula.

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 7 bytes

!Ò2¢s‚>

Try it online!

The number of trailing zeros is the same as the multiplicity of \$2\$ in the prime factorization (for \$n \ne 0\$). This means we just need to count the number of times \$2\$ divides \$m!\$.

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

If output as [denominator, numerator] is fine, !Ò2¢‚> works at 6 bytes.


05AB1E, 8 bytes

An implementation of xnor's formula.

b1¢(0‚>+

Try it online!

There may be a shorter way to count set bits than 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
\$\endgroup\$
5
  • \$\begingroup\$ Whoa! 6 is short :) \$\endgroup\$ – user9207 Aug 21 '20 at 7:29
  • \$\begingroup\$ Ò2¢ can be Óн for -1. \$\endgroup\$ – Kevin Cruijssen Aug 21 '20 at 7:58
  • 1
    \$\begingroup\$ @KevinCruijssen I just tried that as well, but it doesn't doesn't work for 0 and 1 as н returns "" on an empty list: tio.run/##yy9OTMpM/f9fUeHw5At7FYofNcyy@//fEAA \$\endgroup\$ – ovs Aug 21 '20 at 8:01
  • \$\begingroup\$ @ovs Ah ofc, didn't think about those two. \$\endgroup\$ – Kevin Cruijssen Aug 21 '20 at 8:01
  • \$\begingroup\$ What is this diabolic code?! You shall not pass! \$\endgroup\$ – Hal Aug 21 '20 at 20:19
2
\$\begingroup\$

Python 3, 65 64 bytes

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

Try it online!

Returns the fraction as tuple (denominator, numerator).

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 26 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Pyth, 12 bytes

,KhQ-K/.BQ"1

Try it online!

Explanation:

,             // 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

Outputs [denominator, numerator]

\$\endgroup\$
2
\$\begingroup\$

><>, 37 bytes

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

Try it online!

No built-ins to deal with binary representations, so a costly mod% loop is necessary.

A trick used here is to just let the stack grow, since that makes a counter instantly available with only a single l command.

\$\endgroup\$
2
\$\begingroup\$

PHP, 44 bytes

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

Try it online!

It's @xnor's formula with a minor optimization.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 6 bytes

BS’ạ,‘

A monadic Link accepting an integer which yields a pair of integers, [numerator, denominator].

Try it online! Or see 0-40 inclusive.


Or, also for 6:

!Ḥọ2,‘
\$\endgroup\$
2
\$\begingroup\$

x86_64 machine code, 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

Input: m in rdi, output: [ rsi, rdi ]. Works for values m <= 4294967295.

Try it online!

Or original 16-bit version...

x86-16 machine code, 19 17 bytes

Binary:

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

Listing:

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

Callable function, input m in AX output [ AX, DX ]. Works for values m <= 65534 (platform max int).

Test program output:

enter image description here

\$\endgroup\$
2
\$\begingroup\$

Husk, 6 bytes

A:1↑İr

Try it online! This function just takes the average of the start of the ruler sequence.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 76 bytes

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

Fraction is returned as a tuple (numerator,denominator)

Non-golfed version:

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)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 11 bytes

I⟦⁻⊕θΣ⍘N²⊕θ

Try it online! Link is to verbose version of code. Port of @xnor's Python answer. Explanation:

    θ       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
\$\endgroup\$
1
\$\begingroup\$

Io, 55 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Java 8, 27 bytes

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

Port of @xnor's Python answer, so make sure to upvote him as well!

Try it online.

Explanation:

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`
\$\endgroup\$
1
\$\begingroup\$

MathGolf, 7 bytes

âΣ~bα⌠+

Port of @xnor's Python answer, so make sure to upvote him as well!

Try it online.

Explanation:

â        # 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)
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 52 49 bytes

Saved 3 bytes thanks to Mukundan314!!!

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

Try it online!

Port of xnor's Python answer.

\$\endgroup\$
4
  • \$\begingroup\$ -3 bytes by outputting via output arguments \$\endgroup\$ – Mukundan314 Aug 21 '20 at 2:22
  • \$\begingroup\$ Alternatively, save a byte with some reordering: -__builtin_popcount(m++)+m,m \$\endgroup\$ – SE - stop firing the good guys Aug 21 '20 at 9:08
  • \$\begingroup\$ @Mukundan314 Nice one - thanks! :-) \$\endgroup\$ – Noodle9 Aug 21 '20 at 10:51
  • \$\begingroup\$ @SE-stopfiringthegoodguys Good idea but won't work with Mukundan314's idea, Thanks anyway! :-) \$\endgroup\$ – Noodle9 Aug 21 '20 at 10:52
0
\$\begingroup\$

Japt, 10 bytes

Adapted from xnor's solution. Input is a single integer array, output is [numerator, denominator].

ËÒ-¤è1Ãp°U

Try it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy