# Recursive Prime Factorization

Your job is to take the prime factors of a number taken from input (omitting any exponents equal to 1) then take the prime factors of all of the exponents, and so on, until no composite numbers remain; and then output the result.

To make what I'm asking slightly clearer, here's a javascript program that does it, but, at 782 bytes, it's not very well golfed yet:

var primes=[2,3];
function nextPrime(){
var n=2;
while(isAMultipleOfAKnownPrime(n)){n++}
primes.push(n);
}
function isAKnownPrime(n){return primes.indexOf(n)!=-1};
function isAMultipleOfAKnownPrime(n){
for(var i=0;i<primes.length;i++)if(n%primes[i]==0)return true;
return false;
}
function primeFactorize(n){
while(primes[primes.length-1]<n)nextPrime();
if(isAKnownPrime(n)||n==1)return n;
var q=[];while(q.length<=n)q.push(0);
while(n!=1){
for(var i=0;i<primes.length;i++){
var x=primes[i];
if(n%x==0){q[x]++;n/=x}
}
}
var o="";
for(var i=2;i<q.length;i++){
if(q[i]){if(o)o+="x";o+=i;if(q[i]>1){o+="^("+primeFactorize(q[i])+")"}}
}
return o;
}

You are required to make order of operations as clear as possible, and sort the prime factors in ascending order on each level.

You get a -50 byte bonus if you produce the output as formatted mathprint or valid latex code.

• It would help to provide examples of input and output. – DavidC May 28 '15 at 12:28
• Could you give some example inputs and outputs? I'm having trouble understanding your spec, and the example solution is quite terse. – Zgarb May 28 '15 at 12:29
• @Zgarb He means to factor the integer, factor the primes' exponents, factor their exponents, etc., until you are left with all prime numbers. – LegionMammal978 May 28 '15 at 13:11
• What exactly do you understand as "formatted mathprint". Is it for instance allowed to print latex code? – Jakube May 28 '15 at 13:42
• @Zgarb Any format that works (ex. 2^(5^11*11^(2^7))*541). – LegionMammal978 May 28 '15 at 14:12

# CJam, 32312927 25 - 50 = -25 bytes

7 bytes saved by Dennis.

Woooo, Dennis reduced this by an amazing seven bytes and managed to beat Pyth!

q~S2*{mF{~'^'{@j'}'*}/;}j

Test it here.

## Explanation

q~                           e# Read and eval input.
S2*                        e# Push the string "  ". The second space will be our
e# memoised result for input 1. This way, 1-exponents become
e# ^{ } later which do not affect the rendered output of the
e# generated LaTeX.
{                 }j    e# Initialise a recursion with the above base case.
mF                     e# Compute prime factorisation as list of pairs.
{           }/       e# For each pair...
~'^'{@              e# Unwrap the pair and put a '^' and a '{' in the middle.
j             e# Recursively run the outer block on the exponent.
'}'*         e# Push a '}' and a '*' character.
;      e# Discard the last '*'.

All those stack contents will be printed automatically back-to-back at the end of the program.

• "{}" -> {}s Looks like you've figured out how j works. – Dennis May 30 '15 at 20:02
• @Dennis I think I've been using j for a while. user23013 posted a nice explanation on Mixed Base Conversion, and aditsu a few clarifying remarks for advanced usage somewhere on SourceForge. – Martin Ender May 30 '15 at 20:05
• aditsu actually answered a forum post of mine, but SF didn't notify me and I stopped checking after a couple of month... While j is pretty cool, a named function would be shorter here: {mF{)_({Fa+'^}&*}%'**{}s\*}:F – Dennis May 30 '15 at 21:00
• @Dennis Oh right, I didn't consider that I could actually make it a function-only submission if I used the named function approach. Will change the answer later. – Martin Ender May 30 '15 at 21:04
• 25 bytes: q~S2*{mF{~'^'{@j'}'*}/;}j – Dennis May 31 '15 at 2:18

# Pyth, 27 - 50 = -23 bytes

Lj\*m+ed?+\^jyhdHthdkrPb8

This defines a recursive function y. Try it online: Demonstration

The output is valid LaTeX code, so I claim the bonus. The call y66430125 returns the string 3^{2^{2}*3}*5^{3}, which renders to

Quite proud for finding a way to print the curly brackets without using curly brackets in my code.

# Explanation:

L                            define a function y(b): return ...
Pb       prime factorization of b
r  8      run-length-encoded, gives pairs of (exponent, prime)
m                           map each pair d (exponent, prime) to:
ed                          prime
+                            +
yhd                    recursive call
j   H                  join repr(H) by ^
H is preinitialized with an empty dictionary
so the repr(H) gives the string "{}"
and join inserts the prime-factorization
of the exponent between the chars of "{}"

+\^                        add "^" at the beginning
?         thd               if exponent - 1 != 0 else
k              "" (empty string)
j\*                            join by "*"
• @SuperJedi224 Yes, your right. Using an old approach this one was shorter. But now, that I found the repr(H) trick, it doesn't matter. So I edited it right now. – Jakube May 28 '15 at 18:36
• By the way {} is the empty dictionary in Python, not the empty set. – isaacg May 28 '15 at 23:41

# Pyth - 393432 28 bytes

Thanks Jakube

Defines a function y which takes an integer:

L?j\xm+ed+"^("+yhd\)rPb8tPbb

Explanation:

L                              define y(b): return
j\x                              "x".join(
m                                 map(lambda d:
+ed+"^("+yhd\)                       d[1] + "^(" + y(d[0]) + ")",
rPb8                   tally(prime_factors(b))))
?                      tPb        if len(prime_factors(b)) != 1 else
b           b

If ^(1) isn't allowed I have to use 33 bytes:

L?j\xm+ed?+"^("+yhd\)thdkrPb8tPbb

# Mathematica, 106102 101 - 50 = 51 bytes

If[PrimeQ@#,#,(a=CenterDot)@@{b,c}~Function~If[c<2,b,b~Superscript~#0@c]@@@FactorInteger@#/.a@b_:>b]&

Formats as nested exponents with dot multiplication. Unicode representations of example input and output:

• 102 · 5
• 1202³ · 3 · 5
• 163842²˙⁷
• Nice use of CenterDot to avoid Times. I'm still trying to figure out where the recursion takes place. – DavidC May 28 '15 at 13:39
• @DavidCarraher #0 refers to the innermost pure function without argument names. – LegionMammal978 May 28 '15 at 16:23
• Thanks. First time I have heard about this use of # – DavidC May 28 '15 at 17:29

# Bash + coreutils + bsdgames, 117 - 50 = 67

f()(factor $1|tr \ \\n|sed 1d|uniq -c|while read e m;do ((e>1))&&m+=^{f$e}
printf {$m} done) f$1|sed s/}{/}\*{/g

### Output

$./recprimefac.sh 2985984 {2^{{2^{{2}}}*{3}}}*{3^{{2}*{3}}}$
\$

I'm claiming the -50 bonus, because this output is LaTeX formatted and with a tool like http://www.sciweavers.org/free-online-latex-equation-editor renders to:

Let me know if this is not acceptable.

• That works fine. – SuperJedi224 May 28 '15 at 17:07

# Clip, 36 33

jm[z.y(z?()z{'^'(M)z')]L]}qfnx"*

## Explanation

qfnx   .- Prime factors of the input, with exponents -.
m[z                      }       .- For each factor z...               -.
.y(z                          .- The prime number                   -.
?()z            L]        .- If the exponent is 1, nothing      -.
{         ]          .- Otherwise, the following:          -.
M)z              .- Apply the main function to the exponent... -.
'^'(   ')            .- ...inside ^(..)                    -.
j                              "* .- Join the factors with "*"          -.

# Javascript, 388-50=338

l="length";function g(n){for(;m(++n););p.push(n)}function m(n){for(i=0;i<p[l];i++)if(n%p[i]==0)return 1;return 0}function f(n,x,q,o){while(p[p[l]-1]<n)g(2);if(p.indexOf(n)>=0||n==1)return n;q=[];while(q[l]<=n)q.push(0);for(i=0;i<p[l];i++){x=p[i];while(n%x==0){q[x]++;n/=x}}o="";for(i=2;i<q[l];i++)if(q[i]){if(o)o+="*";o+=i;if(q[i]>1){o+="^{"+f(q[i])+"}"}}return o}alert(f(+prompt(p=[2])))

Since LaTeX code is now eligible for the bonus, I decided to include the requisite modifications as part of the golfing for this. It can probably still be golfed further though.