help
Kyle Masters
sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 1000'th ugly number.
----------------------------------
does anyone know how to do that?
Joe Seigh
Wrong newsgroups. Try alt.homework
Joe Seigh
William Elliot
> 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.
>
The first beautiful numbers are 7, 11.
> Write a program to find and print the 1000'th ugly number.
> does anyone know how to do that?
>
Start at 2 and continue to find ugly numbers until you've 1000 of your
darlings. Divide the number by 2 until you get a nonzero remainder.
Then divide the number by 3 until you get a nonzero remainder.
Last divide the number by 5 until you get a nonzero remainder.
If the result is 1, then it's ulgy. Otherwise it's beautiful.
That's how, so get to work and write that ulgy program.
You may want tables of powers of 2,3,5.
Will Twentyman
How would you construct an ugly number? How would you sort them?
Or, how do you tell if a number is an ugly number?
--
Will Twentyman
email: wtwentyman at copper dot net
Corey Murtagh
I daresay a large number of people in the MANY groups you cross-posted
this to know how, or could figure out how with just a few minutes thought.
The question is, why should we do your homework for you?
--
Corey Murtagh
The Electric Monk
"Quidquid latine dictum sit, altum viditur!"
Gerry Quinn
Write a function that detects whether a given number is ugly.
Write a function that steps through the natural numbers,
determining whether the current natural number is ugly and counting ugly
numbers so far, until 1000 ugly numbers are reached.
Print the current natural number.
And that's more than enough help for you...
Gerry Quinn
--
http://bindweed.com
Screensavers and Games for Windows
Download free trial versions
New arcade-puzzler just out - "Volcano"
Bill Godfrey
"Kyle Masters" <ne...@theSpear.net> wrote:
<snip>
> Write a program to find and print the 1000'th ugly number.
You want a complete program that you can just print out and hand in? Sure
thing!
#include <stdio.h>
int main(void)
{
puts("51200000");
}
Oh wait, you wanted the program to *find* and print the 1000'th number.
#include <stdio.h>
#define ONE_THOUSANDTH_UGLY_NUMBER 51200000
int main(void)
{
long i;
while (1)
{
if (i == ONE_THOUSANDTH_UGLY_NUMBER)
{
printf("Answer is %ld.\n",i);
break;
}
}
return 0;
}
Bill, trying to be helpful. (Read Gerry's article elsewhere for better
help.)
--
The address in the reply to header is correct, but I'll
read it quicker if you drop the word "usenet".
gerard46
| 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.
|
| Write a program to find and print the 1000'th ugly number.
| does anyone know how to do that?
Yes, the method isn't intuitively obvious.
Here is a REXX program that displays the Nth (Xth) UGLY number.
No checks are made here for the value of X or it's correctness
(if it is numeric or negative, for example).
_________________________________________________________________
/**/ parse arg n . /*display the Nth ugly number.*/
numeric digits 2000 /*handle up to a couple thousand digits.*/
z=1 /*first UGLY number.*/
fa=1
fb=1
fc=1
u.1=1 /*stemmed array of UGLY numbers.*/
do #=2 to n
a=2*u.fa
b=3*u.fb
c=5*u.fc
z=min(a,b,c)
u.#=z
if a<=z then fa=fa+1
if b<=z then fb=fb+1
if c<=z then fc=fc+1
end
say z /*display the Nth UGLY number.*/
____________________________________________________________________
I hope everyone can understand the program without explaining the
REXX language. The only thing is stemmed arrays. REXX uses (in
this case) u.10 to get the 10th "element" in the U array, where
most languages would use u(10). ________________________Gerard S.
Kyle Masters
just something i want to know how to do
--
-- www.theSpear.net --
-- www.Webmaster-Forum.net
"Corey Murtagh" <em...@slingshot.co.nz.no.uce> wrote in message
news:10679389...@radsrv1.tranzpeer.net...
Corey Murtagh
Kyle Masters wrote:
>> "Corey Murtagh" <em...@slingshot.co.nz.no.uce> wrote in message news:10679389...@radsrv1.tranzpeer.net...
>
>>> 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.
>>>
>>>
>>> Write a program to find and print the 1000'th ugly number.
>>> ----------------------------------
>>> does anyone know how to do that?
>>
>> I daresay a large number of people in the MANY groups you cross-posted
>> this to know how, or could figure out how with just a few minutes thought.
>>
>> The question is, why should we do your homework for you?
>
> its not homework.. im not even taking any computer programming class.. its
> just something i want to know how to do
Your original question is indistinguishable from the many homework
questions we get. And we get lots of people who claim "It's not
homework!" Your statements have failed to convince me.
And really, this is not exactly the kind of problem you'd expect someone
to be actually /interested/ in solving. Now if it was "nth prime" or
"nth factorial" for example, that would be interesting. Or any of a
thousand other simple problems (some more, some less than the above) in
mathematics, engineering, physics, etc. This one just looks like homework.
Richard Heathfield
Corey Murtagh wrote:
> Now if it was "nth prime" or
> "nth factorial" for example, that would be interesting.
Um, no. The nth prime is 13, and n! is 720. Neither of these numbers is
terribly exciting.
--
Richard Heathfield : bin...@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
Robert STRANDH
> /**/ parse arg n . /*display the Nth ugly number.*/
> numeric digits 2000 /*handle up to a couple thousand digits.*/
> z=1 /*first UGLY number.*/
> fa=1
> fb=1
> fc=1
> u.1=1 /*stemmed array of UGLY numbers.*/
>
> do #=2 to n
> a=2*u.fa
> b=3*u.fb
> c=5*u.fc
> z=min(a,b,c)
> u.#=z
> if a<=z then fa=fa+1
> if b<=z then fb=fb+1
> if c<=z then fc=fc+1
> end
>
> say z /*display the Nth UGLY number.*/
Very nice!
Here is a version (in Common Lisp) that uses the same method, but that
is probably faster. I don't think you can extend a vector in constant
time, and I avoid that by using lists instead. My version also uses
much less memory since I throw away the numbers that are no longer
needed. I also use only one multiplication per iteration:
(defun find-ugly (n)
(loop with a = 2 and b = 3 and c = 5
with ugly = 1
with l = (list nil)
with fa = l and fb = l and fc = l
repeat (1- n) do
(setf ugly (min a b c))
(setf (car l) ugly)
(push nil (cdr l))
(pop l)
(when (<= a ugly) (setf a (* 2 (pop fa))))
(when (<= b ugly) (setf b (* 3 (pop fb))))
(when (<= c ugly) (setf c (* 5 (pop fc))))
finally (return ugly)))
It only takes a few seconds to computer the one-millionth ugly number:
* (find-ugly 1000000)
519312780448388736089589843750000000000000000000000000000000000000000000000000000000
--
Robert Strandh
---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------
Richard Harter
wrote:
[snip code]
Just as a note, the amortized cost of vector extension is constant per
element. If one is concerned about speed, one may as well preallocate
n locations (for the n'th ugly number) since the memory requirement is
O(n) anyway.
folloups set to comp.programming
Richard Harter, c...@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
"We have people from every planet on the earth in this State."
-- California Governor Gray Davis
Dirk Thierbach
> Here is a version (in Common Lisp) that uses the same method, but that
> is probably faster. I don't think you can extend a vector in constant
> time, and I avoid that by using lists instead.
It's actually a bit more elegant to use streams (lazy lists) and do
an ordered merge on them. BTW, this is exercise 3.56 in 'Structure and
Interpretation of Computer Programs' (SICP). The original problem
is due to R. Hamming.
So it very likely *is* a homework question :-)
- Dirk
[F'up to poster -- this is crossposting through too many NGs, and I don't
read comp.programming, which would probably be the best candidate for
a follow-up.]