Generate n-ary numbers

Question

A secondary number is a positive integer whose prime factors (without multiplicity) are all less than or equal to its square root. 4 is a secondary number, because its only prime factor is 2, which equals its square root. However, 15 is not a secondary number, because it has 5 as a prime factor, which is larger than its square root (~ 3.9). Because all prime numbers have themselves as prime factors, no prime number is a secondary number. The first few secondary numbers are as follows:

1, 4, 8, 9, 12, 16, 18, 24, 25, 27, 30, 32, 36, 40, 45, 48, 49, 50, 54, 56

A tertiary number is defined similarly, except all the prime factors must be less than or equal to its cube root. The first few tertiary numbers are as follows:

1, 8, 16, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 125, 128, 135, 144, 150, 160, 162

In general, an n-ary number is one whose prime factors are all less than or equal to its n-th root. Thus, a positive integer \$x\$ is an n-ary number iff each of its prime factors \$p\$ satisfies \$p^n ≤ x\$. Thus, primary numbers are all positive integers (all prime factors less than or equal to themselves), quartenary numbers have all their prime factors less than or equal to their fourth root, and so on.

The Challenge

Given integers k and n as inputs, output the kth n-ary number. k may either be zero- or one-indexed (your choice), and n will always be positive.

Examples

These are the first 20 elements in each sequence up to 10-ary numbers:

Primary: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Secondary: 1, 4, 8, 9, 12, 16, 18, 24, 25, 27, 30, 32, 36, 40, 45, 48, 49, 50, 54, 56
Tertiary: 1, 8, 16, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 125, 128, 135, 144, 150, 160, 162
Quarternary: 1, 16, 32, 64, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512
5-ary: 1, 32, 64, 128, 243, 256, 288, 324, 384, 432, 486, 512, 576, 648, 729, 768, 864, 972, 1024, 1152
6-ary: 1, 64, 128, 256, 512, 729, 768, 864, 972, 1024, 1152, 1296, 1458, 1536, 1728, 1944, 2048, 2187, 2304, 2592
7-ary: 1, 128, 256, 512, 1024, 2048, 2187, 2304, 2592, 2916, 3072, 3456, 3888, 4096, 4374, 4608, 5184, 5832, 6144, 6561
8-ary: 1, 256, 512, 1024, 2048, 4096, 6561, 6912, 7776, 8192, 8748, 9216, 10368, 11664, 12288, 13122, 13824, 15552, 16384, 17496
9-ary: 1, 512, 1024, 2048, 4096, 8192, 16384, 19683, 20736, 23328, 24576, 26244, 27648, 31104, 32768, 34992, 36864, 39366, 41472, 46656
10-ary: 1, 1024, 2048, 4096, 8192, 16384, 32768, 59049, 62208, 65536, 69984, 73728, 78732, 82944, 93312, 98304, 104976, 110592, 118098, 124416

Answer 1

Jelly, 12 bytes

Æf*³<‘Ạ
1Ç#Ṫ

Takes n and k (one-indexed) as command-line arguments.

Try it online!

How it works

1Ç#Ṫ     Main link. Left argument: n. Right argument: k

1        Set the return value to 1.
 Ç#      Execute the helper link above for r = 1, 2, 3, ... until k of them return
         a truthy value. Yield the list of all k matches.
   Ṫ     Tail; extract the last match.


Æf*³<‘Ạ  Helper link. Argument: r

Æf       Compute all prime factors of r.
  *³     Elevate them to the n-th power.
    <‘   Compare all powers with r + 1.
      Ạ  All; return 1 if all comparisons were true, 0 if one or more were not.

Answer 2

Brachylog, 21 bytes

:[1]cyt
,1|,.$ph:?^<=

Try it online!

This answer is one-indexed.

Explanation

Input: [N:K]

:[1]cy              Retrieve the first K valid outputs of the predicate below with N as input
      t             Output is the last one

,1                  Output = 1
  |                 Or
   ,.$ph            Take the biggest prime factor of the Output
        :?^<=       Its Nth power is less than the Output

Answer 3

JavaScript (ES7), 95 90 bytes

Reasonably fast but sadly limited by the maximum number of recursions.

f=(k,n,i=1)=>(F=(i,d)=>i-1?d>1?i%d?F(i,d-1):F(i/d,x):1:--k)(i,x=++i**(1/n)|0)?f(k,n,i):i-1

How it works

Rather than factoring an integer i and verifying that all its prime factors are less than or equal to x = floor(i^1/n), we try to validate the latter assumption directly. That's the purpose of the inner function F():

F = (i, d) =>         // given an integer i and a divisor d:
  i - 1 ?             //   if the initial integer is not yet fully factored
    d > 1 ?           //     if d is still a valid candidate
      i % d ?         //       if d is not a divisor of i
        F(i, d - 1)   //         try again with d-1 
      :               //       else
        F(i / d, x)   //         try to factor i/d
    :                 //     else
      1               //       failed: yield 1
  :                   //   else
    --k               //     success: decrement k

We check if any integer d in [2 ... i^1/n] divides i. If not, the assumption is not valid and we return 1. If yes, we recursively repeat the process on i = i / d until it fails or the initial integer is fully factored (i == 1), in which case we decrement k. In turn, the outer function f() is called recursively until k == 0.

Note: Due to floating point rounding errors such as 125**(1/3) == 4.9999…, the actual computed value for x is floor((i+1)^1/n).

Demo

(Here with a 97-byte ES6 version for a better compatibility.)

f=(k,n,i=1)=>(F=(i,d)=>i-1?d>1?i%d?F(i,d-1):F(i/d,x):1:--k)(i,x=Math.pow(++i,1/n)|0)?f(k,n,i):i-1

console.log(f(17, 3)); // 144
console.log(f(13, 4)); // 243
console.log(f(4, 10)); // 4096

Answer 4

JavaScript (ES7), 93 79 bytes

f=(k,n,g=(i,j=2)=>i<2?--k?g(++m):m:j**n>m?g(++m):i%j?g(i,j+1):g(i/j,j))=>g(m=1)

I couldn't understand Arnauld's answer so I wrote my own and conveniently it came in at two bytes shorter. Edit: Saved 14 bytes with help from @ETHproductions. Ungolfed:

function ary(k, n) {
    for (var c = 1;; c++) {
        var m = c;
        for (var i = 2; m > 1 && i ** n <= c; i++)
            while (m % i == 0) m /= i;
        if (m == 1 && --k == 0) return c;
    }
}

Answer 5

Haskell, 86 bytes

m#n=(0:1:filter(\k->last[n|n<-[2..k],all((>0).rem n)[2..n-1],k`rem`n<1]^n<=k)[2..])!!m

Explanation:

(%%%% denotes the code from the line above)

    [n|n<-[2..k],all((>0).rem n)[2..n-1],k`rem`n<1]  -- generates all prime factors of k
    last%%%%^n<=k                                    -- checks whether k is n-ary
    (0:1:filter(\k->%%%%)[2..])!!m                   -- generates all n-ary nubmers and picks the m-th
     m#n=%%%%                                        -- assignment to the function #

Answer 6

Pyth, 13 bytes

e.f.AgL@ZQPZE

Try it online.

Works really just like the Jelly solution.

e.f.AgL@ZQPZE
                 Implicit: read n into Q.
            E    Read k.
 .f              Find the first k integers >= 1 for which
   .A            all
          P      prime factors of
           Z     the number
     gL          are at most
         Q       the n'th
       @         root of
        Z        the number.
e                Take the last one.

Answer 7

Perl 6, 88 bytes

->\k,\n{sub f(\n,\d){n-1??n%%d??f n/d,d!!f n,d+1!!d};(1,|grep {$_>=f($_,2)**n},2..*)[k]}

My accidental insight is that you don't need to look at every factor of n, just the largest one, which is what the internal function f computes. Unfortunately, it blows the stack with larger inputs.

Robustness can be improved by adding a primality test, using the built-in is-prime method on Ints, at a cost of several more characters.

Answer 8

Husk, 10 bytes

!fS≤ȯ^⁰→pN

Try it online!

Explanation

Took me a while to figure out using → on the empty list returns 1 instead of -Inf for ▲ which leaves 1 in the list (otherwise that would cost 2 bytes to prepend it again):

!fS≤(^⁰→p)N  -- input n as ⁰ and k implicit, for example: 4 3
!f        N  -- filter the natural numbers by the following predicate (example on 16):
  S≤(    )   --   is the following less than the element (16) itself?
        p    --   ..prime factors (in increasing order): [2]
       →     --   ..last element/maximum: 2
     ^⁰      --   ..to the power of n: 16
             --   16 ≤ 16: yes
             -- [1,16,32,64,81..
!            -- get the k'th element: 32

Answer 9

R, 93 bytes

f=function(k,n){x='if'(k,f(k-1,n)+1,1);while(!all(numbers::primeFactors(x)<=x^(1/n)))x=x+1;x}

Zero-indexed.

It is a recursive function that just keeps going until it finds the next number in line. Uses to numbers package to find the prime factors.

Answer 10

MATL, 21 bytes

x~`@YflG^@>~A+t2G<}x@

This solution uses one-based indexing and the inputs are n and k, respectively.

Try it Online!

Explanation

x       % Implicitly grab the first input and delete it
~       % Implicitly grab the second input and make it FALSE (0) (this is the counter)
`       % Beginning of the do-while loop
  @Yf   % Compute the prime factors of the current loop index
  1G^   % Raise them to the power of the first input
  @>    % Determine if each value in the array is greater than the current index
  ~A    % Yield a 0 if any of them were and a 1 if they weren't
  +     % Add this to the counter (increments only for positive cases)
  t2G<  % Determine if we have reached a length specified by the second input
}       % After we exit the loop (finally), ...
x@      % Delete the counter and push the current loop index to the stack
        % Implicitly display the result

Answer 11

Brachylog v2, 16 bytes

{∧.ḋ,1⌉;?^≤}ᶠ⁽t

Try it online!

Credit to Dennis's Jelly solution for getting me thinking in the right direction.

Explanation

Here's a slightly ungolfed version that's easier to parse:

↰₁ᶠ⁽t
∧.ḋ,1⌉;?^≤

Helper predicate (line 2): input is the exponent n, output is unconstrained:

∧           Break implicit unification
 .ḋ         Get the prime factors of the output
   ,1       Append 1 (necessary because 1 has no prime factors and you can't take
            the max of an empty list)
     ⌉      Max (largest prime factor, or 1 if the output is 1)
      ;?    Pair that factor with the input (n)
        ^   Take factor to the power of n
         ≤  Verify that the result is less than or equal to the output

Main predicate (line 1): input is a list containing the index k (1-based) and the exponent n; output is unconstrained:

  ᶠ⁽   Find the first k outputs of
↰₁     calling the helper predicate with n as input
    t  Get the last (i.e. kth) one

Answer 12

APL(NARS), 53 chars, 106 bytes

r←a f w;c
c←0⋄r←1
→3×⍳∼∧/(πr)≤a√r⋄→0×⍳w≤c+←1
r+←1⋄→2

test:

  1 f¨1..20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
  2 f¨1..20
1 4 8 9 12 16 18 24 25 27 30 32 36 40 45 48 49 50 54 56 
  3 f¨1..20
1 8 16 27 32 36 48 54 64 72 81 96 108 125 128 135 144 150 160 162 
  4 f¨1..20
1 16 32 64 81 96 108 128 144 162 192 216 243 256 288 324 384 432 486 512 
  10 f¨1..20
1 1024 2048 4096 8192 16384 32768 59049 62208 65536 69984 73728 78732 82944 93312 98304 104976 110592 118098 124416 

Answer 13

Python 2, 114 bytes

f=lambda K,n,i=1:K and f(K-all(j**n<=i for j in range(1,i+1)if i%j==0and all(j%k for k in range(2,j))),n,i+1)or~-i

Try it online!

1-indexed function.

Answer 14

Japt, 14 bytes

Takes n as the first input and k (1-indexed) as the second.

@_k e§Vq}aXÄ}g

Try it