Hasilkan angka n-ary

34

Bilangan sekunder adalah bilangan bulat positif yang faktor prima (tanpa multiplisitas) semuanya kurang dari atau sama dengan akar kuadratnya. 4adalah angka sekunder, karena satu-satunya faktor prima adalah 2, yang sama dengan akar kuadratnya. Namun, 15bukan angka sekunder, karena memiliki 5sebagai faktor utama, yang lebih besar dari akar kuadratnya ( ~ 3.9). Karena semua bilangan prima memiliki dirinya sendiri sebagai faktor prima, tidak ada bilangan prima adalah bilangan sekunder. Beberapa angka sekunder pertama adalah sebagai berikut:

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

Angka tersier didefinisikan dengan cara yang sama, kecuali semua faktor prima harus kurang dari atau sama dengan akar pangkat tiga. Beberapa nomor tersier pertama adalah sebagai berikut:

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

Secara umum, bilangan n-ary adalah bilangan yang faktor prima semuanya kurang dari atau sama dengan akar ke-nnya. Jadi, bilangan bulat positif adalah angka -ary jika masing-masing faktor utamanya memenuhi . Dengan demikian, bilangan primer semuanya bilangan bulat positif (semua faktor prima kurang dari atau sama dengan diri mereka sendiri), bilangan kuarter memiliki semua faktor prima kurang dari atau sama dengan akar keempat, dan seterusnya.xp p nxnppnx

Tantangan

Mengingat bilangan bulat kdan nsebagai masukan, keluaran kth nnomor -ary. kmungkin nol atau satu-diindeks (pilihan Anda), dan nakan selalu positif.

Contohnya

Ini adalah 20 elemen pertama dalam setiap urutan hingga angka 10-ary:

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
sumber

Jawaban:

10

Jelly , 12 byte

Æf*³<‘Ạ
1Ç#Ṫ

Mengambil n dan k (satu-diindeks) sebagai argumen baris perintah.

Cobalah online!

Bagaimana itu bekerja

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
sumber
Tidak ada byte yang disimpan di sini, tapi saya masih akan menggunakan ÆfṪ*³<‘karena kita tahu bahwa jika ada faktor yang memalsukan yang ada di sebelah kanan.
Jonathan Allan
6

Brachylog , 21 byte

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

Cobalah online!

Jawaban ini satu-diindeks.

Penjelasan

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
Fatalisasi
sumber
6

JavaScript (ES7), 95 90 byte

Sangat cepat tetapi sayangnya dibatasi oleh jumlah rekursi maksimum.

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

Bagaimana itu bekerja

Daripada memfaktorkan bilangan bulat i dan memverifikasi bahwa semua faktor utamanya kurang dari atau sama dengan x = lantai (i 1 / n ) , kami mencoba untuk memvalidasi asumsi yang terakhir secara langsung. Itulah tujuan fungsi dalam 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

Kami memeriksa apakah ada bilangan bulat d di [2 ... i 1 / n ] membagi i . Jika tidak, asumsi tersebut tidak valid dan kami mengembalikan 1 . Jika ya, kami mengulangi proses pada i = i / d secara berulang sampai gagal atau bilangan bulat awal sepenuhnya difaktorkan ( i == 1 ), dalam hal ini kami mengurangi k . Pada gilirannya, fungsi luar f () disebut secara rekursif hingga k == 0 .

Catatan: Karena kesalahan pembulatan titik mengambang seperti 125**(1/3) == 4.9999…, nilai aktual yang dihitung untuk x adalah lantai ((i + 1) 1 / n ) .

Demo

(Di sini dengan versi ES6 97-byte untuk kompatibilitas yang lebih baik.)

Arnauld
sumber
6

JavaScript (ES7), 93 79 byte

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)

Saya tidak dapat memahami jawaban Arnauld jadi saya menulis sendiri dan mudahnya dua byte lebih pendek. Sunting: Disimpan 14 byte dengan bantuan dari @ETHproductions. Tidak Disatukan:

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
sumber
Menariknya, milik saya persis 93 byte sebelum saya melihat bug dan memutuskan untuk mengevaluasi ++i**(1/n)daripada i**(1/n)karena kesalahan pembulatan titik mengambang seperti 125**(1/3) == 4.999.... (Cara ini ditulis, saya pikir kode Anda tidak terpengaruh oleh ini.)
Arnauld
@ ETHproductions Sebenarnya, saya ingat untuk memasukkannya dalam hitungan byte, saya hanya lupa untuk memasukkannya dalam jawaban ...
Neil
@ ETHproductions Tampaknya bekerja, tapi saya memindahkan tugas muntuk mencukur dua byte lebih lanjut.
Neil
5

Haskell, 86 byte

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

Penjelasan:

( %%%%menunjukkan kode dari baris di atas)

    [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 #
cacat
sumber
filterdengan lambda jarang terbayar, daftar pemahaman biasanya lebih pendek: 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
Oh, Anda juga dapat menghilangkannya 0:, karena pengindeksan dapat berbasis 0.
nimi
... lebih baik lagi: 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 byte

e.f.AgL@ZQPZE

Cobalah online.

Bekerja sangat mirip dengan solusi 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
sumber
3

Perl 6, 88 byte

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

Wawasan yang tidak disengaja saya adalah bahwa Anda tidak perlu melihat setiap faktor n, hanya faktor terbesar, yang fdihitung oleh fungsi internal . Sayangnya, ini menghancurkan stack dengan input yang lebih besar.

Robustness dapat ditingkatkan dengan menambahkan tes primality, menggunakan is-primemetode bawaan pada Ints, dengan biaya beberapa karakter lagi.

Sean
sumber
3

Sekam , 10 byte

!fS≤ȯ^⁰→pN

Cobalah online!

Penjelasan

Butuh beberapa waktu untuk mencari tahu menggunakan pada daftar kosong kembali 1bukan -Infuntuk yang daun 1dalam daftar (sebaliknya yang akan biaya 2 byte untuk tambahkan lagi):

!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
ბიმო
sumber
2

R, 93 byte

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}

Diindeks nol.

Ini adalah fungsi rekursif yang terus berjalan sampai menemukan nomor berikutnya dalam barisan. Menggunakan numberspaket untuk menemukan faktor utama.

JAD
sumber
2

MATL, 21 byte

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

Solusi ini menggunakan satu berbasis pengindeksan dan input ndan kmasing-masing.

Cobalah secara Online!

Penjelasan

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
sumber
Senang menggunakan ~ untuk mengubah input kedua :-)
Luis Mendo
1

Brachylog v2 , 16 byte

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

Cobalah online!

Kredit untuk solusi Jelly Dennis untuk mendapatkan saya berpikir ke arah yang benar.

Penjelasan

Berikut ini adalah versi yang sedikit tidak digubah yang lebih mudah diurai:

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

Predikat pembantu (baris 2): input adalah eksponen n , output tidak dibatasi:

∧           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

Predikat utama (baris 1): input adalah daftar yang berisi indeks k (1-based) dan eksponen n ; output tidak dibatasi:

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

APL (NARS), 53 karakter, 106 byte

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

uji:

  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
sumber
0

Python 2 , 114 byte

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

Cobalah online!

Fungsi 1-diindeks.

Chas Brown
sumber
0

Japt , 14 byte

Dibawa nsebagai input pertama dan k(1-diindeks) sebagai yang kedua.

@_k e§Vq}aXÄ}g

Cobalah

Shaggy
sumber