MathDB

2019 CMIMC

Part of CMIMC Problems

Subcontests

(15)
15
1
14
1

2019 T14: Integer Overflow

Consider the following function.
procedure \textsc{M}(x) <spanclass=′latex−bold′>if</span>0≤x≤1\qquad<span class='latex-bold'>if </span>0\leq x\leq 1 <spanclass=′latex−bold′>return</span>x\qquad\qquad<span class='latex-bold'>return </span>x \qquadreturn \textsc{M}(x^2\bmod 2^{32})
Let f:N→Nf:\mathbb N\to\mathbb N be defined such that f(x)=0f(x) = 0 if \textsc{M}(x) does not terminate, and otherwise f(x)f(x) equals the number of calls made to \textsc{M} during the running of \textsc{M}(x), not including the initial call. For example, f(1)=0f(1) = 0 and f(231)=1f(2^{31}) = 1. Compute the number of ones in the binary expansion of f(0)+f(1)+f(2)+⋯+f(232−1). f(0) + f(1) + f(2) + \cdots + f(2^{32} - 1).
13
1
12
1
11
1
10
4
9
4
8
4
7
4
6
4
5
4
4
4
3
4
2
4
1
4