# A Mapping of Primes

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 where . Then:

For example:

## 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
• Is the same output, without the commas, still recognisable as a sequence? – Dennis Nov 23 '15 at 13:44
• @Dennis Yes, you can tell by the brackets. – LegionMammal978 Nov 23 '15 at 13:44
• How about the number 1 – Akangka Nov 23 '15 at 13:56
• Ooh, that is {}. – Akangka Nov 23 '15 at 13:56
• Would this be an acceptable output format? CJam doesn't distinguish between empty lists and empty strings, so this is the natural way of representing a nested array. – Dennis Nov 23 '15 at 16:10

# 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 '.

# CJam, 5148444241393433 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!

### 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.

• Blame Pastebin :P – LegionMammal978 Nov 23 '15 at 14:22
• mf e= is much better than what I'd found when I knocked up a sanity test while the question was in the sandbox, but one improvement I found which you haven't used is to do the mapping for the twos as (0a*+ - i.e. ri{}sa2*{mf_W=){mp},\fe=(0a*+0j\{)j}%*}j. And there's a much bigger improvement as well which I'll give you a few hours' headstart on... – Peter Taylor Nov 23 '15 at 14:36
• @PeterTaylor Thanks for the golf and the hint. – Dennis Nov 23 '15 at 15:04
• Yep, changing the output representation was indeed the bigger improvement. There's a better way of handling the base case too, which I've only just found, but to beat your solution I have to use two of your ideas so: {mf_W=)1|{mp},\fe=(0a*+{)J}%}:J – Peter Taylor Nov 23 '15 at 18:59
• @PeterTaylor That one magical 1|. Thanks again! – Dennis Nov 23 '15 at 19:10

# Mathematica, 88 bytes

f@1={};f@n_:=f/@Join[1+{##2},1&~Array~#]&@@SparseArray[PrimePi@#->#2&@@@FactorInteger@n]
`
• The magic of undocumented internals... – LegionMammal978 Nov 23 '15 at 20:48