# How many ways to write N as a product of M integers?

Given an integer N, count how many ways it can be expressed as a product of M integers > 1.

Input is simply N and M, and output is the total count of distinct integer groups. Meaning you can use an integer more than once, but each group must be distinct (3 x 2 x 2 would not count if 2 x 2 x 3 is present).

Constraints

1 < N < 231
1 < M < 30

Examples

Input 30 2 gives output 3, since it can be expressed 3 ways:

2 x 15
3 x 10
5 x 6


Input 16 3 gives output 1, since there's only one distinct group:

2 x 2 x 4


Input 2310 4 gives output 10:

5 x 6 x 7 x 11
3 x 7 x 10 x 11
3 x 5 x 11 x 14
3 x 5 x 7 x 22
2 x 7 x 11 x 15
2 x 5 x 11 x 21
2 x 5 x 7 x 33
2 x 3 x 11 x 35
2 x 3 x 7 x 55
2 x 3 x 5 x 77


Input 15 4 gives output 0, since it cannot be done.

Rules

Standard code golf loopholes apply, along with standard definitions for input/output. Answers may be a function or full program. Built-in functions for factorization and/or partitioning are not allowed, but others are fine. Code is counted in bytes.

• What do you mean by partitioning ? – Optimizer Jan 26 '15 at 17:41
• @Optimizer Grouping a list into nonoverlapping sublists. Some languages have this built in, such as Mathematica. – Geobits Jan 26 '15 at 17:43
• Is there a time limit? A particularly naive algorithm could take centuries for a large value of M. Simple things like noting there can only be one factor larger than sqrt(N) obviously help a lot. – Level River St Jan 26 '15 at 17:51
• @steveverrill Given the upper limit on N, there should only be 30 (prime) factors max, which speeds things up quite a bit. However, feel free to be naive. If your algorithm is not likely to provide an answer within a few hours, a well-explained proof of concept could help voters decide. – Geobits Jan 26 '15 at 17:54
• a built in which allows you to do cartesian product of two list is allowed ? – Optimizer Jan 26 '15 at 18:21

# Pyth - 242322 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{mSdfqu*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.

• Input is fine in that format. – Geobits Jan 26 '15 at 20:11
• Pyth golf tip: if you get 2 arguments, it is usually shorter to use M which defines the function g of 2 arguments, G and H. This is what I get for this: Ml{msdfqu*GHT1G^r2GH. Always nice to see another Pyth user :) – FryAmTheEggman Jan 26 '15 at 22:37
• @FryAmTheEggman updated thanks for the tip. – Maltysen Jan 26 '15 at 22:54
• This seems to give an incorrect answer for the input 72 3, which returns 5, but there are in fact 6 answers, (2, 2, 18), (2, 3, 12), (2, 4, 9), (2, 6, 6), (3, 3, 8) – isaacg Jan 27 '15 at 9:25
• @isaacg oh ok, I'll revert it back to my 21 char version. I didn't think summing it would work but it seemed to, so i'll go back to repr. Thanks for the catch. – Maltysen Jan 27 '15 at 20:32

# 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.

• I think you can use -~M==N<2 – FryAmTheEggman Jan 26 '15 at 22:15
• @FryAmTheEggman I thought that would give false positives, but indeed it works, thanks to the joint constraints on M and N. Thanks! – xnor Jan 26 '15 at 22:25

# 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


# CJam, 48 bytes

This can be a lot shorter but I have added certain checks to make it work for decent number of M on the online compiler.

q~\:N),2>{N\%!},a*{_,2/)<m*{(+\$}%}*{1a+:*N=},_&,


Try it online here

• This is buggy. Try input 2 1. Expected output: 1. Actual output: 0. – Peter Taylor Jan 27 '15 at 14:27
• @PeterTaylor Sigh. Fixed. – Optimizer Jan 27 '15 at 19:45

## T-SQL 456 373

I'm sure this'll break when the inputs are even close to being large.

Thanks to @MickyT for helping to save a lot of characters with CONCAT and SELECTing instead of multiple SETs.

CREATE PROC Q(@N INT,@M INT)AS
DECLARE @ INT=2,@C VARCHAR(MAX)='SELECT COUNT(*)FROM # A1',@D VARCHAR(MAX)=' WHERE A1.A',@E VARCHAR(MAX)=''CREATE TABLE #(A INT)WHILE @<@N
BEGIN
INSERT INTO # VALUES(@)SET @+=1
END
SET @=1
WHILE @<@M
BEGIN
SELECT @+=1,@C+=CONCAT(',# A',@),@D+=CONCAT('*A',@,'.A'),@E+=CONCAT(' AND A',@-1,'.A<=A',@,'.A')END
SET @C+=CONCAT(@D,'=',@N,@E)EXEC(@C)

• I'd like to upvote this, but I can't find a simple way to test it. Any ideas? Third-party confirmation that it works is good, too. – Geobits Jan 26 '15 at 22:30
• I get a couple of conversion errors we I run it (2012). They appear to be from these statements SET @C+=',# A'+@ and SET @D+='*A'+@+'.A'SET @E+=' AND A'+(@-1)+'.A<=A'+@+'.A' – MickyT Jan 27 '15 at 2:42
• You'll also need to fix SET @C+=@D+'=@N'+@E+' SELECT @'. The @N is inside the quotes making it outside the scope when you execute @C. Also I think you will end up counting duplicates – MickyT Jan 27 '15 at 3:02
• Now I've tested it on 2012. It should work. – bmarks Jan 27 '15 at 22:00
• Works good now :) A couple of place where you can shave some characters. Try using CONCAT to build your strings. Then you can drop the CONVERTs. Try SELECT @+=1,@C+=CONCAT(...),@D+=CONCAT(...),@E+=CONCAT(...) in your WHILE loop. Should save you a reasonable number – MickyT Jan 28 '15 at 0:34