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;
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){
    if(isAKnownPrime(n)||n==1)return n;
    var q=[];while(q.length<=n)q.push(0);
        for(var i=0;i<primes.length;i++){
            var x=primes[i];
    var o="";
    for(var i=2;i<q.length;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.

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

7 Answers 7


Pyth, 27 - 50 = -23 bytes


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.


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 "*"
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Jakube
    May 28, 2015 at 18:36
  • \$\begingroup\$ By the way {} is the empty dictionary in Python, not the empty set. \$\endgroup\$
    – isaacg
    May 28, 2015 at 23:41

CJam, 32 31 29 27 25 - 50 = -25 bytes

7 bytes saved by Dennis.

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


Test it here.


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.

  • \$\begingroup\$ "{}" -> {}s Looks like you've figured out how j works. \$\endgroup\$
    – Dennis
    May 30, 2015 at 20:02
  • \$\begingroup\$ @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. \$\endgroup\$ May 30, 2015 at 20:05
  • \$\begingroup\$ 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 \$\endgroup\$
    – Dennis
    May 30, 2015 at 21:00
  • \$\begingroup\$ @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. \$\endgroup\$ May 30, 2015 at 21:04
  • 1
    \$\begingroup\$ 25 bytes: q~S2*{mF{~'^'{@j'}'*}/;}j \$\endgroup\$
    – Dennis
    May 31, 2015 at 2:18

Pyth - 39 34 32 28 bytes

Thanks Jakube

Defines a function y which takes an integer:



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:


Mathematica, 106 102 101 - 50 = 51 bytes


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

  • 102 · 5
  • 1202³ · 3 · 5
  • 163842²˙⁷
  • \$\begingroup\$ Nice use of CenterDot to avoid Times. I'm still trying to figure out where the recursion takes place. \$\endgroup\$
    – DavidC
    May 28, 2015 at 13:39
  • \$\begingroup\$ @DavidCarraher #0 refers to the innermost pure function without argument names. \$\endgroup\$ May 28, 2015 at 16:23
  • \$\begingroup\$ Thanks. First time I have heard about this use of # \$\endgroup\$
    – DavidC
    May 28, 2015 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}
f $1|sed s/}{/}\*{/g


$ ./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:

enter image description here

Let me know if this is not acceptable.

  • 1
    \$\begingroup\$ That works fine. \$\endgroup\$ May 28, 2015 at 17:07

Clip, 36 33



                            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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.