Problem 53725. Easy Sequences 56: Counting "Ugly" Numbers

Hi Ramon,
It's a nice problem, but I had an issue with test 7. One or two of the values come out slightly differently, and depend on the base of the logarithm that is used..

Hi William,
There was rounding-off issues because I precomputed some logs. It's corrected now. Please like and rate the problem. Thanks.

I think your test suite is still incorrect. In test 7, you report regCount(75,85) as 6815143. It is actually 6815144. I suspect that you're failing to count 3^85*5^170, which happens to exactly equal 75^85. Since the problem statement says to count all ugly numbers less than or equal to n^e, this value should be counted.

We basically use the same algorithm but our answers differ not only in 75^85 but also in 2^100, 18^28, etc.

We are not actually enumerating ugly numbers here, therefore I think it's not a matter of failing to count, but about floating-point number precision.

Using your algorithm and plugging more precise values of logarithms (log(2)=0.6931471805599453094172321214582, log(3)=1.0986122886681096913952452369225, log(5) = 1.6094379124341003746007593332262 and log(75) = 4.3174881135363104405967639033749), you will get regCount(75,85) = 6815143.

The only difference between our algorithm is that I used less computation. Most of the time, we lose precision going through too many calculations. Please try to interchange "log(2)' and 'log(5)' to shorten the length of the 'for' loops which would lessen the number of calculations.

Hello Ramon,

First, I'm not sure you can say that the values you are using are more precise than log(2), for example. log(2) should return a value that is precise to within the precision of the machine. In fact, if I type in
log(2)-0.6931471805599453094172321214582
on my machine, the result is identically 0. I agree that precomputing these values once will make the code more efficient, but not more precise.

As for switching the log(5) and log(2) order, again you are correct that this will make the code more efficient, but in this case I think it makes it less accurate. Let me explain. I hope I'm not giving away too much of the answer with my comment.

At the point where you are trying to calculate the max exponent for 3, you are subtracting a multiple of log(5) from a large value, and then dividing by log(3). Because log(5) is larger than log(3), you are increasing the likelihood that this calculation will result in a rounding error. In my algorithm, I'm subtracting a multiple of log(2) from a large value, and then dividing by log(3). Because log(2) is smaller than log(3), the likelihood of a rounding error is less (but still probably not 0).

As proof, try to set a breakpoint in your code at the point where your 5-exponent is 170. I think you'll find that the calculated maximum exponent for 3 is 84, when it should actually be 85. As I had guessed in my original comment, your algorithm is missing 3^85*5^170.