Récemment, j'ai trouvé un mappage bijectif f d'entiers positifs à des séquences imbriquées finies. Le but de ce challenge est de le mettre en œuvre dans la langue de votre choix.

La cartographie

Considérons un nombre n avec les facteurs où . Alors:

Par exemple:

Règles

• Vous pouvez écrire un programme complet ou une fonction pour effectuer cette tâche.
• La sortie peut être dans n'importe quel format reconnaissable comme une séquence.
• Les fonctions intégrées pour la factorisation principale, les tests de primalité, etc. sont autorisées .
• Les failles standard ne sont pas autorisées.
• Votre programme doit terminer le dernier cas de test en moins de 10 minutes sur ma machine.
• C'est le code-golf, donc le code le plus court gagne!

Cas de test

• 10: {{},{{}},{}}
• 21: {{{}},{},{{}}}
• 42: {{{}},{},{{}},{}}
• 30030: {{{}},{{}},{{}},{{}},{{}},{}}
• 44100: {{{{}}},{{{}}},{{{}}},{},{}}
• 16777215: {{{{}}},{{}},{{}},{},{{}},{{}},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{{}}}
• 16777213: pastebin

Pyth, 29 octets

L+'MhMtbmYhbL&JPby/LJf}TPTSeJ

Manifestation

Cela définit une fonction, 'qui effectue le mappage souhaité.

Une fonction d'aide,, yeffectue le mappage récursivement en fonction d'une décomposition principale. Le cas de base et la décomposition principale sont effectués dans '.

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

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

Essayez-le en ligne dans l' interpréteur CJam .

Merci à @ MartinBüttner pour avoir joué au golf sur 3 octets!

Merci à @PeterTaylor pour avoir joué au golf sur 3 octets et ouvert la voie à 1 autre!

Au moins sur mon ordinateur, le téléchargement du fichier prend plus de temps que l'exécution du programme ...

E / S

Il s'agit d'une fonction nommée qui apparaît et entier à partir de STDIN et pousse un tableau en retour.

Étant donné que CJam ne fait pas de distinction entre les tableaux vides et les chaînes vides - une chaîne est simplement une liste qui ne contient que des caractères -, la représentation de la chaîne ressemblera à ceci:

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

se référant au tableau imbriqué suivant

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

Vérification

$ 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

Comment ça fonctionne

{                           }: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.

Mathematica, 88 octets

f@1={};f@n_:=f/@Join[1+{##2},1&~Array~#]&@@SparseArray[PrimePi@#->#2&@@@FactorInteger@n]