7
\$\begingroup\$

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\$)
\$\endgroup\$
7
  • 1
    \$\begingroup\$ These numbers are usually referred to as k-smooth. \$\endgroup\$
    – primo
    Oct 18, 2013 at 11:52
  • \$\begingroup\$ @primo hahaha.. thats funny. I never knew about k-smooth \$\endgroup\$
    – Coding man
    Oct 18, 2013 at 12:02
  • 3
    \$\begingroup\$ You should exclude k=1. \$\endgroup\$
    – Howard
    Oct 18, 2013 at 13:20
  • 1
    \$\begingroup\$ Related: stackoverflow.com/questions/4600048/nth-ugly-number/… \$\endgroup\$
    – DavidC
    Oct 18, 2013 at 14:03
  • 2
    \$\begingroup\$ May we assume a largest output? For example N=1000, K=2 gives 5.357543 x 10^300. \$\endgroup\$
    – primo
    Oct 19, 2013 at 3:50

7 Answers 7

4
\$\begingroup\$

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

data

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

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!).

\$\endgroup\$
8
  • \$\begingroup\$ syntax error at "n,k=input()" \$\endgroup\$
    – Coding man
    Oct 19, 2013 at 4:53
  • \$\begingroup\$ The script is written for Python 2. \$\endgroup\$
    – primo
    Oct 19, 2013 at 4:56
  • \$\begingroup\$ mine is Python 2.7.3, shouldn't it work? i m noob :) \$\endgroup\$
    – Coding man
    Oct 19, 2013 at 5:03
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – boothby
    Oct 21, 2013 at 16:46
  • 1
    \$\begingroup\$ you never use that j \$\endgroup\$
    – boothby
    Oct 21, 2013 at 19:23
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ these brackets around m=m+1 are not necessary. \$\endgroup\$
    – flodel
    Oct 19, 2013 at 21:35
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – primo
    Oct 22, 2013 at 8:01
  • \$\begingroup\$ @primo I totally agree. Added some clarification. \$\endgroup\$
    – daniero
    Oct 22, 2013 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.