Генерация n-арных чисел

34

Вторичное число - это положительное целое число, простые множители которого (без кратности) меньше или равны его квадратному корню. 4является вторичным числом, потому что его единственный главный фактор 2равен его квадратному корню. Тем 15не менее, это не вторичное число, потому что оно имеет 5в качестве основного фактора, который больше, чем его квадратный корень ( ~ 3.9). Поскольку все простые числа сами являются основными факторами, никакое простое число не является вторичным числом. Первые несколько вторичных чисел следующие:

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

Третичное число определяется аналогично, за исключением того, что все простые множители должны быть меньше или равны его корню куба. Первые несколько третичных чисел следующие:

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

В общем случае n-числовое число - это число , простые множители которого меньше или равны его n-му корню. Таким образом, положительное целое число x является nариальным числом тогда и только тогда, когда каждый из его простых факторов удовлетворяет условию . Таким образом, все первичные числа являются положительными целыми числами (все простые множители меньше или равны самим себе), четвертичные числа имеют все свои простые множители меньше или равны их четвертому корню и т. Д.ppnx

Соревнование

С учетом числа kи в nкачестве входных данных, выведите kй n-ичный номер. kможет быть либо с нулевым, либо с одним индексом (на ваш выбор) и nвсегда будет положительным.

Примеры

Это первые 20 элементов в каждой последовательности до 10-ти чисел:

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
Мего
источник

Ответы:

10

Желе , 12 байт

Æf*³<‘Ạ
1Ç#Ṫ

Принимает n и k (одноиндексные) в качестве аргументов командной строки.

Попробуйте онлайн!

Как это работает

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.
Деннис
источник
Здесь нет сохранения байтов, но я бы все еще был полон, ÆfṪ*³<‘поскольку мы знаем, что если какой-либо фактор искажает, то тот, что справа, будет.
Джонатан Аллан
6

Брахилог , 21 байт

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

Попробуйте онлайн!

Этот ответ одноиндексный.

объяснение

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
Fatalize
источник
6

JavaScript (ES7), 95 90 байт

Разумно быстро, но, к сожалению, ограничено максимальным количеством рекурсий.

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

Как это работает

Вместо того, чтобы факторизовать целое число i и убедиться, что все его простые множители меньше или равны x = floor (i 1 / n ) , мы пытаемся проверить последнее предположение напрямую. Это цель внутренней функции 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

Мы проверяем, делит ли любое целое число d в [2 ... i 1 / n ] i . Если нет, предположение неверно, и мы возвращаем 1 . Если да, мы рекурсивно повторяем процесс на i = i / d до тех пор, пока он не завершится неудачей или начальное целое число не будет полностью учтено ( i == 1 ), и в этом случае мы уменьшаем k . В свою очередь, внешняя функция f () вызывается рекурсивно, пока k == 0 .

Примечание. Из-за ошибок округления с плавающей запятой, таких как 125**(1/3) == 4.9999…фактическое вычисленное значение для x - это пол ((i + 1) 1 / n ) .

демонстрация

(Здесь с 97-байтовой версией ES6 для лучшей совместимости.)

Arnauld
источник
6

JavaScript (ES7), 93 79 байт

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)

Я не мог понять ответ Арно, поэтому я написал свой собственный, и он был удобен на два байта короче. Редактировать: 14 байтов сохранено с помощью @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;
    }
}
Нил
источник
Интересно, что у меня было ровно 93 байта, прежде чем я заметил ошибку и решил оценить, ++i**(1/n)а не i**(1/n)из-за ошибок округления с плавающей запятой, таких как 125**(1/3) == 4.999.... (То, как это написано, я думаю, что на ваш код это не влияет.)
Arnauld
@ETHproductions На самом деле, я не забыл включить его в число байтов, я просто забыл включить его в ответ ...
Нейл
@ETHproductions Кажется, работает, но я переместил назначение, mчтобы сбрить еще два байта.
Нил
5

Haskell, 86 байт

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

Объяснение:

( %%%%обозначает код из строки выше)

    [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 #
flawr
источник
filterс лямбда редко окупается, понимание списка обычно короче: m#n=(0:1:[k|k<-[2..],last[n|n<-[2..k],all((>0).rem n)[2..n-1],krem n<1]^n<=k])!!m.
Ними
О, вы также можете опустить 0:, потому что индексирование может быть на основе 0.
Ними
... еще лучше: m#n=[k|k<-[1..],last[n|n<-[1..k],all((>0).rem n)[2..n-1],kremn<1]^n<=k]!!m
nimi
3

Pyth, 13 байт

e.f.AgL@ZQPZE

Попробуйте онлайн.

Работает действительно так же, как решение Jelly.

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.
PurkkaKoodari
источник
3

Perl 6, 88 байт

->\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]}

Я случайно понял, что вам не нужно смотреть на каждый фактор n, только на самый большой, который fвычисляет внутренняя функция . К сожалению, это уносит стек с большими входами.

Надежность можно улучшить, добавив тест на простоту, используя встроенный is-primeметод Ints, за счет еще нескольких символов.

Шон
источник
3

Шелуха , 10 байт

!fS≤ȯ^⁰→pN

Попробуйте онлайн!

объяснение

Мне потребовалось некоторое время, чтобы выяснить, использует ли возврат 1из пустого списка вместо того, -Infдля чего он уходит 1в список (в противном случае это будет стоить 2 байта, чтобы добавить его снова):

!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
ბიმო
источник
2

R, 93 байта

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-индексироваться.

Это рекурсивная функция, которая продолжает работать до тех пор, пока не найдет следующий номер в строке. Использует numbersупаковку, чтобы найти основные факторы.

JAD
источник
2

MATL, 21 байт

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

В этом решении используется индексация по одному, а входы - nи kсоответственно.

Попробуйте онлайн!

объяснение

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
Suever
источник
Хорошо использовать ~ для повторного использования второго ввода :-)
Луис Мендо
1

Brachylog v2 , 16 байт

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

Попробуйте онлайн!

Благодарим Денниса за решение Jelly, которое заставило меня задуматься в правильном направлении.

объяснение

Вот версия, немного отличная от других, которую легче разобрать:

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

Предикат помощника (строка 2): вход - показатель степени n , выход - без ограничений:

∧           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

Основной предикат (строка 1): вход - это список, содержащий индекс k (на основе 1) и показатель степени n ; вывод неограничен:

  ᶠ⁽   Find the first k outputs of
↰₁     calling the helper predicate with n as input
    t  Get the last (i.e. kth) one
DLosc
источник
0

APL (NARS), 53 символа, 106 байтов

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

тест:

  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 
RosLuP
источник
0

Japt , 14 байт

Принимает nв качестве первого ввода и k(1-индексированный) в качестве второго.

@_k e§Vq}aXÄ}g

Попытайся

мохнатый
источник