Eine Kartierung der Primzahlen

19

Kürzlich habe ich eine bijektive Abbildung f von positiven ganzen Zahlen auf endliche, verschachtelte Sequenzen gefunden. Der Zweck dieser Herausforderung besteht darin, sie in der Sprache Ihrer Wahl zu implementieren.

Das Mapping

Betrachten Sie eine Zahl n mit den Faktoren wo . Dann:

Beispielsweise:

Regeln

  • Sie können ein vollständiges Programm oder eine Funktion schreiben, um diese Aufgabe zu erledigen.
  • Die Ausgabe kann in jedem Format erfolgen, das als Sequenz erkennbar ist.
  • Eingebaute Funktionen für Primfaktorisierung, Primalitätstests usw. sind zulässig .
  • Standardlücken sind nicht zulässig.
  • Ihr Programm muss den letzten Testfall auf meinem Computer in weniger als 10 Minuten abschließen.
  • Das ist Code-Golf, also gewinnt der kürzeste Code!

Testfälle

  • 10: {{},{{}},{}}
  • 21: {{{}},{},{{}}}
  • 42: {{{}},{},{{}},{}}
  • 30030: {{{}},{{}},{{}},{{}},{{}},{}}
  • 44100: {{{{}}},{{{}}},{{{}}},{},{}}
  • 16777215: {{{{}}},{{}},{{}},{},{{}},{{}},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{{}}}
  • 16777213: Pastebin
code-golf sequence primes LegionMammal978
quelle
Ist dieselbe Ausgabe ohne Komma noch als Sequenz erkennbar ?
Dennis
@ Tennis Ja, das erkennen Sie an den Klammern.
LegionMammal978
Wie wäre es mit der Nummer 1
Akangka
Oh, das ist {}.
Akangka
1
Wäre dies ein akzeptables Ausgabeformat? CJam unterscheidet nicht zwischen leeren Listen und leeren Strings. Dies ist also die natürliche Art, ein verschachteltes Array darzustellen.
Dennis

Antworten:

1

Pyth, 29 Bytes

L+'MhMtbmYhbL&JPby/LJf}TPTSeJ

Demonstration

Dies definiert eine Funktion, 'die das gewünschte Mapping durchführt.

Eine Hilfsfunktion yführt die Abbildung bei einer Primzerlegung rekursiv durch. Der Basisfall und die Primzerlegung werden in durchgeführt '.

isaacg
quelle
5

CJam, 51 48 44 42 41 39 34 33 31 Bytes

{mf_W=)1|{mp},\fe=(0a*+{)J}%}:J

Probieren Sie es online im CJam-Interpreter aus .

Danke an @ MartinBüttner für das Golfen mit 3 Bytes!

Vielen Dank an @PeterTaylor für das Golfen mit 3 Bytes und den Weg für 1 weiteren!

Zumindest auf meinem Computer dauert das Herunterladen der Datei länger als das Ausführen des Programms ...

I / O

Dies ist eine benannte Funktion, die eine Ganzzahl aus STDIN abruft und ein Array zurückgibt.

Da CJam nicht zwischen leeren Arrays und leeren Zeichenfolgen unterscheidet - eine Zeichenfolge ist einfach eine Liste, die nur Zeichen enthält - sieht die Zeichenfolgendarstellung folgendermaßen aus:

[[""] "" [""] ""]

Bezug nehmend auf das folgende, verschachtelte Array

[[[]] [] [[]] []]

Nachprüfung

$ wget -q pastebin.com/raw.php?i=28MmezyT -O test.ver
$ cat prime-mapping.cjam
ri
  {mf_W=)1|{mp},\fe=(0a*+{)J}%}:J
~`
$ time cjam prime-mapping.cjam <<< 16777213 > test.out

real    0m25.116s
user    0m23.217s
sys     0m4.922s
$ diff -s <(sed 's/ //g;s/""/{}/g;y/[]/{}/' < test.out) <(tr -d , < test.ver)
Files /dev/fd/63 and /dev/fd/62 are identical

Wie es funktioniert

{                           }:J  Define a function (named block) J.
 mf                              Push the array of prime factors, with repeats.
   _W=                           Push a copy and extract the last, highest prime.
      )1|                        Increment and OR with 1.
         {mp},                   Push the array of primes below that integer.

                                 If 1 is the highest prime factor, this pushes
                                 [2], since (1 + 1) | 1 = 2 | 1 = 3.
                                 If 2 is the highest prime factor, this pushes
                                 [2], since (2 + 1) | 1 = 3 | 1 = 3.
                                 If p > 2 is the highest prime factor, it pushes
                                 [2 ... p], since (p + 1) | 1 = p + 2, where p + 1
                                 is even and, therefor, not a prime.

              \fe=               Count the number of occurrences of each prime
                                 in the factorization.

                                 This pushes [0] for input 1.

                  (              Shift out the first count.
                   0a*           Push a array of that many 0's.
                      +          Append it to the exponents.

                                 This pushes [] for input 1.

                       {  }%     Map; for each element in the resulting array:
                                   Increment and call J.
Dennis
quelle
Schuld Pastebin: P
LegionMammal978
mf e=ist viel besser als das, was ich gefunden habe, als ich einen Gesundheitstest durchgeführt habe, während die Frage im Sandkasten war, aber eine Verbesserung, die ich gefunden habe, die Sie nicht verwendet haben, ist das Mapping für die beiden als (0a*+- dh ri{}sa2*{mf_W=){mp},\fe=(0a*+0j\{)j}%*}j. Und es gibt auch eine viel größere Verbesserung, die ich Ihnen ein paar Stunden Vorsprung verschaffen werde ...
Peter Taylor,
@PeterTaylor Danke für den Golf und den Hinweis.
Dennis
Ja, das Ändern der Ausgabedarstellung war in der Tat die größere Verbesserung. Es gibt auch einen besseren Weg, mit dem Basisfall umzugehen, den ich gerade erst gefunden habe. Um Ihre Lösung zu übertreffen, muss ich zwei Ihrer Ideen verwenden:{mf_W=)1|{mp},\fe=(0a*+{)J}%}:J
Peter Taylor,
@PeterTaylor Das magische 1|. Danke noch einmal!
Dennis
2

Mathematica, 88 Bytes

f@1={};f@n_:=f/@Join[1+{##2},1&~Array~#]&@@SparseArray[PrimePi@#->#2&@@@FactorInteger@n]
Alephalpha
quelle
Die Magie der undokumentierten Interna ...
LegionMammal978