1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
shows the first 11 ugly numbers. By convention, 1 is included.
How can I find out if a number is an ugly number?
Thanks!
Umm.. How about looking at its prime factorization?
Mats Faugli wrote:
>
> How can I find out if a number is an ugly number?
Factor the number. Or better yet, keep dividing by 2, 3, 5 until one can
divide no longer. If the number you are left with is 1 the number you
started with is ugly.
Bob Kolker
See if the only prime factors are 2, 3 or 5.
>Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The
>sequence
>How can I find out if a number is an ugly number?
Didn't you just tell us?
Doug
- 1 is ugly
- all numbers ending with 0,2,4,5,6,8 are ugly
- all numbers whose sum of its digits is a multiple of 3, is ugly
And, just if case this kind of thing worries you, this process is
entirely computable. (cf. eg. Cutland, Computability).
I think you just misunderstand the poster's meaning.
> "Mats Faugli" <matsf...@hotmail.com> wrote in message
> news:ULc8a.28012$CG6.4...@news4.e.nsc.no...
>> Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The
>> sequence
>>
>>
>> 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
>>
>>
>>
>> shows the first 11 ugly numbers. By convention, 1 is included.
>>
>>
>> How can I find out if a number is an ugly number?
> - 1 is ugly
By definition, not by convention.
> - all numbers ending with 0,2,4,5,6,8 are ugly
No. A counterexample is 14.
> - all numbers whose sum of its digits is a multiple of 3, is ugly
No. A counterexample is 21.
--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
Thanks! This answer helped me a lot!
qo|=<):
"Mats Faugli" <matsf...@hotmail.com> wrote in message
news:ULc8a.28012$CG6.4...@news4.e.nsc.no...
No. An ugly number has ONLY 2, 3, and 5 as prime factors. 2*7 = 14
ends in 4 but is not ugly!
Darren
>I think you just misunderstand the poster's meaning.
Is that so? Enlighten us, then.
Doug
I used to think that 162 was an ugly number, but then I got to know it
better...
ML
But this is clearly a misunderstanding of the definition of an ugly number,
since this only checks if a number has factors of 2, 3, or 5. It doesn't
ensure that there aren't other prime factors.
A chapter in Dijkstra's wonderful book "A Discipline of Programming"
is devoted to "A Problem of Hamming". This problem is to
generate the numbers which are divisible by only powers
(0th power included) of 2, 3, or 5 - in other words, your
"ugly numbers". He develops an algorithm for doing this.
If I remember to, I will look this up tomorrow,
Martin Cohen
BTW, why did you choose to call them "ugly"? I think they
are rather nice.
The algorithm is very simple. However, when (say) finding the
3,000th ugly number, it slows down quite a bit. I had to resort
to various tricks to speed it up. I'd like to see Dijkstra's
algorithm --- just to see if it's elegant one or a pratical one
(of course, it may be both). _____________________________Gerard S.
It is easy to test a binary number for divisibility by 2, 3, or 5.
Divisibility by 2 depends on just the last bit. 3 is 11 in base 2 so
you use an alternating sum of bits. 5 is 101 base 2 so you use an
alternating sum of pairs of bits.
--OL
I expect Martin Cohen will have more comments tomorrow on Dijkstra's
formulation. Here are the important points in it:
"Axiom 2. If x is in the sequence, so are 2*x, 3*x, and 5*x."
The algorithm starts 3 sequence indices, i2, i3, i5 at 1,1,1,
and 3 values, x2, x3, x5 at 2, 3, 5. It repeatedly delivers the
least of x2, x3, x5, say xi. If any of x2, x3, x5 is not more
than xi, update to 2, 3, or 5 times the next-indexed entry in
sequence and advance index.
I appear to be a little dense in understanding the wording here.
I understand everything up to delivers...
what is the next-indexed entry in the sequence? Are there only
three sequences, each with one number, or does each sequence have
more and more entries in it?
I don't understand what "update to" means. What is updated ?
What does advance the index mean? Which index?
Maybe somebody can clarify this for me. ________________Gerard S.
Values are stored in an array, aq, as they are generated. The
three indices point into the array such that x2 = 2*aq[i2],
x3 = 3*aq[i3], etc. after any update.
Example: i2,i3,i5,x2,x3,x5 = 1,1,1,2,3,5, aq=1.
Now min(x2,x3,x5) is 2 so set aq=1,2 i2=2, x2=4.
Now min(x2,x3,x5) is 3 so set aq=1,2,3 i3=2, x3=6.
Now min(x2,x3,x5) is 4 so set aq=1,2,3,4 i2=3, x2=6.
Now min(x2,x3,x5) is 5 so set aq=1,2,3,4,5 i5=2, x5=10.
Etc.
so
Thank you!|! It's all very clear now. Thanks again for your
eludication. __________________________________________________Gerard S.
ah, you are right, I missed that.