Detailed mathematical approach

Problem Summary

For each positive integer \(x\), consider all integers obtained by deleting exactly one binary digit from the binary expansion of \(x\). These smaller integers act as predecessors. A deleted \(1\)-bit gives a lower constraint, and a deleted \(0\)-bit gives an upper constraint.

Starting from the base value \(v_0=0\), the value \(v_x\) is defined to be the simplest dyadic rational compatible with all those constraints. Here a dyadic rational means a number of the form \(\frac{m}{2^k}\) with \(m\in\mathbb{Z}\) and \(k\ge 0\).

The target quantity is

$S(n)=\left\lceil \sum_{i=1}^{n} i\,v_i \right\rceil.$

Mathematical Approach

The recurrence is local: once the deleted-bit predecessors of \(x\) are known, \(v_x\) is forced to lie in an open interval, and the simplest dyadic number inside that interval is chosen.

Step 1: Deleted-Bit Predecessors Create the Interval

Let the deleted-bit predecessors of \(x\) be \(y_1,\dots,y_\ell\), where \(\ell\) is the binary length of \(x\). Every predecessor is smaller than \(x\), because deleting one bit shortens the representation to at most \(\ell-1\) bits, so

$y_j<2^{\ell-1}\le x.$

This is why the values can be computed in increasing order of \(x\).

Let \(A_x\) be the set of predecessor values coming from deleted \(1\)-bits, and let \(B_x\) be the set coming from deleted \(0\)-bits. Define

$L_x=\max A_x,$

and, when \(B_x\neq\varnothing\), define

$R_x=\min B_x.$

The defining inequalities are

$v_x>L_x,$

and, if \(B_x\neq\varnothing\), also

$v_x<R_x.$

Because the leading binary digit is always \(1\), the set \(A_x\) is never empty, so every \(x\ge 1\) has at least a lower bound.

Step 2: Turn the Open Interval into Integer Inequalities

Suppose first that \(B_x\neq\varnothing\) and test a dyadic candidate \(\frac{m}{2^k}\). The condition

$L_x<\frac{m}{2^k}<R_x$

is equivalent to

$\left\lfloor 2^kL_x\right\rfloor+1\le m\le \left\lceil 2^kR_x\right\rceil-1.$

So, for a fixed denominator \(2^k\), admissible numerators are exactly the integers in that closed interval. The smallest \(k\) for which such an integer exists gives the coarsest denominator and therefore the simplest dyadic level.

If \(B_x=\varnothing\), then the binary expansion of \(x\) contains no \(0\)-bit. There is no upper bound, and the simplest admissible dyadic is just the smallest integer strictly larger than \(L_x\):

$v_x=\lfloor L_x\rfloor+1.$

Step 3: Choose the Simplest Dyadic and Reduce It

Once the minimal denominator \(2^k\) is known, there may be several admissible numerators. The implementations select the feasible integer closest to \(0\): choose \(m=0\) if possible, otherwise choose the admissible integer with smallest absolute value. This reproduces the intended notion of the simplest dyadic inside the interval.

After that, remove all common factors of \(2\) from numerator and denominator. Each value is therefore stored in reduced form

$v_x=\frac{a_x}{2^{e_x}},$

where \(a_x\) is odd unless the value is \(0\).

This reduction is important because dyadic numbers can then be compared exactly by lifting them to a common power-of-two denominator and comparing the scaled numerators as integers. No floating-point approximation is needed anywhere.

Step 4: Evaluate the Weighted Ceiling Sum Exactly

After computing \(v_1,\dots,v_n\), write each one as \(v_i=\frac{a_i}{2^{e_i}}\) in reduced form, and let

$E=\max_{1\le i\le n} e_i.$

Then

$\sum_{i=1}^{n} i\,v_i=\frac{1}{2^E}\sum_{i=1}^{n} i\,a_i\,2^{E-e_i}=\frac{N_n}{2^E},$

where \(N_n\) is an integer.

In this recurrence every \(v_i\) is positive, so \(N_n\ge 0\). Therefore

$S(n)=\left\lceil \frac{N_n}{2^E}\right\rceil=\left\lfloor \frac{N_n+2^E-1}{2^E}\right\rfloor.$

The final ceiling can thus be computed with integer arithmetic only.

Worked Example

The first few values come directly from the interval rule:

$\begin{aligned} v_1&=1,\\ v_2&=\frac{1}{2},\\ v_3&=2,\\ v_4&=\frac{1}{4},\\ v_5&=\frac{3}{2}. \end{aligned}$

For example, \(x=5\) has binary form \(101_2\). Deleting the leftmost \(1\) gives \(1\), deleting the middle \(0\) gives \(3\), and deleting the last \(1\) gives \(2\). So the lower bound is

$L_5=\max(v_1,v_2)=1,$

the upper bound is

$R_5=v_3=2,$

and the simplest dyadic in \((1,2)\) is

$v_5=\frac{3}{2}.$

Using the first five values,

$S(5)=\left\lceil 1\cdot 1+2\cdot \frac{1}{2}+3\cdot 2+4\cdot \frac{1}{4}+5\cdot \frac{3}{2}\right\rceil=\left\lceil \frac{33}{2}\right\rceil=17.$

Continuing the same recurrence gives

$v_6=1,\qquad v_7=3,\qquad v_8=\frac{1}{8},\qquad v_9=\frac{5}{4},\qquad v_{10}=\frac{3}{4},$

hence

$S(10)=64,$

which matches the implementation checkpoint.

How the Code Works

The C++, Python, and Java implementations iterate from \(1\) up to \(n\). For each \(x\), they scan all bit positions, form each deleted-bit predecessor, and update the best lower and upper bounds using exact dyadic comparisons. Because every predecessor is smaller than \(x\), all required values are already known when \(x\) is processed.

They then test denominators \(1,2,4,\dots\) until the interval contains an admissible dyadic rational. The chosen value is reduced immediately so the stored denominator is as small as possible. After the table is complete, the implementations lift every term \(i\,v_i\) to a common denominator, add the integer numerators, and apply the ceiling formula exactly.

Complexity Analysis

For a given \(x\), there are \(\lfloor\log_2 x\rfloor+1\) deleted-bit predecessors to inspect, so building the interval for \(v_x\) costs \(O(\log x)\). The additional search over dyadic denominators is bounded by a small fixed constant in the implementations, so the total running time up to \(n\) is \(O(n\log n)\). The table of dyadic values uses \(O(n)\) memory.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=882
2. Dyadic rational: Wikipedia - Dyadic rational
3. Binary numeral system: Wikipedia - Binary number
4. Floor and ceiling functions: Wikipedia - Floor and ceiling functions