Prime Factorization - but on the exponents too

Question

Though there is a prime factorization challenge and it's here, this, I feel, will be a bit more interesting than that one.

To understand this, let's have an example; I will use 5,184 for this. \$5184 = 2^6 \times 3^4\$. However, for this challenge, such a factorization is insufficient - the reason is that 6 and 4 are composite - therefore, we must factorize them too: \$5184 = (2^{2*3}) \times (3^{2^2})\$. This containes a total of 0 composite numbers, so we are done.

Your task is to prime-factorize a number. However, unlike in here, if you see a composite number in the exponent, you must then factorize this too.

Input will be a number or a string, and output can be a nested array, nested list, or string.

You must use the fewest numbers necessary: 65536 is \$2^{2^{2^2}}\$, not \$ 2^{2 \times 2 \times 2 \times 2}\$ or anything similar - however, \$2^{2^2}\$ and \$2^{2 \times 2}\$ are identical and as such, can be used freely - make of it what you will.

Some example answers to show the format:

5184, 65536 - see above

\$2^{144} = 2^{2^{2^2} \times 3^2}\$ or [2, [2, [2, 2], [3, [2]]]], or "2^(2^2^2)*(3^2)", where the brackets are necessary to separate the terms.

\$5^{125} = 5^{5^3}\$, or [5, [5, [3]]], or 5^5^3 (note, as \$a^{b^c} == a^{(b^c)}\$, the brackets are not necessary.

\$47,258,883 = 3^9 \times 7^4 = 3^{3 \times 3} \times 7^{2 \times 2}\$ or \$3^{3^2} \times 7^{2^2}\$ or [3, [3, 2], 7, [2, 2]] or [3, [3, [2]], 7, [2, [2]]] or 3^(3 \times 3) \times 7^(2 \times 2) or 3^3^2 \times 7^2^2

\$2^{81} = 2^{3^{2 \times 2}}\$ or similar (see above)

\$5^{343} * 7^{125} = 5^{7^3} \times 7^{5^3}\$ or similar (see above)

And finally, to check your prime factorization technique:

\$2^{2162160} \times 3^{1441440} \times 5^{1081080} = 2^{2^{2^2} \times 3^3 \times 5 \times 7 \times 11 \times 13} \times 3^{2^5 \times 3^2 \times 5 \times 7 \times 11 \times 13} \times 5^{2^3 \times 3^3 \times 5 \times 7 \times 11 \times 13}\$

You may pick any output format and use any non-number or newline separator, and you may include any number of trailing/leading newlines in output, but you must be consistent about your choice and state it in your answer.

As always, this is code-golf - shortest code wins.

Answer 1

Jelly, 15 bytes

¹ÆFṛÇṭ¥Ị?@/€$Ẓ?

Try it online!

A full program that takes the number and outputs the answer.

This isn't a link because I am using "last link" to refer to itself, so it would break as a link on its own. I fix this for my test suite by making the last link a single atom that calls the next link. For whatever reason, "this link" breaks due to arity related reasons, or something like that. Not sure why.

If Arnauld's return format is acceptable where 1 exponents are returned as [x, []], then:

Jelly, 12 bytes

¹ÆF,ß}¥/€$Ẓ?

Try it online!

¹ÆF,ß}¥/€$Ẓ?  Main link
           ?  If the input
          Ẓ   is prime
¹             return the input itself
 ()(    )$    otherwise, (call last two links)
 ÆF           compute [prime, exponent] pairs
        €     for each pair
       /      reduce (convert pairs into left and right dyad arguments)
   -()¥       (over last two links)
   ,          pair the left argument (the prime) with
    ß         this link (recurse) called on
     }        the right argument (the exponent)

Explanation

This one is a bit complex so, here's a shitty hand-drawn breakdown:

Or, if you enjoy being able to read:

¹ÆFṛÇṭ¥Ị?@/€$Ẓ?
              ?  if
             Ẓ   the input is prime
¹                return the input itself
                 otherwise
 ()(       )$    [combine last two into a monad]
 ÆF              compute [prime, exponent] factorization
           €     for each pair
          /      reduce over (convert pair into left, right arguments for a dyad)
         @       the following dyadic relation, with the arguments swapped
        ?        if
       Ị         the left argument is insignificant (-1 <= ? <= 1) - the left argument is the exponent
   ṛ             return the right argument (just the prime)
                 otherwise
    --¥          [combine last two into a dyad]
    Ç            call this link again on the exponent (technically "call last link" due to weird behavior)
     ṭ           and append that factorization to the prime itself

Answer 2

Jelly, 8 bytes

ÆF¹ßẒ?€€

A monadic Link accepting a positive integer that yields a list (Note that [] represents an empty product).

Try it online!

How?

ÆF¹ßẒ?€€ - Link f: integer
ÆF       - prime-factorisation
             e.g. 144 -> [[2,4],[3,2]]
                  (note that 1 -> [])
       € - for each ([prime,exponent] pair in that)
      €  -   for each (v in [prime,exponent]):
     ?   -     if...
    Ẓ    -     ...condition: is prime?
  ¹      -     ...then: no-op
   ß     -     ...else: call this Link with the same arity -> f(v)

Answer 3

J, ³⁴ 32 bytes

[:(;<@$:)`(<@[)@.(1=])/"1@|:2&p:

Try it online!

Outputs J boxed structure. Eg, f 1584 is:

┌─┬───────┐
│2│┌─┬─┐  │
│ ││2│3│  │
│ │└─┴─┘  │
├─┼───────┤
│3│┌─┬───┐│
│ ││2│┌─┐││
│ ││ ││2│││
│ ││ │└─┘││
│ │└─┴───┘│
└─┴───────┘

• 2&p: is a built in that produces the primes and their exponents as two lists, like:

     2&p: 5184
  2 3
  6 4
  

• [:(...)/"1@|: transpose and apply what's in parens to each row, putting it between the two elements so that [ and ] are the left and right args in what follows...

• (;<@$:)`(<@[)@.(1=]) If the right arg is 1 (ie, we've reached a prime), put it in a single box and return (<@[). Otherwise put the left arg in a left box, and into the right box put the function applied recursively to the right arg $:.

Answer 4

JavaScript (ES6), 73 bytes

Returns nested arrays, where \$k^1\$ is [k,[]].

f=(n,k=2,a=[],i,b=i?[...a,k,f(i)]:a)=>k>n?b:n%k?f(n,k+1,b):f(n/k,k,a,-~i)

Try it online!

Answer 5

Japt, 16 bytes

Japt suffering from its lack of a prime/exponent built-in again. Uses the empty array if the exponent is 1.

*j ªUk ü Ëâ pßDl

Try it

*j ªUk ü Ëâ pßDl     :Implicit input of integer U
*                    :Multiply by
 j                   :Is prime?
   ª                 :Logical OR with
    Uk               :Prime factors of U
       ü             :Group by value
         Ë           :Map each D
          â          :  Deduplicate
            p        :  Push
             ß       :    Recursive call with argument
              Dl     :      Length of D

Answer 6

Stax, 15 bytes

╛⌐í₧?uò╗∩¿7d∩í±

Run and debug it

a pretty straightforward recursion.

-3 from recursive.

Answer 7

Core Maude, 283 bytes

mod F is ex RAT *(sort Nat to N). op __ : N N -> N[id: 1]. op e : N N ->
N[right id: 1]. vars A B C D : N . eq e(A,0)= 1 . op f : N -> N . eq f(A)=
A,2,0 . op _,_,_ : N N N -> N . ceq A,B,0 = A if A < B . ceq A,B,C = D,B,s C
if D := A / B . eq A,B,C = e(B,f(C))(A,s B,0)[owise]. endm

The f function will evaluate the factorization of its input, a natural number. In the output, the __ (juxtaposition) operator represents multiplication, and the e function represents exponentiation. So the term e(2, 3) (e(3, 3) (5 (7 (11 13)))) represents \$2^3 \times 3^3 \times 5 \times 7 \times 11 \times 13\$.

Example Session

             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Thu Jun  3 08:42:33 2021
Maude> set show stats off .
Maude> set show timing off .
Maude> set show command off .
Maude> mod F is ex RAT *(sort Nat to N). op __ : N N -> N[id: 1]. op e : N N ->
> N[right id: 1]. vars A B C D : N . eq e(A,0)= 1 . op f : N -> N . eq f(A)=
> A,2,0 . op _,_,_ : N N N -> N . ceq A,B,0 = A if A < B . ceq A,B,C = D,B,s C
> if D := A / B . eq A,B,C = e(B,f(C))(A,s B,0)[owise]. endm
Maude> red f(5184) .
result N: e(2, 2 3) e(3, e(2, 2))
Maude> red f(65536) .
result N: e(2, e(2, e(2, 2)))
Maude> red f(1081080) .
result N: e(2, 3) (e(3, 3) (5 (7 (11 13))))
Maude> red f(1441440) .
result N: e(2, 5) (e(3, 2) (5 (7 (11 13))))
Maude> red f(2162160) .
result N: e(2, e(2, 2)) (e(3, 3) (5 (7 (11 13))))
Maude> red f(47258883) .
result N: e(3, e(3, 2)) e(7, e(2, 2))

Ungolfed

mod F is
    ex RAT * (sort Nat to N) .

    op __ : N N -> N [id: 1] .
    op e : N N -> N [right id: 1] .

    vars A B C D : N .

    eq e(A, 0) = 1 .

    op f : N -> N .
    eq f(A) = A, 2, 0 .

    op _,_,_ : N N N -> N .
    ceq A, B, 0 = A if A < B .
    ceq A, B, C = D, B, s C if D := A / B .
    eq A, B, C = e(B, f(C)) (A, s B, 0) [owise] .
endm

Rather than use the built-in nested list module (LIST*), I opted to define my own output operators __ and e. Since Maude allows operators to be declared with identity elements, this saves me having to specify any special rules for 1 (i.e., don't show it).