Generiere n-fache Zahlen

34

Eine Sekundärzahl ist eine positive Ganzzahl, deren Primfaktoren (ohne Multiplizität) alle kleiner oder gleich der Quadratwurzel sind. 4ist eine sekundäre Zahl, da ihr einziger Primfaktor 2gleich der Quadratwurzel ist. Dies 15ist jedoch keine sekundäre Zahl, da sie 5einen Primfaktor hat, der größer ist als ihre Quadratwurzel ( ~ 3.9). Da alle Primzahlen sich selbst als Primfaktoren haben, ist keine Primzahl eine Sekundärzahl. Die ersten paar sekundären Zahlen lauten wie folgt:

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

Eine tertiäre Zahl wird auf ähnliche Weise definiert, mit der Ausnahme, dass alle Primfaktoren kleiner oder gleich der Kubikwurzel sein müssen. Die ersten paar Tertiärzahlen lauten wie folgt:

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

Im Allgemeinen ist eine n-fache Zahl eine Zahl, deren Primfaktoren alle kleiner oder gleich ihrer n-ten Wurzel sind. Somit ist eine positive ganze Zahl eine Zahl, wenn jeder ihrer Primfaktoren erfüllt . Primzahlen sind also alle positiven ganzen Zahlen (alle Primfaktoren kleiner oder gleich sich selbst), Quartenary-Zahlen haben alle Primfaktoren kleiner oder gleich ihrer vierten Wurzel und so weiter.xp p nxnppnx

Die Herausforderung

Gegeben ganze Zahlen kund nals Eingänge Ausgang der kth nary Nummer. kkann entweder null- oder einsindiziert sein (Ihre Wahl) und nist immer positiv.

Beispiele

Dies sind die ersten 20 Elemente in jeder Sequenz mit bis zu 10-stelligen Zahlen:

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
quelle

Antworten:

10

Gelee , 12 Bytes

Æf*³<‘Ạ
1Ç#Ṫ

Nimmt n und k (mit einem Index) als Befehlszeilenargumente.

Probieren Sie es online!

Wie es funktioniert

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
quelle
Hier spart man kein Byte, aber ich würde es trotzdem gutheißen, ÆfṪ*³<‘da wir wissen, dass, wenn irgendein Faktor den einen auf der rechten Seite verfälscht, dies der Fall ist.
Jonathan Allan
6

Brachylog , 21 Bytes

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

Probieren Sie es online!

Diese Antwort ist einseitig indiziert.

Erläuterung

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
Tödlich
quelle
6

JavaScript (ES7), 95 bis 90 Byte

Ziemlich schnell, aber leider begrenzt durch die maximale Anzahl von Rekursionen.

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

Wie es funktioniert

Anstatt eine ganze Zahl i zu faktorisieren und zu verifizieren, dass alle ihre Primfaktoren kleiner oder gleich x = floor (i 1 / n ) sind , versuchen wir, die letztere Annahme direkt zu validieren. Das ist der Zweck der inneren Funktion 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

Wir prüfen, ob eine ganze Zahl d in [2 ... i 1 / n ] i dividiert . Wenn nicht, ist die Annahme ungültig und wir geben 1 zurück . Wenn ja, wiederholen wir den Prozess auf i = i / d rekursiv, bis er fehlschlägt oder die anfängliche Ganzzahl vollständig berücksichtigt ist ( i == 1 ). In diesem Fall dekrementieren wir k . Die äußere Funktion f () wird wiederum rekursiv aufgerufen, bis k == 0 ist .

Hinweis: Durch Gleitkommazahl Fehler wie Rundungs 125**(1/3) == 4.9999…, der tatsächliche berechnete Wert für x ist floor ((i + 1) 1 / n ) .

Demo

(Hier mit einer 97-Byte-ES6-Version für eine bessere Kompatibilität.)

Arnauld
quelle
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)

Ich konnte Arnauld's Antwort nicht verstehen, also schrieb ich meine eigene und passenderweise kam sie um zwei Bytes kürzer. Bearbeiten: 14 Bytes mit Hilfe von @ETHproductions gespeichert. 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;
    }
}
Neil
quelle
Interessanterweise waren es genau 93 Bytes, bevor ich einen Fehler bemerkte, und ich entschied mich ++i**(1/n)eher für eine Auswertung als i**(1/n)für Gleitkomma-Rundungsfehler wie 125**(1/3) == 4.999.... (So ​​wie es geschrieben steht, ist Ihr Code davon wohl nicht betroffen.)
Arnauld
@ETHproductions Eigentlich habe ich daran gedacht, es in die Byteanzahl aufzunehmen, ich habe nur vergessen, es in die Antwort aufzunehmen ...
Neil
@ETHproductions Scheint zu funktionieren, aber ich habe die Aufgabe verschoben, mzwei weitere Bytes zu entfernen .
Neil
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

Erläuterung:

( %%%%bezeichnet den Code aus der obigen Zeile)

    [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 #
fehlerhaft
quelle
filtermit einem lambda rechnet sich selten, ein listenverständnis ist meist kürzer: 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, Sie können das auch weglassen 0:, da die Indizierung 0-basiert sein kann.
nimi
... noch besser: 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 Bytes

e.f.AgL@ZQPZE

Probieren Sie es online aus.

Funktioniert wirklich genauso wie die Jelly-Lösung.

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
quelle
3

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

Meine zufällige Einsicht ist, dass Sie nicht jeden Faktor betrachten müssen, sondern nnur den größten, den die interne Funktion fberechnet. Leider bläst es den Stack mit größeren Eingaben.

Die Robustheit kann verbessert werden, indem ein Primalitätstest mit der integrierten is-primeMethode für Ints hinzugefügt wird, der mehrere Zeichen kostet.

Sean
quelle
3

Schale , 10 Bytes

!fS≤ȯ^⁰→pN

Probieren Sie es online!

Erläuterung

Es hat eine Weile gedauert, bis ich herausgefunden habe, wie ich die leeren Listenrückgaben verwendet habe, 1anstatt -Inffür welche Blätter 1in der Liste (andernfalls würde es 2 Byte kosten, sie erneut voran zu stellen):

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

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}

Null indexiert.

Es ist eine rekursive Funktion, die nur so lange ausgeführt wird, bis die nächste Zahl in der Zeile gefunden wird. Verwendet zum numbersPacken, um die Primfaktoren zu finden.

JAD
quelle
2

MATL, 21 Bytes

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

Diese Lösung verwendet eine basierte Indizierung und die Eingänge sind nund kjeweils.

Probieren Sie es online!

Erläuterung

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
quelle
Nizza mit ~ den zweiten Eingang umzuwandeln :-)
Luis Mendo
1

Brachylog v2 , 16 Bytes

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

Probieren Sie es online!

Wir danken Dennis's Jelly-Lösung , die mich veranlasst hat, in die richtige Richtung zu denken.

Erläuterung

Hier ist eine leicht ungolfederte Version, die einfacher zu analysieren ist:

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

Hilfsprädikat (Zeile 2): Eingabe ist der Exponent n , Ausgabe ist nicht eingeschränkt:

∧           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

Hauptprädikat (Zeile 1): Eingabe ist eine Liste, die den Index k (1-basiert) und den Exponenten n enthält ; Die Ausgabe ist nicht eingeschränkt:

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

APL (NARS), 53 Zeichen, 106 Byte

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

Prüfung:

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

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

Probieren Sie es online!

1-indizierte Funktion.

Chas Brown
quelle
0

Japt , 14 Bytes

Nimmt nals erste Eingabe und k(1-indiziert) als zweite.

@_k e§Vq}aXÄ}g

Versuch es

Zottelig
quelle