A Mapping of Primes

Question

Recently, I have found a bijective mapping \$f\$ from positive integers to finite, nested sequences. The purpose of this challenge is to implement it in the language of your choice.

The Mapping

Consider a number \$n\$ with the factors \$2^{a_1}3^{a_2}5^{a_3}\cdots p^{a_i}\$ where \$a_i > 0\$

$$f(n) = \{f(a_2+1),f(a_3+1),\cdots,f(a_i+1),\underbrace{\{\},\{\},\cdots,\{\}}_{a_1}\}$$

For example:

$$\begin{align} f(22308) & = \{f(2),f(1),f(1),f(2),f(3),\{\},\{\}\} \\ & = \{\{\{\}\},\{\},\{\},\{\{\}\},\{f(2)\},\{\},\{\}\} \\ & = \{\{\{\}\},\{\},\{\},\{\{\}\},\{\{\{\}\}\},\{\},\{\}\} \end{align}$$

Rules

• You may write a full program or a function to do this task.
• Output can be in any format recognisable as a sequence.
• Built-ins for prime factorization, primality testing, etc. are allowed.
• Standard loopholes are disallowed.
• Your program must complete the last test case in under 10 minutes on my machine.
• This is code-golf, so the shortest code wins!

Test Cases

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

Answer 1

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

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

Try it online in the CJam interpreter.

Thanks to @MartinBüttner for golfing off 3 bytes!

Thanks to @PeterTaylor for golfing off 3 bytes and paving the way for 1 more!

At least on my computer, downloading the file takes longer than running the program...

I/O

This is a named function that pops and integer from STDIN and pushes an array in return.

Since CJam does not distinguish between empty arrays and empty strings – a string is simply a list that contains only characters –, the string representation will look like this:

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

referring to the following, nested array

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

Verification

$ 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

How it works

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

Answer 2

Mathematica, 88 bytes

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

Answer 3

Jelly, 14 bytes

ÆEµ“”WẋḢ;@‘߀$

Try it online!

The last test case times out on TIO. The Footer runs the program over the inputs, gets their raw form (Jelly doesn't display empty lists well) and replaces the [] with {}

How it works

ÆEµ“”WẋḢ;@‘߀$ - Main link. Takes n on the left
ÆE             - Compute the prime exponents of n
  µ            - Begin a new link with the exponents E as the argument
   “”          - []
     W         - [[]]
       Ḣ       - Take the first exponent, a
      ẋ        - Repeat each element of [[]] a times
             $ - Group the previous 2 links as a monad f(E):
          ‘    -   Increment each exponent
            €  -   Over each:
           ß   -     Recursively run the main link
        ;@     - Append the [[]] to the recursive call result

Answer 4

Pyth, 29 bytes

L+'MhMtbmYhbL&JPby/LJf}TPTSeJ

Demonstration

This defines a function, ', which performs the desired mapping.

A helper function, y, performs the mapping recursively given a prime decomposition. The base case and the prime decomposition are performed in '.

Answer 5

05AB1E, 10 bytes

ÓćÅ0«ε¯sF¸

Output with [] instead of {}.

Try it online or verify all test cases, where test case 16777213 is replaced with 1009 (another prime number) - the output for 16777213 would be similar, just with a lot more leading [], ..

Explanation:

Ó           # Get the exponents of the prime factorization of the (implicit) input
            #  ([a,b,c,d,...] in 2^a*3^b*5^c*7^d*...=input)
 ć          # Extract head; pop and push remainder-list and first item separated
  Å0        # Get a list of 0s with a length equal to the `a` exponent
    «       # Merge that as trailing items to the remainder-list
     ε      # Map over each integer in the list:
      ¯     #  Push an empty list
       s    #  Swap so the current number is at the top of the stack
        F   #  Loop that many times
         ¸  #   And wrap the list into a list every iteration
            # (after which the result is output implicitly)

Answer 6

Stax, 34 bytes

ÑE│♂█ⁿt2N╔₧Ñ↓Ls&ûΦ}eóâÇΔ-ë╖»8Kq+╔r

Run and debug it

There's very likely a better way to do this with recursion, but I just can't seem to find anything related to it in the builtin docs. So, this is a manually built implementation.

Takes very, very long after the third test case.

Explanation (Unpacked)

z]Yx{c2>{|nBs{y@msz]s|*+c]ys+Yd}{vy@}?F|u
z]                                        array [[]]
  Y                                       write that to register Y
   x{                                 F   for i in [1..input]
     c2>                                  if i < 2,
                                {vy@}     increment and take element at that index from y
        {|n                               otherwise take prime exponents
           Bs                             push the first element and the rest of the array separately
             {  m                         map the rest of the array to:
              y@                          elements in y at those indices
                 sz]s                     push [[]] and first element
                     |*                   repeat it's elements that many times
                       +                  add those together
                        c]ys+Y            and append that to register Y
                              d}          then delete it
                                       |u convert the last element on stack to string
                                          implicit output