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\$
  • 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\$ – LegionMammal978 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\$ – LegionMammal978 May 28 '15 at 14:12
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\$
  • \$\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\$ – Martin Ender 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\$ – Martin Ender May 30 '15 at 21:04
  • 1
    \$\begingroup\$ 25 bytes: q~S2*{mF{~'^'{@j'}'*}/;}j \$\endgroup\$ – Dennis May 31 '15 at 2:18
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\$
  • 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
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\$
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\$
  • \$\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\$ – LegionMammal978 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
    \$\begingroup\$ That works fine. \$\endgroup\$ – SuperJedi224 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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