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
- \$a(m) = m/(m+1)\$ when \$m\$ is a power of \$2\$.
- If \$m\$ is a power of \$2\$, \$a(n) < a(m)\$ for all \$n\ < 2m, n \neq m\$.
- \$\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\$.
m+1for the denominator. \$\endgroup\$ – xnor Aug 20 '20 at 22:40