# Nth K-Ugly Number

Write the shortest code in any language of your choice to find the $$\N\$$th $$\K\$$-ugly number.

A $$\K\$$-ugly number is a number whose only prime factors are the prime numbers $$\\le K\$$. $$\K\$$-ugly number's are popularly known as $$\K\$$-smooth numbers.

Constraints:

• $$\0 < N < 1000\$$

• $$\0 < K < 25\$$

Input:

• N K (separated by a single space)

Output:

• -1 (if no such number exists)
or
• $$\M\$$ (if $$\N\$$th $$\K\$$-ugly number is $$\M\$$)
• These numbers are usually referred to as k-smooth. Commented Oct 18, 2013 at 11:52
• @primo hahaha.. thats funny. I never knew about k-smooth Commented Oct 18, 2013 at 12:02
• You should exclude k=1. Commented Oct 18, 2013 at 13:20
• Commented Oct 18, 2013 at 14:03
• May we assume a largest output? For example N=1000, K=2 gives 5.357543 x 10^300. Commented Oct 19, 2013 at 3:50

# Mathematica 82 72 70

n_~u~k_:=(c=m=1;While[m <= n,If[FactorInteger[c][[-1,1]]<=k,m++];c++];c-1)


Usage

u[1, 5]
u[5, 2]
u[20, 3]
u[57, 5]
u[66, 13]
u[100, 5]
u[1000, 25]


1
16
96
324
110
1536
5474

Prime factors and their powers are in the center column.

Table[{t, FactorInteger[t], u[t, 5]}, {t, 15}] // Grid


• n_~u~k_:= OMG! you made my day :) Commented Oct 19, 2013 at 0:12
• c=1;m=1; can be replaced with c=m=1; Commented Oct 19, 2013 at 5:19
• @alephalpha Yes. Good catch. Commented Oct 19, 2013 at 11:07

## Python 2 - 63 bytes

i=t=1
n,k=input()
while~-n:i+=1;t*=i>k or i**n;n-=t%i<1
print i


Input is taken from stdin, comma separated.

Sample usage:

$echo 1, 5 | python nth-k-smooth.py 1$ echo 5, 2 | python nth-k-smooth.py
16

$echo 20, 3 | python nth-k-smooth.py 96$ echo 57, 5 | python nth-k-smooth.py
324

$echo 66, 13 | python nth-k-smooth.py 110$ echo 100, 5 | python nth-k-smooth.py
1536

$echo 1000, 25 | python nth-k-smooth.py 5474  At N = 1000, the script has a reasonable execution time for all values K ≥ 7. For the input N = 1000, K = 2 the correct answer is 2999 ≈ 5.357543300·10300. Using an "increase by one" approach, as David Carraher's answer also does, it would take longer than the age of the universe to reach this value (considerably longer!). • syntax error at "n,k=input()" Commented Oct 19, 2013 at 4:53 • The script is written for Python 2. Commented Oct 19, 2013 at 4:56 • mine is Python 2.7.3, shouldn't it work? i m noob :) Commented Oct 19, 2013 at 5:03 • Hah. This is shorter than the sage solution I'd come up with, using built-ins... problem being that they've got lotsa letters to be user-friendly: x.prime_divisors()... ugh Commented Oct 21, 2013 at 16:46 • you never use that j Commented Oct 21, 2013 at 19:23 ## APL(Dyalog), 38 {⍵≡1:¯1⋄⊃⌽⍺{0~⍨⍺↑y[⍋y←∪,⍵∘.×⍵]}⍣≡⍳⍵}/⎕  Finally, for once, APL has beaten GS!! Sample ⎕: 5 3 6 ⎕: 20 5 36 ⎕: 500 20 2028 ⎕: 50 1 ¯1  Explanation /⎕ Takes evaluated input (space-seperated numbers are interpreted as numerical array) and insert a function in between (reduce). ⍵≡1: If right argument (k) is 1 ¯1 return -1 (¯ is the high-minus, APL's way of representing negative numbers) ⋄ Statement seperator used as else. ⍳⍵ Generate a numerical array from 1 to k ⍺{...}⍣≡ Recursively apply function until output of an iteration is the same as that of the last iteration (fixpoint), passing the left argument of outer function (N) as the left each iteration. ⍵∘.×⍵ Outer product of the left argument with itself (generating a multiplication table) , Unravel the matrix to numerical array ∪ Remove duplicates y[⍋y←...] Sort ⍺↑ Get the first N values (fills 0s if shorter than N) 0~⍨ Remove 0s In short, ⍺{0~⍨⍺↑y[⍋y←∪,⍵∘.×⍵]}⍣≡⍳⍵ generates the first N k-smooth numbers ⊃⌽ get last value ### GolfScript, 42 characters ~),2>{:s,2>{s\%!},!},:^1+1+{$({*}+^%|}@*0=


Unfortunately, I had to insert several correction terms to get the indexing correct.

Examples:

> 5 2
16

> 20 3
96

> 66 13
110

> 1000 25
5474


## R 133 characters

a=scan(n=2)
k=1:a[2]
i=m=0
while(m<a[1]){i=i+1;if(all(sfsmisc::factorize(i)[[1]][,1]%in%k[rowSums(!outer(k,k,%%))<3]))m=m+1}
cat(i)


Explanation:

k[rowSums(!outer(k,k,%%))<3]: k being here the sequence from 1 to K, this piece of code outputs the list of primes smaller or equal to K.
all(sfsmisc::factorize(i)[[1]][,1]%in%k[rowSums(!outer(k,k,%%))<3]): this checks that all of the primes used to factorize a number belong to the previous list. It uses a function from package sfsmisc that performs the prime factorization.

• these brackets around m=m+1 are not necessary. Commented Oct 19, 2013 at 21:35

## Mathematica, 96 characters

{n,k}=%~Read~{Number,Number};If[n>k==1,-1,While[p<n,m++;If[Max@FactorInteger[m][[All,1]]<=k,p++]];m]


Ungolfed:

{n, k} = % ~Read~ {Number, Number};
If[n > k == 1,
-1,
While[p < n,
m++;
If[Max@FactorInteger[m][[All, 1]] <= k, p++]
]; m
]


I did manage to find a shorter solution, more in the spirit of Mathematica's functional programming style by avoiding the while-loop, but it runs out of memory without an upper bound on M. It also cheats on the space-seperated input, but I thought it was elegant (60 characters):

Select[Range@999,Max@FactorInteger[#][[All,1]]<=k&][[n]]~Check~-1


# Ruby 1.9+, 101 chars

Sort of verbose but nice and functional:

require'Prime'
n,k=gets.split.map &:to_i
p (1..5474).select{|i|i.prime_division.all?{|j,l|j<=k}}[n-1]

edit:

The number constant 5474 represents the highest value the program will ever output (upper bound), and is the answer to N = 1000, K = 2. As Primo points out, this may be a little low.

If you for some reason would like to run this program, the upper bound can be changed to whatever you want. Increasing it by a few digits will however increase execution time dramatically1, even for small outputs.

A feature I find quite neat is that the program cleanly outputs nil if the output would exceed the upper bound.

• 5474 (the result of N = 1000, K = 23-28) as an upper bound might be a bit low. For example, N = 1000, K = 7 -> 385875. Commented Oct 22, 2013 at 8:01
• @primo I totally agree. Added some clarification. Commented Oct 22, 2013 at 16:29