A Mapping of Primes
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.
Mathematica, 88 bytes
f@1={};f@n_:=f/@Join[1+{##2},1&~Array~#]&@@SparseArray[PrimePi@#->#2&@@@FactorInteger@n]
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