Ugly numbers
Mats Faugli
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?
Thanks!
Zachary Turner
"Mats Faugli" <matsf...@hotmail.com> wrote in message
news:ULc8a.28012$CG6.4...@news4.e.nsc.no...
Umm.. How about looking at its prime factorization?
Robert Kolker
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
Mike Varney
See if the only prime factors are 2, 3 or 5.
Doug Norris
>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
username
- 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
Adam Booth
And, just if case this kind of thing worries you, this process is
entirely computable. (cf. eg. Cutland, Computability).
Zhiqiang Zhang
"username" <e-mail@adress> write:3e61d234$0$49104$e4fe...@news.xs4all.nl...
I think you just misunderstand the poster's meaning.
Dave Seaman
> "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>
Mats Faugli
"Robert Kolker" <bobk...@attbi.com> skrev i melding
news:3E6160FD...@attbi.com...
Thanks! This answer helped me a lot!
qo|=<):
Prai Jei
"Mats Faugli" <matsf...@hotmail.com> wrote in message
news:ULc8a.28012$CG6.4...@news4.e.nsc.no...
Darren G. Lorent
> "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
> - all numbers ending with 0,2,4,5,6,8 are ugly
No. An ugly number has ONLY 2, 3, and 5 as prime factors. 2*7 = 14
ends in 4 but is not ugly!
Darren
Doug Norris
>I think you just misunderstand the poster's meaning.
Is that so? Enlighten us, then.
Doug
Moufang Loop
I used to think that 162 was an ugly number, but then I got to know it
better...
ML
Zachary Turner
"Doug Norris" <norr...@rintintin.colorado.edu> wrote in message
news:norrisdt....@rintintin.colorado.edu...
factors are 2, 3, and 5. The next poster said that a number is ugly if:
1) The last digit is even
OR
2) The sum of digits is 3
OR
3) The last digit is 5
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.
Martin Cohen
is at work and I am not:
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.
GerardS
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.
Oscar Lanzi III
successively by 3 until the result is not a multiple of 3. Then divide
successively by 5 until the result is not a multiple of 5. Iff the
final quotient is 1, the number is ugly and moreover you have determined
its prime factorization.
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
James Waldby
> | Martin Cohen wrote:
> |> Mats Faugli wrote:
> |> 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.
> | A chapter in Dijkstra's wonderful book "A Discipline of Programming"
> | is devoted to "A Problem of Hamming".
> I'd like to see Dijkstra's
...
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.
GerardS
---snipped---
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.
James Waldby
>
> | James Waldby wrote:
> ---snipped---
> |> GerardS wrote:
> |>| Martin Cohen wrote:
> |>|> Mats Faugli wrote:
> |>|> 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.
> |...
> |>| A chapter in Dijkstra's wonderful book "A Discipline of Programming"
> |>| is devoted to "A Problem of Hamming".
> |...
> |> I'd like to see Dijkstra's
> |> algorithm --- just to see if it's elegant one or a practical one
> |...
>
> | 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.
> 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?
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
GerardS
----snipped----
|>| James Waldby wrote:
|> ---snipped---
|>|>| Martin Cohen wrote:
|>|>|> Mats Faugli wrote:
|>|>|> 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.
|>|...
|>|>| A chapter in Dijkstra's wonderful book "A Discipline of Programming"
|>|>| is devoted to "A Problem of Hamming".
|>| 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.
| 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.
Thank you!|! It's all very clear now. Thanks again for your
eludication. __________________________________________________Gerard S.
username
>
> "Doug Norris" <norr...@rintintin.colorado.edu> wrote in message
> news:norrisdt....@rintintin.colorado.edu...
> > "Zhiqiang Zhang" <zz...@163.com> writes:
> >
> > >I think you just misunderstand the poster's meaning.
> >
> > Is that so? Enlighten us, then.
> >
> > Doug
> >
> >
> It's true. The original poster said a number is ugly if the _only_ prime
> factors are 2, 3, and 5.
ah, you are right, I missed that.