# Factorials of primes decomposition

You have to decompose a positive integer/fraction as a product of powers of factorials of prime numbers.

For example

22 = (11!)^1 × (7!)^(−1) × (5!)^(−1) × (3!)^(−1) × (2!)^1

10/9 = (5!)^1 × (3!)^(−3) × (2!)^1

Use this special notation: prime number#power to denote each term, e.g. (11!)^4 is denoted as 11#4.

Output the non-zero terms only, with space separation.

The above examples hence become:

22 = 11#1 7#-1 5#-1 3#-1 2#1

10/9 = 5#1 3#-3 2#1

## Input & Output

• You are given a positive number N, that can be either an integer or a fraction of the form numerator/denominator
• The ordered list of the non-zero terms of the decomposition of N, denoted using the special notation
• You are allowed to output the terms as a list/array (containing strings with the special notation #)
• You are allowed to output the terms in any order
• Duplicate prime numbers are allowed
• You are not allowed to use terms that have to the power of 0

## Test cases

6 -> 3#1
5040 -> 7#1
22 -> 11#1 7#-1 5#-1 3#-1 2#1
1/24 -> 3#-1 2#-2
720/121 -> 11#-2 7#2 5#3 3#3


This is code-golf, shortest code wins!

Credits to this puzzle

• Ah ok, the # notation is mandatory, but the join by spaces is optional. Feb 18 at 13:21
• Feb 18 at 13:40
• I’d suggest standard site rules for the output. Feb 18 at 14:10
• May I include terms where power is 0? For example, 7 -> 7#1, 5#-1, 3#-1, 2#0?
– tsh
Feb 19 at 4:28
• @tsh "Output the non-zero terms only" (not sure why though). Feb 19 at 17:11

# Excel (Insider Beta), 350 bytes

=LET(e,IFERROR(FIND("/",A1),0),n,ROW(1:99),m,COLUMN(A:CU),p,SORT(FILTER(n,MMULT(1*(MOD(n,m)=0),n^0)=2),,-1),f,LAMBDA(d,LET(c,MMULT((MOD(d,p^m)=0)*1,n^0),h,LAMBDA(x,y,SUM(INT(x/y^n))),z,TRANSPOSE(MINVERSE(MAKEARRAY(25,25,LAMBDA(x,y,h(INDEX(p,x),INDEX(p,y)))))),MMULT(z,c))),r,IF(e,f(LEFT(A1,e-1))-f(MID(A1,e+1,99)),f(A1)),CONCAT(IF(r,p&"#"&r&" ","")))


Uses MAKEARRAY and LAMBDA which are not widely available yet. Prime factors are not duplicated. Works for all numbers $$\ <= 2^{20} \$$ whose prime factors are all $$\<100\$$.

## Explanation

=LET(e,IFERROR(FIND("/",A1),0), Finds position of "/"; return 0 if not found

n,ROW(1:99), vertical array of 1..99

m,COLUMN(A:CU), horizontal array of 1..99

p,SORT(FILTER(n,MMULT(1*(MOD(n,m)=0),n^0)=2),,-1), reverse sort of all primes $$\<100\$$.

f,LAMBDA(d, f is the function that returns the array of prime factorials for an integer $$\>1\$$.

LET(c,MMULT((MOD(d,p^m)=0)*1,n^0), the vertical array of the number of times each prime divides $$\d\$$.

h,LAMBDA(x,y,SUM(INT(x/y^n))), function that returns the number of times $$\y\$$ divides $$\x!\$$.

MAKEARRAY(25,25,LAMBDA(x,y,h(INDEX(p,x),INDEX(p,y)))) an array indicating how many times each prime divides the factorial of each prime

z,TRANSPOSE(MINVERSE(~)), the inverse of the prime matrix, note: I had to use TRANSPOSE instead of reversing x & y because of some weird precision errors.

MMULT(z,c))), matrix multiply z and c, this transforms the number of times each prime divides d to the powers of prime factorials

r,IF(e,f(LEFT(A1,e-1))-f(MID(A1,e+1,99)),f(A1)), if $$\e>0\$$ then $$\r=f(num.)-f(denom.)\$$ else $$\r=f(n)\$$.

CONCAT(IF(r,p&"#"&r&" ",""))) if an element in $$\r>0\$$ then return $$\p\$$#$$\r\$$ and then concatenate.

• Not sure if it'll help here, but you should take a look at the new insider preview functions - they are certain to help with golfing Apr 27 at 10:25

# JavaScript (Node.js), 120 bytes

p=>q=>(o={},g=(v,t,i=2,h=j=>j?h(--j,g(j,-t)):i)=>{for(;v>1;)v%i?++i:delete o[i*!(o[h(i,v/=i)]=~~o[i]+t)]})(q,~g(p,1))||o


Try it online!

# Python 3, 133 130 bytes

import math
g=lambda i,k=1,n=1,j=2:i%j%i and g(i,k,n,j+1)or(i+k<3)*" "or"%s#%s "%(j,n)*(i>1)+g(k*math.factorial(j-1),i//j or 1,-n)


Try it online!

-3 bytes thanks to loopy walt

-5 more bytes if using python 3.8, as pointed out by ovs

Returns a whitespace separated string.

Uses a recursive algorithm: i is the numerator and k is the denominator. If n is -1, the roles are reversed. j is a potential divisor of i; j is incremented until it divides i. After this, we add j#n to the output and the function is called again with the roles reversed (n is negated). More precisely for inputs i, k we recurse with i=k*fact(j-1),k=i//j. This halts, because every step we are removing one "instance" of the prime number j, and only possibly adding smaller primes.

Just for fun, here are some shorter programs using looser IO rules:

106 bytes: Integer input only, returns flat list

• It's actually cheaper to use math.factorial. Feb 18 at 16:49
• If you require 3.8+ math.perm is shorter than math.factorial
– ovs
Feb 18 at 21:30
• 125 bytes from @ovs 's comment Feb 19 at 4:52

# 05AB1E, 30 bytes

þ>LD(«ZÅPâæ¦.Δε!sm}PI.EQ}í'#ý


Outputs as a list of strings. Can output with duplicated prime numbers as allowed in the rules (e.g. 3/4 results in ["3#1","2#-1","2#-2"] instead of [3#1","2#-3"]).
Brute-force approach, so very slow and times out for most test cases.

Explanation:

þ         # Keep the digits of the (implicit) input, potentially removing the "/"
# for fractions
>        # Increase it by 1 (for edge case input=1 or 1/1)
LD(«    # Convert it into a [value,-value]-ranged list without 0:
L       #  Pop the copy and push a list in the range [1,value]
D      #  Duplicate this list
(     #  Negate each value
«    #  Merge the two lists together
Z       # Push the maximum (without popping), which is the value again
ÅP     # Pop and push a list of primes <= this value
â   # Cartesian power to create all possible pairs of the two lists
æ  # Get the powerset of this list of pairs
¦ # Remove the leading empty list (for edge case input=1 or 1/1 again,
# because the product of an empty list is 1)
.Δ        # Find the first result which is truthy for:
ε       #  Map the list of pairs to:
#   Pop and push the values in the pair separated to the stack
!     #   Take the factorial on the second
s    #   Swap so the other is at the top
m   #   Exponent the two together
}P      #  After the map: take the product of the values
I     #  Push the input
.E   #  Evaluate it as Elixir code, which calculates the value for factorial
#  inputs and will keep integer inputs unchanged
Q  #  Check if they're the same
}í       # After we've found our result: reverse each inner pair
'#ý   '# Join each inner pair with "#"-delimiter
# (after which the list is output implicitly as result)


# JavaScript (Node.js), 222 bytes

x=>([n,d=1]=x.split('/'),(f=r=>r<2?'':(((i=y=>y<2||r%y&&i(~-y))(~-r)?v=(q=s=>s%r?0n:-~q(s/r))(n,w=q(d)):v=w=0n)-w?' '+r+'#'+(v-w):'')+f(~-r,n*=(F=n=>n?n*F(~-n):1n)(r)**w,d*=F(r)**v))((n=(z=BigInt)(n))>(d=z(d))?n:d).trim())


Try it online!

.trim() could be removed (-7 bytes) if you were willing to tolerate an extraneous space at the start of the output.

# Charcoal, 94 89 bytes

≔Ｉ…⪪⁺Ｓ/1¦/²θ≔Πθη≔²ζＷ⊖η¿﹪ηζ≦⊕ζ≧÷ζηＷ⊖ζ¿∨¬⬤…²ζ﹪ζκΠ﹪θζ≦⊖ζ¿¬Σ﹪θζ≧÷ζθ«Ｉζ#⌕﹪θζ⁰1→ＵＭθ⎇﹪κζ×κΠ…·¹ζκ


Try it online! Link is to verbose version of code. Outputs each prime factorial once per power. Explanation:

≔Ｉ…⪪⁺Ｓ/1¦/²θ


Append "/1" to the input in case it's a single integer, then split it on "/" and take the first two values.

≔Πθη≔²ζＷ⊖η¿﹪ηζ≦⊕ζ≧÷ζη


Find the largest prime number dividing either the numerator or denominator.

Ｗ⊖ζ¿∨¬⬤…²ζ﹪ζκΠ﹪θζ≦⊖ζ


Loop though the prime numbers down to 2, decrementing if the current number is not prime or does not divide either the numerator or denominator.

¿¬Σ﹪θζ≧÷ζθ«


If the current prime number divides both numerator and denominator, start reducing the fraction to its lowest terms, otherwise:

Ｉζ#⌕﹪θζ⁰1→


Print the current prime number with "#-1" if it's a factor of the denominator or "#1" if it's a factor of the numerator, leaving a space between prime factorials.

ＵＭθ⎇﹪κζ×κΠ…·¹ζκ


Multiply whichever isn't a factor by the factorial of the prime.

# Python3, 461 bytes:

from itertools import*
import math
def s(n=1):
while(n:=n+1):
if all(n%i for i in range(2,n)):yield n
r=lambda x:pow(*x[0][:-1])*(not x[1:]or r(x[1:]))
F=math.factorial
def f(n):
q,Q=[[[],2,s()]],[]
while q:
p,I,v=q.pop(0)
for i in product(*[range(-I,I)]*len(p)):
if all(i)and p and round(r([[a,z,c]for(a,c),z in zip(p,i)]),4)==round(n,4):return' '.join(f'{b}#{j}'for(_,b),j in zip(p,i))
q+=[[p+[[F(P:=next(v)),P]],I,s(P)],[p,I+1,s(P)],[p,I,s(P)]]


Try it online!

Basic brute force solution, but still runs quickly on the test cases.

• Isn't 1 if not x[1:]else r(x[1:]) just not x[1:]or r(x[1:])? You can also remove the space at return' and merge the last three lines to q+=[[p+[[F(P:=next(v)),P]],I,s(P)],[p,I+1,s(P)],[p,I,s(P)]]. Feb 18 at 15:59
• Save one byte by defining your own factorial function rather than using math.factorial and then removing import math. Feb 18 at 16:01