7
\$\begingroup\$

Write the shortest code in any language of your choice to find the Nth K-ugly number.

A K-ugly number is a number whose only prime factors are the prime numbers <= K. This K-ugly number is popularly known as a K-smooth number.

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 Nth K-ugly number is M)
\$\endgroup\$
  • 1
    \$\begingroup\$ These numbers are usually referred to as k-smooth. \$\endgroup\$ – primo Oct 18 '13 at 11:52
  • \$\begingroup\$ @primo hahaha.. thats funny. I never knew about k-smooth \$\endgroup\$ – Coding man Oct 18 '13 at 12:02
  • 3
    \$\begingroup\$ You should exclude k=1. \$\endgroup\$ – Howard Oct 18 '13 at 13:20
  • 1
    \$\begingroup\$ Related: stackoverflow.com/questions/4600048/nth-ugly-number/… \$\endgroup\$ – DavidC Oct 18 '13 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 '13 at 3:50
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\$
  • \$\begingroup\$ n_~u~k_:= OMG! you made my day :) \$\endgroup\$ – Dr. belisarius Oct 19 '13 at 0:12
  • \$\begingroup\$ c=1;m=1; can be replaced with c=m=1; \$\endgroup\$ – alephalpha Oct 19 '13 at 5:19
  • \$\begingroup\$ @alephalpha Yes. Good catch. \$\endgroup\$ – DavidC Oct 19 '13 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\$
  • \$\begingroup\$ syntax error at "n,k=input()" \$\endgroup\$ – Coding man Oct 19 '13 at 4:53
  • \$\begingroup\$ The script is written for Python 2. \$\endgroup\$ – primo Oct 19 '13 at 4:56
  • \$\begingroup\$ mine is Python 2.7.3, shouldn't it work? i m noob :) \$\endgroup\$ – Coding man Oct 19 '13 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 '13 at 16:46
  • 1
    \$\begingroup\$ you never use that j \$\endgroup\$ – boothby Oct 21 '13 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\$
  • \$\begingroup\$ these brackets around m=m+1 are not necessary. \$\endgroup\$ – flodel Oct 19 '13 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\$
  • \$\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 '13 at 8:01
  • \$\begingroup\$ @primo I totally agree. Added some clarification. \$\endgroup\$ – daniero Oct 22 '13 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.