Project Euler/112 - Revision history

Admin: Restructure page to match Project Euler/42 format: add detailed Approach section mirroring the Java Digit DP implementation (via update-page on MediaWiki MCP Server)

2026-06-16T14:40:44Z

Restructure page to match Project Euler/42 format: add detailed Approach section mirroring the Java Digit DP implementation (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 14:40, 16 June 2026
Line 3:		Line 3:
	[[Image:ProjectEuler112.png\|500px]]		[[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>		<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>		</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>

	~~1. Implement functions (likely using Digit DP) to compute <math>NB(N)</math> accurately for any <math>N</math>.~~		===Search Strategy===

	~~2. 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.

	~~3. 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==		==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}}		{{ProjectEulerFlag}}

Unknown user: /* Solution */

2025-04-20T03:06:04Z

Solution

← Older revision		Revision as of 03:06, 20 April 2025
Line 3:		Line 3:
	[[Image:ProjectEuler112.png\|500px]]		[[Image:ProjectEuler112.png\|500px]]

	==~~Solution~~==		==Analysis==


	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%.		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%.
Line 55:		Line 54:

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

			==Solution==

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

	==Flag==		==Flag==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Solution */

2025-04-20T02:42:27Z

Solution

← Older revision		Revision as of 02:42, 20 April 2025
Line 6:		Line 6:


	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%. 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).		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%.

			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 <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>.		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>.

	The condition is <math>\frac{B(N)}{N} = 0.99</math>.		The condition is <math>\frac{B(N)}{N} = 0.99</math>.

Line 18:		Line 21:

	This means we seek the smallest <math>N</math> such that <math>NB(N) = \frac{N}{100}</math>.		This means we seek the smallest <math>N</math> such that <math>NB(N) = \frac{N}{100}</math>.

	A key consequence is that <math>N</math> must be a multiple of 100.		A key consequence is that <math>N</math> must be a multiple of 100.

	Non-bouncy numbers are either increasing or decreasing. 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>. ~~Numbers with all identical digits (e.g., 555) are both increasing and decreasing;~~		Non-bouncy numbers are either increasing or decreasing.

			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>.

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

	By inclusion-exclusion:		By inclusion-exclusion:

Unknown user: /* Solution */

2025-04-20T02:41:22Z

Solution

← Older revision		Revision as of 02:41, 20 April 2025
Line 12:		Line 12:

	Since <math>B(N) = N - NB(N)</math>, the condition becomes:		Since <math>B(N) = N - NB(N)</math>, the condition becomes:

	<math>		<math>
	\frac{N - NB(N)}{N} = 0.99 \implies 1 - \frac{NB(N)}{N} = 0.99 \implies \frac{NB(N)}{N} = 0.01		\frac{N - NB(N)}{N} = 0.99 \implies 1 - \frac{NB(N)}{N} = 0.99 \implies \frac{NB(N)}{N} = 0.01
	</math>		</math>

	This means we seek the smallest <math>N</math> such that <math>NB(N) = \frac{N}{100}</math>.		This means we seek the smallest <math>N</math> such that <math>NB(N) = \frac{N}{100}</math>.
	A key consequence is that <math>N</math> must be a multiple of 100.		A key consequence is that <math>N</math> must be a multiple of 100.

	Non-bouncy numbers are either increasing or decreasing. 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>. Numbers with all identical digits (e.g., 555) are both increasing and decreasing; let their count be <math>F(N)</math>.		Non-bouncy numbers are either increasing or decreasing. 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>. Numbers with all identical digits (e.g., 555) are both increasing and decreasing;

			let their count be <math>F(N)</math>.

	By inclusion-exclusion:		By inclusion-exclusion:

	<math>		<math>
	NB(N) = I(N) + D(N) - F(N)		NB(N) = I(N) + D(N) - F(N)
Line 27:		Line 33:

	<math>\|I(10^k-1)\| = \binom{k+9}{9} - 1</math>		<math>\|I(10^k-1)\| = \binom{k+9}{9} - 1</math>

	<math>\|D(10^k-1)\| = \binom{k+10}{10} - 1 - k</math>		<math>\|D(10^k-1)\| = \binom{k+10}{10} - 1 - k</math>

	<math>\|F(10^k-1)\| = 9k</math>		<math>\|F(10^k-1)\| = 9k</math>

	<math>\|NB(10^k-1)\| = \binom{k+9}{9} + \binom{k+10}{10} - 10k - 2</math>		<math>\|NB(10^k-1)\| = \binom{k+9}{9} + \binom{k+10}{10} - 10k - 2</math>

	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>.		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>.

Unknown user: /* Problem Statement */

2025-04-20T02:39:52Z

Problem Statement

@@ Line 3: / Line 3: @@
 [[Image:ProjectEuler112.png|500px]]
 ==Flag==
 {{ProjectEulerFlag}}

Unknown user: Created page with "==Problem Statement== 500px ==Flag== {{ProjectEulerFlag}}"

2025-04-20T02:35:41Z

Created page with "==Problem Statement== 500px ==Flag== {{ProjectEulerFlag}}"

New page

==Problem Statement==

[[Image:ProjectEuler112.png|500px]]

==Flag==

{{ProjectEulerFlag}}