13
\$\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\$
8
  • \$\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\$ 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
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\$
2
  • \$\begingroup\$ I think you can use -~M==N<2 \$\endgroup\$ 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
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\$
6
  • \$\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\$ 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
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\$
0
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\$
2
  • \$\begingroup\$ This is buggy. Try input 2 1. Expected output: 1. Actual output: 0. \$\endgroup\$ 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\$
5
  • \$\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
0
\$\begingroup\$

Jelly, 10 bytes

ḍƇ`ḊœċP€ċ⁸

Try it online!

Assumes that "Built-in functions for factorization and/or partitioning are not allowed" doesn't prohibit the œċ builtin, which is combinations with replacements. If this isn't allowed, we can use a Cartesian product builtin, which is allowed, for 12 bytes: ḍƇ`ḊṗṢ€QP€ċ⁸

How it works

ḍƇ`ḊœċP€ċ⁸ - Main link. Takes n on the left and m on the right
 Ƈ         - Filter the integers, k, between 1 and n where the following is true:
ḍ          -   Does k divide...
  `        -   ...n?
           - This gives a list of divisors
   Ḋ       - Remove the first value, 1
    œċ     - Take all combinations of length m, with replacement
      P€   - Take the product of each
        ċ⁸ - Count occurrences of n
\$\endgroup\$

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.