8
\$\begingroup\$

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

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

7 Answers 7

2
\$\begingroup\$

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.

\$\endgroup\$
1
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

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

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)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 94 89 bytes

≔I…⪪⁺S/1¦/²θ≔Πθη≔²ζW⊖η¿﹪ηζ≦⊕ζ≧÷ζηW⊖ζ¿∨¬⬤…²ζ﹪ζκΠ﹪θζ≦⊖ζ¿¬Σ﹪θζ≧÷ζθ«Iζ#⌕﹪θζ⁰1→UMθ⎇﹪κζ×κΠ…·¹ζκ

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

≔I…⪪⁺S/1¦/²θ

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

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

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

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

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:

Iζ#⌕﹪θζ⁰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.

UMθ⎇﹪κζ×κΠ…·¹ζκ

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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)]]. \$\endgroup\$ Feb 18 at 15:59
  • \$\begingroup\$ Save one byte by defining your own factorial function rather than using math.factorial and then removing import math. \$\endgroup\$
    – ophact
    Feb 18 at 16:01

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.