Problem 53725. Easy Sequences 56: Counting "Ugly" Numbers
Solution Stats
Problem Comments

6 Comments
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 roundingoff 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 floatingpoint 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 5exponent 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,.
Problem Recent Solvers5
Suggested Problems

1298 Solvers

109 Solvers

141 Solvers

615 Solvers

Compute the Sequence of the Day
10 Solvers
More from this Author66
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!