There has to be an approach better than . Iterating through every number takes forever for input like 9999999 1000000. Perhaps a formula for that? A clever DP?

EDIT: I have two pieces of clues that could be hit or miss.

Firstly, on proportion . We are looking for the least number for which the proportion of bouncy numbers is at least . That means we would stop at the first occurrence of answer.

It is clear that every intermediate proportion can also be expressed as a rational fraction , and that because the numerator is at most incremented by one for each step, we should first encounter an answer that is exactly the same as before it is greater than that (EDIT 2: Not True). This is similar to how we would come across zero on the number line when sliding from negative integers to positive integers.

As a result, it is guaranteed that our answer would be divisible by , assuming and have no common divisor other than (when they have, manipulate them). If we have a method to quickly count the occurrences of bouncy numbers below the number , we would save a lot of time by only checking the multiples of .

Secondly, on counting the occurrences of -digit bouncy numbers. This could be a sub-problem of this problem. We can think of it as a stars and bars problem distributing the increase-by-one operators or decrease-by-one operators over the "wall" of the digit placeholders. This reminds me of Google Code Jam Qualification Round 2017 Problem B: Tidy Numbers.

Anyway, by counting all increasing -digit numbers and decreasing -digit numbers separately, we could easily find the number of occurrences that are neither increasing or decreasing (and don't forget about their intersection).

The problem here is that, we could not yet easily count the occurrences of bouncy numbers that is JUST BELOW certain . Perhaps some sort of messy queue can do? Performing some kind of binary search does not work either, as the proportion of bouncy numbers given by, for example, , is definitely not greater than that of .

EDIT 2: Although I've figured out a way to count the occurrences of bouncy numbers below certain (generating the positions of original stars and bars first, and count the posibilities of moving the nine bars left or right, depending on increasing or decreasing numbers and whether you want to do it inclusively or subtractively. I chose to be inclusive for increasing numbers and subtractive for decreasing numbers, both moving the bars to the right), now that I think it through, it is not necessarily true that the proportion has to be equivalent to before exceeding it (e.g. the answer for 50 101 is 519, which is not a multiple of ).

It appears to be true for a lot of input, though. It's somewhat alluring when you see that is a multiple of . For those where this is true, it's also funny to discover the result for 394 395 and 395 396 are sharing the same multiplier , and the same for 396 397 and 397 398. The multiplier has an increasing trend. You might work your way up to see if a sequence is out there.