A positive integer x is called a regular number, if and only if there exist a non-negative integer k, such that 
. For some reason, such a number is also refered to as an ugly number. Below are the first few regular numbers:
. For some reason, such a number is also refered to as an ugly number. Below are the first few regular numbers:
It turns out that regular numbers are not so regular after all. In fact, regular numbers are quite rare. There are only 
regular numbers 
and just 
regular numbers 
.
regular numbers and just regular numbers .Given an integer n, and exponent e, we are tasked to write a function that counts the number of regular numbers less than or equal to 
.
.Solution Stats
Problem Comments
8 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers6
Suggested Problems
-
1344 Solvers
-
243 Solvers
-
Determine if input is a Narcissistic number
216 Solvers
-
Compute the nth term from the golden sieve
19 Solvers
-
171 Solvers
More from this Author116
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
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.
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,.
Hmm... the test suite has the wrong answer, but it appears to be MATLAB's fault. It appears that in test case 8, when called with 9 and 100, the "successful" solutions miss 9^100 as an ugly number, which it clearly is. It appears to be an issue with the colon operator.
Here's an easy way to isolate the error:
>> 199:100*log(9)/log(3)
ans =
199.0000 200.0000
>> ans(end)-200
ans =
2.8422e-14
>>
Just the fact that the first answer is showing floating point numbers is a clue, but the second one should clearly return 0, or -1 if the roundoff error between log(9) and log(3) had gone the other way.
I posted a bug report and was told it was a feature. I did a bit of push back, and they agreed that the documented behavior and the actual differ, and to take on a fix for a future update or release. Not clear whether they'll fix the behavior or change the documentation.