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
Do
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
End If
If Mid(Num, j, 1) GTE Mid(Num, j + 1, 1) Then ‘Decreasing
D = D + 1
End If
If I != j And D != j Then Exit For
Next j
If I LT Len(Num) – 1 And D LT Len(Num) – 1 Then ‘Bouncy
B = B + 1
End If
Loop Until (B / Answer) = 0.99
Debug.Print Answer; ” Time:”; Timer – T
End Sub
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)
Michael, one answer may be to skip big chunks of numbers. For example, if you are looking at the number 24510000, then clearly the next 45554 numbers are going to be bouncy, until you get to 24155555. It may take some twisted logic to achieve, but would save heaps of time.
dermotb is on the right track. Bounciness is recursive. Let letters be decimal digits, then if cba is bouncy, so is dcba, edcba, fedcba, etc as well as cbaz, cbazy, cbazyx etc. And so are abc, abcd, abcde, abcdef, zabc, yzabc, xyzabc, etc.
Actually, given abc distinct digits with a less than b less than c, the permutations acb, bac, bca and cab are bouncy, so 2/3 of 3-digit numbers with 3 distinct digits are bouncy. With 2 distinct numbers aab, the permutation aba is bouncy while aab and baa aren’t, so 1/3 of 3-digit numbers with 2 distinct digits are bouncy. No 3-digit numbers with all digits the same are bouncy.
Generalize to permutations of more numbers.