Euler Problem 112 asks:
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%.
Looking at the three examples, adjacent digits can be equal and not disqualifying in any of the cases. This means that a number such as 222222 is both increasing and decreasing. Semantically, while this is nonsense, it’s clear that 222222 cannot be bouncy. Using this observation does give us a way of breaking out of a loop without having to check every digit. If the count of the increasing digits (I) equals the counter, or the count of decreasing digits (D) equals the counter, than the number cannot be bouncy. Similarly, if they are ever both less than the counter, the number must be bouncy, and break the loop.
We’ll start with the Answer as 21780, bouncy number B as 0.9*Answer and keep going until B/Answer is 0.99.
Here is the code that does that. It runs in 3.5 seconds on my new hot rod, a 3Ghz dual core tech refresh. My fastest machine is now the office PC.
Dim Num As String, j As Long
Dim I As Long, D As Long, B As Long
Dim Answer As Long, T As Single
T = Timer
Answer = 21780
B = 0.9 * Answer
Answer = Answer + 1
I = 0
D = 0
Num = CStr(Answer)
For j = 1 To Len(Num) – 1
If Mid(Num, j, 1) LTE Mid(Num, j + 1, 1) Then ‘Increasing
I = I + 1
If Mid(Num, j, 1) GTE Mid(Num, j + 1, 1) Then ‘Decreasing
D = D + 1
If I != j And D != j Then Exit For
If I LT Len(Num) – 1 And D LT Len(Num) – 1 Then ‘Bouncy
B = B + 1
Loop Until (B / Answer) = 0.99
Debug.Print Answer; ” Time:”; Timer – T
The usual angle bracket substitutions are in the above. This is me solving a number problem by strings once again. There must be a better insight. Problem 113 wants the number of non-bouncy numbers below a Googol (10100). Going this way, working with strings, my hot rod might be calculating for a week.
…mrt (thinking Googol looks funny spelled that way)