Project Euler/112: Difference between revisions

Latest revision as of 14:40, 16 June 2026

Problem Statement

Working from left-to-right, if no digit is exceeded by the digit to its left it is called an increasing number — for example, 134468.

Similarly, if no digit is exceeded by the digit to its right it is called a decreasing number — for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number — for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.

Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.

Approach

The goal is to find the least $$ N $$ such that the proportion of bouncy numbers $\le N$ is exactly 99%. Equivalently, the count of non-bouncy numbers $$ NB(N) $$ must satisfy:

$NB(N) = \frac{N}{100}$

This implies $$ N $$ must be a multiple of 100.

A number is non-bouncy if it is either increasing or decreasing. Numbers with all identical digits (e.g., 555) are both increasing and decreasing, so by inclusion-exclusion:

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

where $$ I(N) $$ , $$ D(N) $$ , and $$ F(N) $$ are the counts of increasing, decreasing, and flat (all digits identical) numbers $\le N$ , respectively.

Digit DP for Increasing Numbers

The function $$ I(N) $$ counts positive integers $x \le N$ whose digits are non-decreasing from left to right. This is computed using a recursive Digit DP with memoization.

State variables:

index — current digit position being processed (0 to number of digits in $$ N $$ )
prevDigit — the previous digit placed (0–9)
isLessThan — whether the prefix constructed so far is already strictly less than the corresponding prefix of $$ N $$
isLeadingZero — whether we are still in the leading-zero phase (no non-zero digit has been placed yet)

Transitions: At each position, iterate over possible digits $$ d $$ from 0 up to the bound (9 if isLessThan is true, otherwise the digit of $$ N $$ at that position). If isLeadingZero is active and $$ d = 0 $$ , the leading-zero state continues. Once a non-zero digit is placed, subsequent digits must satisfy $d \ge \text{prevDigit}$ to maintain the increasing property.

The DP result includes 0, so 1 is subtracted to count only positive integers.

Digit DP for Decreasing Numbers

The function $$ D(N) $$ is analogous but enforces non-increasing digits ( $d \le \text{prevDigit}$ ). The memoization table uses an extra slot (index 10) to represent the initial/leading-zero state where no previous digit constraint applies.

Counting Flat Numbers

Flat numbers are those with all digits identical (e.g., 7, 22, 999). The count $$ F(N) $$ is computed directly:

For each digit length less than the length of $$ N $$ , there are 9 flat numbers (one for each digit 1–9).
For numbers with the same length as $$ N $$ , each candidate flat number (111…1 through 999…9) is compared lexicographically to $$ N $$ ; if it is $\le N$ , it is counted.

Non-Bouncy Count

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

Search Strategy

The search begins at $$ N = 1{,}000{,}000 $$ (where the proportion of bouncy numbers is approximately 98.7%) and increments by 100. At each step, $$ NB(N) $$ is computed via the Digit DP routines. The first $$ N $$ satisfying $$ NB(N) = N / 100 $$ is the answer.

A timeout and an upper bound (50,000,000) are included as safety guards.

Solution

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

Flags

@@ Line 3: / Line 3: @@
 [[Image:ProjectEuler112.png|500px]]
-==Analysis==
+Working from left-to-right, if no digit is exceeded by the digit to its left it is called an increasing number — for example, 134468.
-This problem asks for the least positive integer <math>N</math> such that the proportion of "bouncy" numbers up to <math>N</math> is exactly 99%.
+Similarly, if no digit is exceeded by the digit to its right it is called a decreasing number — for example, 66420.
-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).
+We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number — for example, 155349.
-Let <math>B(N)</math> be the count of bouncy numbers <math>\le N</math>, and <math>NB(N)</math> be the count of non-bouncy numbers <math>\le N</math>.
+Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.
-The condition is <math>\frac{B(N)}{N} = 0.99</math>.
+Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.
-Since <math>B(N) = N - NB(N)</math>, the condition becomes:
+Find the least number for which the proportion of bouncy numbers is exactly 99%.
+==Approach==
+The goal is to find the least <math>N</math> such that the proportion of bouncy numbers <math>\le N</math> is exactly 99%. Equivalently, the count of non-bouncy numbers <math>NB(N)</math> must satisfy:
 <math>
-\frac{N - NB(N)}{N} = 0.99 \implies 1 - \frac{NB(N)}{N} = 0.99 \implies \frac{NB(N)}{N} = 0.01
+NB(N) = \frac{N}{100}
 </math>
-This means we seek the smallest <math>N</math> such that <math>NB(N) = \frac{N}{100}</math>.
+This implies <math>N</math> must be a multiple of 100.
-A key consequence is that <math>N</math> must be a multiple of 100.
+A number is non-bouncy if it is either increasing or decreasing. Numbers with all identical digits (e.g., 555) are both increasing and decreasing, so by inclusion-exclusion:
-Non-bouncy numbers are either increasing or decreasing.
+<math>
+NB(N) = I(N) + D(N) - F(N)
+</math>
-Let <math>I(N)</math> be the count of increasing numbers <math>\le N</math> and <math>D(N)</math> be the count of decreasing numbers <math>\le N</math>.
+where <math>I(N)</math>, <math>D(N)</math>, and <math>F(N)</math> are the counts of increasing, decreasing, and flat (all digits identical) numbers <math>\le N</math>, respectively.
-Numbers with all identical digits (e.g., 555) are both increasing and decreasing; let their count be <math>F(N)</math>.
+===Digit DP for Increasing Numbers===
-By inclusion-exclusion:
+The function <math>I(N)</math> counts positive integers <math>x \le N</math> whose digits are non-decreasing from left to right. This is computed using a recursive Digit DP with memoization.
-<math>
+'''State variables:'''
-NB(N) = I(N) + D(N) - F(N)
+* <code>index</code> — current digit position being processed (0 to number of digits in <math>N</math>)
-</math>
+* <code>prevDigit</code> — the previous digit placed (0–9)
+* <code>isLessThan</code> — whether the prefix constructed so far is already strictly less than the corresponding prefix of <math>N</math>
+* <code>isLeadingZero</code> — whether we are still in the leading-zero phase (no non-zero digit has been placed yet)
+'''Transitions:''' At each position, iterate over possible digits <math>d</math> from 0 up to the bound (9 if <code>isLessThan</code> is true, otherwise the digit of <math>N</math> at that position). If <code>isLeadingZero</code> is active and <math>d = 0</math>, the leading-zero state continues. Once a non-zero digit is placed, subsequent digits must satisfy <math>d \ge \text{prevDigit}</math> to maintain the increasing property.
+The DP result includes 0, so 1 is subtracted to count only positive integers.
-While calculating <math>I(N), D(N), F(N)</math> for arbitrary <math>N</math> typically requires Digit Dynamic Programming, analytical formulas exist for <math>N=10^k-1</math>:
+===Digit DP for Decreasing Numbers===
-<math>|I(10^k-1)| = \binom{k+9}{9} - 1</math>
+The function <math>D(N)</math> is analogous but enforces non-increasing digits (<math>d \le \text{prevDigit}</math>). The memoization table uses an extra slot (index 10) to represent the initial/leading-zero state where no previous digit constraint applies.
-<math>|D(10^k-1)| = \binom{k+10}{10} - 1 - k</math>
+===Counting Flat Numbers===
-<math>|F(10^k-1)| = 9k</math>
+Flat numbers are those with all digits identical (e.g., 7, 22, 999). The count <math>F(N)</math> is computed directly:
-<math>|NB(10^k-1)| = \binom{k+9}{9} + \binom{k+10}{10} - 10k - 2</math>
+* For each digit length less than the length of <math>N</math>, there are 9 flat numbers (one for each digit 1–9).
+* For numbers with the same length as <math>N</math>, each candidate flat number (111…1 through 999…9) is compared lexicographically to <math>N</math>; if it is <math>\le N</math>, it is counted.
-These formulas show that the proportion of non-bouncy numbers drops below 1.3% for <math>k=6</math> (<math>N=999,999</math>) and below 0.4% for <math>k=7</math> (<math>N=9,999,999</math>), indicating <math>N</math> is likely greater than <math>10^6</math>.
+===Non-Bouncy Count===
-The computational strategy is:
+<math>
+NB(N) = I(N) + D(N) - F(N)
+</math>
-. Implement functions (likely using Digit DP) to compute <math>NB(N)</math> accurately for any <math>N</math>.
+===Search Strategy===
-. Search for the target <math>N</math> by checking multiples of 100, starting from an estimated lower bound (e.g., <math>N \approx 100 \times NB(10^6-1) \approx 1.3 \times 10^6</math>).
+The search begins at <math>N = 1{,}000{,}000</math> (where the proportion of bouncy numbers is approximately 98.7%) and increments by 100. At each step, <math>NB(N)</math> is computed via the Digit DP routines. The first <math>N</math> satisfying <math>NB(N) = N / 100</math> is the answer.
-. The first <math>N</math> found such that <math>NB(N) = N/100</math> is the solution.
+A timeout and an upper bound (50,000,000) are included as safety guards.
 ==Solution==
-Link to solution: https://git.charlesreid1.com/cs/euler/src/branch/master/java/Problem112.java
+Link to solution: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem112.java
-==Flag==
+==Flags==
 {{ProjectEulerFlag}}