Project Euler/112

Problem Statement

Analysis

This problem asks for the least positive integer $N$ such that the proportion of "bouncy" numbers up to $N$ is exactly 99%.

A number is bouncy if it is neither increasing (digits non-decreasing left-to-right, e.g., 13448) nor decreasing (digits non-increasing left-to-right, e.g., 99740).

Let $B(N)$ be the count of bouncy numbers $\leq N$, and $NB(N)$ be the count of non-bouncy numbers $\leq N$.

The condition is ${\frac {B(N)}{N}}=0.99$.

Since $B(N)=N-NB(N)$, the condition becomes:

${\frac {N-NB(N)}{N}}=0.99\implies 1-{\frac {NB(N)}{N}}=0.99\implies {\frac {NB(N)}{N}}=0.01$

This means we seek the smallest $N$ such that $NB(N)={\frac {N}{100}}$.

A key consequence is that $N$ must be a multiple of 100.

Non-bouncy numbers are either increasing or decreasing.

Let $I(N)$ be the count of increasing numbers $\leq N$ and $D(N)$ be the count of decreasing numbers $\leq N$.

Numbers with all identical digits (e.g., 555) are both increasing and decreasing; let their count be $F(N)$.

By inclusion-exclusion:

$NB(N)=I(N)+D(N)-F(N)$

While calculating $I(N),D(N),F(N)$ for arbitrary $N$ typically requires Digit Dynamic Programming, analytical formulas exist for $N=10^{k}-1$:

$|I(10^{k}-1)|={\binom {k+9}{9}}-1$

$|D(10^{k}-1)|={\binom {k+10}{10}}-1-k$

$|F(10^{k}-1)|=9k$

$|NB(10^{k}-1)|={\binom {k+9}{9}}+{\binom {k+10}{10}}-10k-2$

These formulas show that the proportion of non-bouncy numbers drops below 1.3% for $k=6$ ($N=999,999$) and below 0.4% for $k=7$ ($N=9,999,999$), indicating $N$ is likely greater than $10^{6}$.

The computational strategy is:

1. Implement functions (likely using Digit DP) to compute $NB(N)$ accurately for any $N$.

2. Search for the target $N$ by checking multiples of 100, starting from an estimated lower bound (e.g., $N\approx 100\times NB(10^{6}-1)\approx 1.3\times 10^{6}$).

3. The first $N$ found such that $NB(N)=N/100$ is the solution.

Solution

Link to solution: https://git.charlesreid1.com/cs/euler/src/branch/master/java/Problem112.java