Given a positive integer, n, return the number of possible ways such that k positive integers multiply to n. Order matters.
Example
n = 24
k = 2
(1, 24), (2, 12), (3, 8), (4, 6), (6, 4), (8, 3), (12, 2), (24, 1) -> 8
n = 100
k = 1
100 -> 1
n = 20
k = 3
(1, 1, 20), (1, 2, 10), (1, 4, 5), (1, 5, 4), (1, 10, 2), (1, 20, 1),
(2, 1, 10), (2, 2, 5), (2, 5, 2), (2, 10, 1), (4, 1, 5), (4, 5, 1),
(5, 1, 4), (5, 2, 2), (5, 4, 1), (10, 1, 2), (10, 2, 1), (20, 1, 1) -> 18
I tried to count all the divisors of the number and multiply the result by 2, but this only works if k=2. and what if k>2 I can't even imagine
from itertools import *
divs = lambda n: [(d, n // d) for d in range(1, int(n ** 0.5) + 1) if n % d == 0]
new = list(divs(24))
print(new) #output [(1, 24), (2, 12), (3, 8), (4, 6)]
print(len(new)*2) #output 8
Recursion is probably the easiest way to approach it:
def prodWays(N,k):
if k < 2: return k
return sum(prodWays(N//f,k-1)+prodWays(f,(k-1)*(f*f<N))
for f in range(1,int(N**0.5)+1) if N%f==0)
output:
print(prodWays(24,2)) # 8
print(prodWays(20,3)) # 18
from math import factorial
print(prodWays(factorial(8),8)) # 7907328
Note: (k-1)*(f*f<N) is used to avoid double counting the root when N is a square number.
The problem with this approach is that it will become slow for larger values of N and k.
Another way to approach this is to break down the number into its prime factors and compute the number of ways that these factors can be spread over the k values:
def primeFactors(N):
p,i = 2,1
while p*p<=N:
count = 0
while N%p==0:
count += 1
N //= p
if count: yield p,count
p,i = p+i,2
if N>1: yield N,1
import sys
sys.setrecursionlimit(5000)
from functools import lru_cache
@lru_cache(1024**2)
def spread(n,k):
if not n or k==1: return 1
return sum(spread(n-i,k-1) for i in range(n+1))
def prodWays(N,k):
result = 1
for factor,count in primeFactors(N):
result *= spread(count,k)
return result
output:
print(prodWays(24,2)) # 8
print(prodWays(20,3)) # 18
from math import factorial
print(prodWays(factorial(8),8)) # 7907328
print(prodWays(factorial(10),10)) # 9559907500
print(prodWays(1_000_000_000_000,100)) # 15552492827131124616917824205625
print(prodWays(1_000_000_000_000,200)) # 139745851268403591681228469699689610000
print(prodWays(1_000_000_000_000,500)) # 337590999829671459601812675011066296958938890625
print(prodWays(1_000_000_000_000,1000)) # 4970893321600801353542680174879865699066125982010250000
print(prodWays(factorial(14),1000)) # 55796977547671530595085675778733683013300000000000000000
The spread() function computes the number of ways n identical items can be spread across k positions (from 0 to n at each position always totalling n). It looks like a variant of the partition problem. I only know how to compute this using recursion (or iterations) so this solution, although much faster, is still constrained by Python's recursion limit (which I had to boost up for the larger values). The lru_cache decorator is used to optimize the recursion by automatically saving some of the result and thus avoid recalculating the same values.
An iterative version of the spread() function with "manual" caching can avoid these limitations but it is a bit more complex:
known = dict()
def spread(n,k):
todo = [(n,k)]
while todo:
n,k = todo.pop()
if (n,k) in known:
continue
if k==1 or not n:
known[n,k] = 1
continue
unknown = [ (n-i,k-1) for i in range(n+1) if (n-i,k-1) not in known ]
if unknown:
todo.append((n,k))
todo.extend(unknown)
continue
known[n,k] = sum( known[n-i,k-1] for i in range(n+1) )
return known[n,k]