Mapowanie liczb pierwszych

19

Ostatnio znalazłem bijectywne mapowanie f od dodatnich liczb całkowitych do skończonych, zagnieżdżonych sekwencji. Celem tego wyzwania jest wdrożenie go w wybranym języku.

Mapowanie

Rozważ liczbę n z czynnikami, w których . Następnie:

Na przykład:

Zasady

  • Możesz napisać pełny program lub funkcję do wykonania tego zadania.
  • Dane wyjściowe mogą być w dowolnym formacie rozpoznawalnym jako sekwencja.
  • Dozwolone są wbudowane czynniki pierwsze, testowanie pierwszeństwa itp .
  • Standardowe luki są niedozwolone.
  • Twój program musi ukończyć ostatni test w ciągu 10 minut na moim komputerze.
  • To jest golf golfowy, więc wygrywa najkrótszy kod!

Przypadki testowe

  • 10: {{},{{}},{}}
  • 21: {{{}},{},{{}}}
  • 42: {{{}},{},{{}},{}}
  • 30030: {{{}},{{}},{{}},{{}},{{}},{}}
  • 44100: {{{{}}},{{{}}},{{{}}},{},{}}
  • 16777215: {{{{}}},{{}},{{}},{},{{}},{{}},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{{}}}
  • 16777213: pastebin
LegionMammal978
źródło
Czy ten sam wynik bez przecinków jest nadal rozpoznawany jako sekwencja ?
Dennis,
@Dennis Tak, możesz powiedzieć w nawiasach.
LegionMammal978,
Co powiesz na numer 1
Akangka,
Ooch, to jest {}.
Akangka,
1
Byłoby to być akceptowalny format wyjściowy? CJam nie rozróżnia pustych list od pustych ciągów, więc jest to naturalny sposób reprezentowania zagnieżdżonej tablicy.
Dennis,

Odpowiedzi:

1

Pyth, 29 bajtów

L+'MhMtbmYhbL&JPby/LJf}TPTSeJ

Demonstracja

Definiuje to funkcję ', która wykonuje pożądane mapowanie.

Funkcja pomocnicza ywykonuje mapowanie rekurencyjnie, biorąc pod uwagę rozkład pierwotny. Przypadek podstawowy i rozkład główny są wykonywane w '.

isaacg
źródło
5

CJam, 51 48 44 42 41 39 34 33 31 bajtów

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

Wypróbuj online w interpretatorze CJam .

Dzięki @ MartinBüttner za grę w golfa z 3 bajtów!

Dzięki @PeterTaylor za grę w golfa z 3 bajtów i torowanie drogi dla jeszcze 1!

Przynajmniej na moim komputerze pobranie pliku trwa dłużej niż uruchomienie programu ...

I / O

Jest to nazwana funkcja, która wyskakuje i jest liczbą całkowitą ze STDIN i wypycha tablicę w zamian.

Ponieważ CJam nie rozróżnia pustych tablic od pustych ciągów - ciąg jest po prostu listą zawierającą tylko znaki - reprezentacja ciągu będzie wyglądać następująco:

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

odnosząc się do następującej, zagnieżdżonej tablicy

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

Weryfikacja

$ 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

Jak to działa

{                           }: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
źródło
Obwiniaj Pastebin: P
LegionMammal978
mf e=jest znacznie lepszy niż to, co znalazłem, gdy podrzuciłem test poczytalności, gdy pytanie było w piaskownicy, ale jednym z ulepszeń, którego nie znalazłem, jest wykonanie mapowania dla dwójki jako (0a*+- tj ri{}sa2*{mf_W=){mp},\fe=(0a*+0j\{)j}%*}j. I jest też znacznie większa poprawa, którą dam wam kilka godzin przewagi nad ...
Peter Taylor
@PeterTaylor Dzięki za golfa i podpowiedź.
Dennis,
Tak, zmiana reprezentacji wyjściowej była rzeczywiście większą poprawą. Jest też lepszy sposób na załatwienie sprawy podstawowej, którą właśnie znalazłem, ale aby pokonać twoje rozwiązanie, muszę użyć dwóch twoich pomysłów, więc:{mf_W=)1|{mp},\fe=(0a*+{)J}%}:J
Peter Taylor
@PeterTaylor That one magiczne 1|. Dzięki jeszcze raz!
Dennis,
2

Mathematica, 88 bajtów

f@1={};f@n_:=f/@Join[1+{##2},1&~Array~#]&@@SparseArray[PrimePi@#->#2&@@@FactorInteger@n]
alephalpha
źródło
Magia nieudokumentowanych elementów wewnętrznych ...
LegionMammal978,