UVa 136. Ugly Numbers

This blog-post is about UVa 136: Ugly Number, a trivial, but interesting UVa problem. The crux involves computing 1500th Ugly number, where a Ugly number is defined as a number whose prime factors are only 2, 3 or 5. Following illustrates a sequence of Ugly numbers:

1,2,3,4,5,6,8,9,10,12,15...

Using F#, we can derive 1500th Ugly Number in F#’s REPL as follows.

seq{1L..System.Int64.MaxValue}
|> Seq.filter (isUglyNumber)
|> Seq.take 1500
|> Seq.last
view raw gistfile1.fs hosted with ❤ by GitHub

In this context, the primary function the determines whether a number is a Ugly number or not–isUglyNumber–is outlined as follows. As we can see, it is a naive algorithm that can be further optimized using memoization (as listed here).

(*
* :a:int64 -> b:bool
*)
let isUglyNumber (x:int64) :bool =
let rec checkFactors (n_org:int64) (n:int64) lfactors =
match n with
| 1L -> true
| _ ->
match lfactors with
| [] -> false
| d::xs ->
if isFactor n d then
checkFactors n_org (n/d) lfactors
elif n > d then
checkFactors n_org n xs
else
false
checkFactors x x [2L;3L;5L]
view raw gistfile1.fs hosted with ❤ by GitHub

After computing the 1500th Ugly number in this manner, we submit the Java source code listed below. For complete source code. please visit this gist. Alternatively, this script is also available at tryfsharp.org for further introspection.

class Main {
public static void main(String[] args) {
System.out.println("The 1500'th ugly number is 859963392.");
}
}
view raw gistfile1.java hosted with ❤ by GitHub

Please leave a comment in case of any question or improvement of this implementation. Thanks.

3 thoughts on “UVa 136. Ugly Numbers”

  1. Pingback: URL

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: