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

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.

Hi Michael,

I commented out test 7, for other players to check and I added test 8, which gives the same values even if we switch the places of log(2) and log(5). I've tested it with your first solution. Please try again and please like and rate the problem. You my also try my other problems::

https://www.mathworks.com/matlabcentral/cody/players/13897958/created.

Thanks,.