Generuj liczby n-arytowe

34

Liczba wtórna jest dodatnią liczbą całkowitą, której czynniki pierwsze (bez wielokrotności) są mniejsze lub równe pierwiastkowi kwadratowemu. 4jest liczbą drugorzędną, ponieważ jej jedynym czynnikiem podstawowym jest 2równa pierwiastek kwadratowy. Nie 15jest to jednak liczba wtórna, ponieważ ma ona 5jako pierwszy czynnik większy niż pierwiastek kwadratowy ( ~ 3.9). Ponieważ wszystkie liczby pierwsze mają się jako czynniki pierwsze, żadna liczba pierwsza nie jest liczbą wtórną. Pierwsze kilka liczb wtórnych jest następujące:

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

Liczba trzeciorzędowa jest zdefiniowana podobnie, z tym wyjątkiem, że wszystkie czynniki pierwsze muszą być mniejsze lub równe pierwiastkowi sześcianu. Pierwsze kilka liczb trzeciorzędnych są następujące:

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

Ogólnie rzecz biorąc, liczba n-ary to liczba, której czynniki pierwsze są mniejsze lub równe n-temu pierwiastkowi. Zatem dodatnia liczba całkowita x jest liczbą n-arną iff każdy z jej czynników pierwszych p spełnia pnx . Tak więc wszystkie liczby pierwotne są dodatnimi liczbami całkowitymi (wszystkie czynniki pierwsze mniejsze lub równe sobie), liczby kwadratowe mają wszystkie swoje czynniki pierwsze mniejsze lub równe czwartemu pierwiastkowi i tak dalej.

Wyzwanie

Biorąc pod uwagę całkowite ki njak wejść, wyjście kth nliczba -ary. kmoże być zerowy lub indeksowany jednokrotnie (twój wybór) i nzawsze będzie dodatni.

Przykłady

Oto pierwszych 20 elementów w każdej sekwencji do 10-arytowych liczb:

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
Mego
źródło

Odpowiedzi:

10

Galaretka , 12 bajtów

Æf*³<‘Ạ
1Ç#Ṫ

Pobiera n i k (jeden indeks) jako argumenty wiersza poleceń.

Wypróbuj online!

Jak to działa

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.
Dennis
źródło
Nie ma tu bajtu oszczędzania, ale wciąż bym za to walczył, ÆfṪ*³<‘ponieważ wiemy, że jeśli jakikolwiek czynnik fałszuje ten z prawej.
Jonathan Allan,
6

Brachylog , 21 bajtów

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

Wypróbuj online!

Ta odpowiedź ma jeden indeks.

Wyjaśnienie

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
Fatalizować
źródło
6

JavaScript (ES7), 95 90 bajtów

Racjonalnie szybki, ale niestety ograniczony maksymalną liczbą rekurencji.

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

Jak to działa

Zamiast faktoryzować liczbę całkowitą i i sprawdzić, czy wszystkie jej czynniki pierwsze są mniejsze lub równe x = floor (i 1 / n ) , staramy się bezpośrednio zweryfikować to drugie założenie. Taki jest cel funkcji wewnętrznej 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

Sprawdzamy, czy jakaś liczba całkowita d w [2 ... i 1 / n ] dzieli i . Jeśli nie, założenie jest nieważne i zwracamy 1 . Jeśli tak, rekurencyjnie powtarzamy proces na i = i / d aż do niepowodzenia lub początkowa liczba całkowita zostanie w pełni uwzględniona ( i == 1 ), w którym to przypadku zmniejszamy wartość k . Z kolei funkcja zewnętrzna f () jest wywoływana rekurencyjnie, aż do k == 0 .

Uwaga: Z powodu błędów zaokrąglania zmiennoprzecinkowego, takich jak 125**(1/3) == 4.9999…faktyczna obliczona wartość dla x to floor ((i + 1) 1 / n ) .

Próbny

(Tutaj z 97-bajtową wersją ES6 dla lepszej kompatybilności.)

Arnauld
źródło
6

JavaScript (ES7), 93 79 bajtów

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)

Nie mogłem zrozumieć odpowiedzi Arnaulda, więc napisałem własną i wygodnie przyszła o dwa bajty krócej. Edycja: Zapisano 14 bajtów przy pomocy @ETHproductions. Nie golfowany:

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;
    }
}
Neil
źródło
Co ciekawe, mój miał dokładnie 93 bajty, zanim zauważyłem błąd i postanowiłem go ocenić, ++i**(1/n)a nie z i**(1/n)powodu błędów zaokrąglania zmiennoprzecinkowego, takich jak 125**(1/3) == 4.999.... (Sposób, w jaki jest napisany, myślę, że nie wpływa to na twój kod.)
Arnauld,
@ETHproductions Właściwie pamiętam, aby uwzględnić go w liczbie bajtów, po prostu zapomniałem podać go w odpowiedzi ...
Neil
@ETHproductions Wydaje się, że działa, ale przesunąłem zadanie, maby zgolić kolejne dwa bajty.
Neil,
5

Haskell, 86 bajtów

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

Wyjaśnienie:

( %%%%oznacza kod z powyższej linii)

    [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 #
wada
źródło
filterz lambda rzadko się opłaca, lista jest zazwyczaj krótsza: 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.
nimi
Och, można również pominąć 0:, ponieważ indeksowanie może być oparte na 0.
nimi
... jeszcze lepiej: 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 bajtów

e.f.AgL@ZQPZE

Wypróbuj online.

Działa tak samo jak rozwiązanie 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
źródło
3

Perl 6, 88 bajtów

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

Mój przypadkowy wgląd jest taki, że nie trzeba patrzeć na każdy czynnik n, tylko na największy, jaki jest funkcją wewnętrznąf oblicza . Niestety, wysadza stos z większymi wejściami.

Wytrzymałość można poprawić, dodając test pierwszeństwa, używając wbudowanej is-primemetody Ints, kosztem kilku dodatkowych znaków.

Sean
źródło
3

Łuska , 10 bajtów

!fS≤ȯ^⁰→pN

Wypróbuj online!

Wyjaśnienie

Zajęło mi trochę czasu, aby wymyślić użycie pustej listy zwrotów 1zamiast tego, -Infdla których pozostawia 1na liście (w przeciwnym razie to kosztowałoby 2 bajty, aby ją ponownie wstawić):

!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
ბიმო
źródło
2

R, 93 bajty

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 indeksowane.

Jest to funkcja rekurencyjna, która działa, dopóki nie znajdzie następnej liczby w linii. Używa numberspakietu, aby znaleźć czynniki pierwsze.

JAD
źródło
2

MATL, 21 bajtów

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

Rozwiązanie to wykorzystuje jedną opartą indeksowania i wejścia są ni k, odpowiednio.

Wypróbuj online!

Wyjaśnienie

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
źródło
Miło jest użyć, ~ aby zmienić przeznaczenie drugiego wejścia :-)
Luis Mendo,
1

Brachylog v2 , 16 bajtów

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

Wypróbuj online!

Kredyt do rozwiązania Jelly Dennisa za wprowadzenie mnie myślenie w dobrym kierunku.

Wyjaśnienie

Oto nieco niestosowana wersja, którą łatwiej przeanalizować:

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

Predykat pomocnika (wiersz 2): dane wejściowe są wykładnikiem n , dane wyjściowe nie są ograniczone:

∧           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

Główny predykat (wiersz 1): dane wejściowe to lista zawierająca indeks k (oparty na 1) i wykładnik n ; dane wyjściowe są nieograniczone:

  ᶠ⁽   Find the first k outputs of
↰₁     calling the helper predicate with n as input
    t  Get the last (i.e. kth) one
DLosc
źródło
0

APL (NARS), 53 znaki, 106 bajtów

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 
RosLuP
źródło
0

Python 2 , 114 bajtów

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

Wypróbuj online!

Funkcja 1-indeksowana.

Chas Brown
źródło
0

Japt , 14 bajtów

Pobiera njako pierwsze wejście i k(1-indeksowane) jako drugie.

@_k e§Vq}aXÄ}g

Spróbuj

Kudłaty
źródło