Task — Ugly numbers

You are given an integer $n >= 1. Write a script to find the $nth Ugly Number.

Ugly numbers are those number whose prime factors are 2, 3 or 5. For example, the first 10 Ugly Numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12.

Examples

Input: $n = 7
Output: 8

Input: $n = 10
Output: 12

Analysis

I could see no way of finding ugly[$n] without testing every integer from 1 until the $n-th ugly number is found.

For each candidate number $j I divide it repeatedly by 2 until either the result is 1 - meaning $j is ugly - or non-integer in which case I repeat the exercise dividing by 3 and then 5.

This completes in

• under a second for ugly[100]
• about a second for the last one (ugly[62]) listed in OEIS
• in a few seconds for ugly[500]

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-07-26
use utf8;     # Week 123 - task 1 - Ugly numbers
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

ugly_numbers(7);
ugly_numbers(10);
ugly_numbers(40);
ugly_numbers(62);
ugly_numbers(500);

sub ugly_numbers {
    
    my ($index, $found, $j, $jj, $div, $d);
    
    # initialise
    $index = shift;
    say qq[\nInput:  $index];
    $found = 0;
    
    # search
    J: for $j (1 .. 1e10) {
        $jj = $j;
        
        # try dividing repeatedly by 2, 3 and 5
        D: for $d (2, 3, 5) {
            
            $jj *= $d;
            while ($jj >= 1) {
            
                # divide remaining number by $d
                $jj = $jj / $d;
                
                # result fractional, so undo
                if ($jj != int($jj)) {
                    $jj *= $d;
                    next D;
                    
                # got all factors
                } elsif ($jj == 1) {
                    $found ++;
                    if ($found == $index) {
                        say qq[Output: ugly[$found] = $j];
                        return;
                    }

                    # try next number
                    next J; 
                }
            }
        }
    }
}

last updated 2026-03-05 — 20 lines of code

Output

Input:  7
Output: ugly[7] = 8

Input:  10
Output: ugly[10] = 12

Input:  40
Output: ugly[40] = 144

Input:  62
Output: ugly[62] = 405

Input:  500
Output: ugly[500] = 937500