8
\$\begingroup\$

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;
}
alert(primeFactorize(+prompt()));

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.

\$\endgroup\$
14
  • 17
    \$\begingroup\$ It would help to provide examples of input and output. \$\endgroup\$
    – DavidC
    May 28 '15 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 '15 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 '15 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 '15 at 13:42
  • 1
    \$\begingroup\$ @Zgarb Any format that works (ex. 2^(5^11*11^(2^7))*541). \$\endgroup\$ May 28 '15 at 14:12
14
\$\begingroup\$

Pyth, 27 - 50 = -23 bytes

Lj\*m+ed?+\^jyhd`HthdkrPb8

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

pic_small

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

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!

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.

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

Pyth - 39 34 32 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
\$\endgroup\$
0
4
\$\begingroup\$

Mathematica, 106 102 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²˙⁷
\$\endgroup\$
3
  • \$\begingroup\$ Nice use of CenterDot to avoid Times. I'm still trying to figure out where the recursion takes place. \$\endgroup\$
    – DavidC
    May 28 '15 at 13:39
  • \$\begingroup\$ @DavidCarraher #0 refers to the innermost pure function without argument names. \$\endgroup\$ May 28 '15 at 16:23
  • \$\begingroup\$ Thanks. First time I have heard about this use of # \$\endgroup\$
    – DavidC
    May 28 '15 at 17:29
3
\$\begingroup\$

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:

enter image description here

Let me know if this is not acceptable.

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

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 "*"          -.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

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