Factorials of primes decomposition

Question

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

Answer 1

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.

Try it online or verify some test cases using values below 3 by replacing the þ>.

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)

Answer 2

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.

Answer 3

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.

Answer 4

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!

• +13 bytes if output as an array.
  • +26 more bytes to format the string with hash and spaces.
• -9 bytes if we only accept integer inputs.
  • -34 more bytes if output duplicate items

Answer 5

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.

Answer 6

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

Answer 7

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.