12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What do you mean by partitioning ? \$\endgroup\$ – Optimizer Jan 26 '15 at 17:41
  • \$\begingroup\$ @Optimizer Grouping a list into nonoverlapping sublists. Some languages have this built in, such as Mathematica. \$\endgroup\$ – Geobits Jan 26 '15 at 17:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Level River St Jan 26 '15 at 17:51
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Geobits Jan 26 '15 at 17:54
  • \$\begingroup\$ a built in which allows you to do cartesian product of two list is allowed ? \$\endgroup\$ – Optimizer Jan 26 '15 at 18:21
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Input is fine in that format. \$\endgroup\$ – Geobits Jan 26 '15 at 20:11
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$ – FryAmTheEggman Jan 26 '15 at 22:37
  • \$\begingroup\$ @FryAmTheEggman updated thanks for the tip. \$\endgroup\$ – Maltysen Jan 26 '15 at 22:54
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – isaacg Jan 27 '15 at 9:25
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Maltysen Jan 27 '15 at 20:32
9
\$\begingroup\$

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.

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

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

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

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

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)
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Geobits Jan 26 '15 at 22:30
  • \$\begingroup\$ 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' \$\endgroup\$ – MickyT Jan 27 '15 at 2:42
  • \$\begingroup\$ 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 \$\endgroup\$ – MickyT Jan 27 '15 at 3:02
  • \$\begingroup\$ Now I've tested it on 2012. It should work. \$\endgroup\$ – bmarks Jan 27 '15 at 22:00
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – MickyT Jan 28 '15 at 0:34

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.