How many ways to write N as a product of M integers?
Python 3, 59
f=lambda N,M,i=2:i<=N and f(N/i,M-1,i)+f(N,M,i+1)or-~M==N<2
We count up potential divisors i
. With the additional argument i
as the lowest allowed divisor, the core recursive relation is
f(N,M,i)=f(N/i,M-1,i)+f(N,M,i+1)
For each i
, we either choose to include it (possible as a repeat), in which case we divide the required product N
by i
and decrement M
. If we don't, we increase i
by 1, but only if i<N
, since there's no use checking divisors greater than N
.
When the minimum divisor i
exceeds N
, there's no more potential divisors. So, we check if we've succeeded by seeing if M==0 and N==1
, or, equivalently, M+1==N==1
or M+1==N<2
, since when M+1==N
, the mutual value is guaranteed to be a positive integer (thanks to FryAmTheEggman for this optimization).
This code will cause a stack overflow for N
about 1000 on most systems, but you can run it in Stackless Python to avoid this. Moreover, it is extremely slow because of its exponential recursive branching.
Pyth - 24 23 22 21 bytes
Not a complicated solution. Will be golfing more. Just takes cartesian product of lists and filters. Same strategy as @optimizer (I'm guessing because of his comment, didn't actually decipher that CJam) Thanks to @FryAmTheEggman for 2 bytes and trick with M.
Ml{m`Sdfqu*GHT1G^r2GH
Defines a function g
with args G
and H
M function definition of g with args G and H
l length of
{ set (eliminates duplicates)
m map
`Sd repr of sorted factors so can run set (on bash escape ` as \`)
f filter
q G equals first arg
u*GHT1 reduce by multiplication
^ H cartesian product by repeat second arg
r2G range 2 to first arg
Worked on all test args except last, was too slow on that one but there is no time limit given.
Ruby, 67
f=->n,m,s=2,r=0{m<2?1:s.upto(n**0.5){|d|n%d<1&&r+=f[n/d,m-1,d]}&&r}
Actually reasonably efficient for a recursive definition. For each divisor pair [d,q]
of n, with d
being the smaller one, we sum the result of f[q,m-1]
. The tricky part is that in the inner calls, we limit factors to ones greater than or equal to d so that we don't end up double-counting.
1.9.3-p327 :002 > f[30,2]
=> 3
1.9.3-p327 :003 > f[2310,4]
=> 10
1.9.3-p327 :004 > f[15,4]
=> 0
1.9.3-p327 :005 > f[9,2]
=> 1