Check if a number is a product of consecutive integer numbers

Question

Some numbers such as: 6, 12, 20, 30, 42, 56, 60, 90, 120 and so on as can be expressed as a product of consecutive integer numbers as shown below.

6   = 2 * 3  
12  = 3 * 4  
30  = 5 * 6
60  = 3 * 4 * 5  
90  = 9 * 10  
120 = 4 * 5 * 6  

Write a program or function that outputs a list of consecutive integers which product equals the specified number.

Examples of numbers that are not fit for this logic are:

99  = 9 * 11  (Product of non-consecutive numbers)
121 = 11 * 11 (Same numbers)
2   = 1 * 2   (Product of itself and 1)
13  = 13      (Product of only one number)

Please note that for the case of 2 = 2 * 1, we do not consider it as a valid result, as a integer multiplied by 1 gives the same result. For this question, we would consider only integers >= 2 in the product.

Input

A valid 32-bit positive integer. Can be from standard input, a function argument, etc.

Output

A list of consecutive integer numbers >= 2 (in either ascending or descending order). If there are several combinations of consecutive integers, just provide one instance will do. If you provide more, its fine.

Restrictions

The code should take a reasonable amount of time (< 5 minutes) to run on a standard computer for all valid inputs (positive 32-bit integers). If there is a consecutive integer product, the code should output one or more within the time limit. Else, the code should terminate with no output within the time limit.

This is code golf, so the shortest code in bytes wins.

Answer 1

Java - 124

String f(int t){int s=2,h=3,p=s,i;String o="";for(;p!=t&&s*s<t;p=p<t?p*h++:p/s++);if(p==t)for(i=s;i<h;o+++=i+" ");return o;}

Starting at 2, this loops until the start number is > the square root of the target (or target is reached exactly). If the product is low, it multiplies by the high number and increments it. If high, it divides by the starting number and increments it.

For example, for 30, it would check:

2*3     = 6 (too low, multiply)
2*3*4   = 24 (too low, multiply)
2*3*4*5 = 120 (too high, divide)
3*4*5   = 60 (too high, divide)
4*5     = 20 (too low, multiply)
4*5*6   = 120 (too high, divide)
5*6     = 30 (bingo!)

Outputs a space-separated string of factors in ascending order.

With line breaks:

String p(int t){
    int s=2,h=3,p=s,i;
    String o="";
    for(;p!=t&&s*s<t;p=p<t?p*h++:p/s++);
    if(p==t)
        for(i=s;i<h;o+=i+" ");
    return o;
}

Answer 2

Python - 104 97 95 92 try it

n=input()
s=i=2
c=1
while s<n:
 s*=i+c;c+=1
 if s==n:print range(i,i+c)
 if s/n:i+=1;s,c=i,1

If n is, e.g., set to 120 beforehand, the program outputs the two solutions:

[2, 3, 4, 5]
[4, 5, 6]

Answer 3

Clojure - 127 109 bytes

(defn f[x](first(for[r[range]y(r 2 x)v[(take-while #(<=(apply * %(r y %))x)(r y x))]:when(=(apply * v)x)]v)))

Example:

(map f [6 12 30 60 90 120 1404816 99 121 2 13])
=> ((2 3) (3 4) (5 6) (3 4 5) (9 10) (2 3 4 5) (111 112 113) nil nil nil nil)

Explanation:

This is basic, quite unoptimized functional approach. I create a lazy list of all the possibilities using a simple loop over them (it does skip all combinations which would give too big numbers, preventing overflow) and take the first of them. If no possibilities exist, it returns nil.

Easiest to test in http://tryclj.com/ .

---

I also now noticed that I can return all the possibilities: 120 bytes 102 bytes, but gives results in a nested list.

(defn f[x](for[r[range]y(r 2 x)v[(take-while #(<=(apply * %(r y %))x)(r y x))]:when(=(apply * v)x)]v))

Example:

(map f [6 12 30 60 90 120 1404816 99 121 2 13])
=> (((2 3)) ((3 4)) ((5 6)) ((3 4 5)) ((9 10)) ((2 3 4 5) (4 5 6)) ((111 112 113)) () () () ())

Answer 4

R, 65 63 61 58 bytes

Edit: -2 bytes, and then -2 more bytes, thanks to Giuseppe

Edit: -3 bytes thanks to Robin Ryder

x=scan();`[`=`for`;i[1:x,j[1:x-i,if(prod(i:j)==x)a=i:j]];a

Try it online!

I really tried to find something cleverer and shorter, but couldn't.
Loops (unusually for R) through all combinations of consecutive integers from 1..x 2..x, printing any that whose product equals x. Breaking out of two loops is very awkward, so its shorter code to just print all the successes. (see explanation of Robin Ryder's improvement below).

Giuseppe's (second) 2-byte saving comes from redefining the array-index operator [] as the for command. This is a classic R golf - since all operations and commands are functions that can be redefined (including indexing and for) - but has the side-effect of making the code almost unreadable afterwards... (and, if you ever used this in 'real' code, it would make all of R almost unuseable afterwards, since indexing is now no longer possible!).

Robin's 3-byte saving skips my previous careful avoidance of non-valid ranges that don't include 1, and instead sets-up the loops so that the last range found will always be valid. So, we just need to remember this (as the variable a here) and output it when we're finished. This has the effect that non-valid inputs leave a undefined, and so 'terminate' with no output by throwing an error.

Answer 5

CJam, 31 bytes

q~:Qmq,A,m*{2f+~,f+_:*Q={p}*}%;

It's a brute-force approach, but execution time is only a couple of seconds using the official Java interpreter.

If you want to test the code using the online interpreter, you should keep the input reasonably low. Anything less than 2²⁶ still works on my machine.

Examples

$ TIME="%e s"
$ time cjam product.cjam <<< 2
0.12 s
$ time cjam product.cjam <<< 6
[2 3]
0.10 s
$ time cjam product.cjam <<< 120
[2 3 4 5]
[4 5 6]
0.12 s
$ time cjam product.cjam <<< 479001600
[2 3 4 5 6 7 8 9 10 11 12]
0.68 s
$ time cjam product.cjam <<< 4294901760
[65535 65536]
1.48 s
$ time cjam product.cjam <<< 4294967295
1.40 s

How it works

q~:Q      " Read from STDIN, interpret the input and save the result in variable “Q”.     ";
mq,       " Push the array [ 0 1 2 … (Q ** 0.5 - 1) ].                                    ";
A,m*      " Push the array [ 0 1 2 … 9 ] and take the Cartesian product.                  ";
{         " For each pair in the Cartesian product:                                       ";
  2f+     " Add 2 to each component.                                                      ";
  ~       " Dump the array's elements on the stack.                                       ";
  ,       " Push the array [ 0 1 2 … n ], where “n” is the topmost integer on the stack.  ";
  f+      " Add “m” to each element, where “m” is the integer below the array.            ";
  _:*     " Duplicate the resulting array and push the product of its elements.           ";
  Q={p}*  " If the product is equal to “Q”, print.                                        ";
}%        " Collect the remaining results into an array.                                  ";
;         " Discard the array from the stack.                                             ";

Answer 6

Java, 162

returns an array of integers, or null if there are no consecutive numbers that exist.

int[] e(int n){for(int i=1;i<n;i++){int h=i+1,c=1,s=i;while(s<n){c++;s*=h++;}if(s==n){int[] o=new int[c];for(int j=0;j<c;j++){o[j]=h-j-1;}return o;}}return null;}

ungolfed:

int[] execute(int input){
    for(int i=1; i<input; i++){
        int highest = i+1, count = 1, sum = i;
        while(sum < input){
            count++;
            sum *= highest++;
        }
        if(sum == input){
            int[] numbers = new int[count];
            for(int j=0; j<count; j++){
                numbers[j] = highest-j-1;
            }
            return numbers;
        }
    }
    return null;
}

Answer 7

C 105 110 try it

n,k,l;main(i){for(scanf("%d",&n);++i<n;)for(k=1,l=i;k<n;)if(k*=l++,k==n)for(l=n;l/=i;)printf("%d ",i++);}

144 with bonus: this one iterates through every number and finds matching products

main(i,j,k,l,m){for(scanf("%d",&m);++i<13;)for(j=0;++j<46341-i;){for(l=k=1;k<=i;)l*=j+k++;if(l==m)for(puts(""),k=0;k<i;)printf("%d ",j+k+++1);}}

Answer 8

PHP 258 chars, 201 not counting factorial function.

The simplest way to mathematically express "consecutive factors that equal a number" is X!/Y! Where X is the highest number and Y is the lowest minus one. Unfortunately I stopped taking calculus before I learned to solve Z = X!/Y!, so I had to bruteforce it a little.

Messy, ungolfed version:

<?php
// PHP does not define a factorial function, so I've kludged one in.
function fact($n) {
    $r = 1;
    for($i=$n; $i>1; $i--) {
        $r *= $i;
    }
    return $r;
}

$input = intval($argv[1]);

if( $input < 2 ) { die('invalid input'); }

printf("input: %s\n", $input);

$max=min(ceil(sqrt($input)),170); // integer breakdown for > 170!
$grid = array();
for( $x=1;$x<$max;$x++ ) {
    for( $y=$max;$y>=1;$y-- ) {
        if( $y >= $x ) { continue; } // Skip results that would be < 1
        $cur = fact($x)/fact($y);
        if( $cur > $input ) { // too large!
            echo "\n"; continue 2;
        }
        if( $cur == $input ) { //just right
            printf("%7d\n\nFound %s == %s\n", $cur, implode(' * ', range($y+1, $x)), $cur);
            break 2;
        }
        printf("%7d ", $cur);
    }
    echo "\n";
}
if($cur!=$input){printf("No consecutive factors produce %d\n", $input);}

Example output:

input: 518918400

  2
  3       6
  4      12      24
  5      20      60     120
  6      30     120     360     720
  7      42     210     840    2520    5040
  8      56     336    1680    6720   20160   40320
  9      72     504    3024   15120   60480  181440  362880
 10      90     720    5040   30240  151200  604800 1814400 3628800
 11     110     990    7920   55440  332640 1663200 6652800 19958400 39916800
 12     132    1320   11880   95040  665280 3991680 19958400 79833600 239500800 479001600
 13     156    1716   17160  154440 1235520 8648640 51891840 259459200
 14     182    2184   24024  240240 2162160 17297280 121080960
 15     210    2730   32760  360360 3603600 32432400 259459200
 16     240    3360   43680  524160 5765760 57657600 518918400

Found 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 == 518918400

Golfed:

<? function f($n){$r=1;for($i=$n;$i>1;$i--)$r*=$i;return $r;}$i=$argv[1];$m=min(ceil(sqrt($i)),170);for($x=1;$x<$m;$x++){for($y=$m;$y>0;$y--){if($y>=$x)continue;$c=f($x)/f($y);if($c>$i)continue 2;if($c==$i){$y++;echo "$y $x";break 2;}}}if($c!=$i){echo 'No';}

Output:

[sammitch@vm ~/golf] time php consecutive_golf.php 518918400
9 16
real 0m0.019s
user 0m0.011s
sys  0m0.009s
[sammitch@vm ~/golf] time php consecutive_golf.php 518918401
No
real 0m0.027s
user 0m0.017s
sys  0m0.011s

I was not expecting the run time to be quite this quick!

Answer 9

Pyth, 35

JvwKr2 4W-ZJ~@KgJZ1=YurGHK=Zu*NTY)Y

Note: My code actually finds the shortest representation of the input as a representation of consecutive integers >=2, so on invalid input it will print a 1 element list, possibly after a very long time. Since the problem statement says the input will be valid, I assume this is OK.

Short explanation:

Essentially, the program stores the upper and lower limits of a range, calculates the product of the numbers in the range using a reduce, adjusts the endpoints as necessary, and repeats until the product equals the input.

Long explanation:

For each snippet of code, I will give equivalent python, as well as a more detailed explanation and reasoning.

Jvw => J=eval(input())

Standard way to take input in Pyth.

Kr2 4 => K=range(2,4) => K=[2,3]

Here's the first weird part: Instead of storing the endpoints as separate variables, I'm storing them as elements of a list. The reason will soon be clear. Also, instead of doing a simple assignment, which in Pyth would be K[2 3), I'm using a range to save a character.

W-ZJ => while Z-J => while Z!=J

At this point, you might ask, "What is Z? You haven't defined it." In Pyth, all variables come predefined. Z happens to start as 0. However, Z will be set to the value of the product later, so this check will serve to end the while loop once the list is at the correct value.

~@K>JZ1 => K[J>Z] += 1

Here's why I'm storing the values in a list, not in separate variables: I want to increment one of the two endpoints, depending on whether the product is currently too high or too low. That would be a rather long conditional if the endpoints were separate variables, but with the magic of list indexing, it becomes short. Also, the fact that this check comes before the product, and the fact that Z is initialized to 0, ensure that K will be [2,4] by the time we first take the product, which are the proper endpoints.

=YurGHK => Y=reduce(lambda G,H: range(G,H),K) => Y=range(K[0],K[1])

Now, I need the actual list that the product will be taken over, and that will be printed out if we succeed. Clearly, we will use a range function. The trickiness lies in obtaining the inputs to the range function. The obvious way to do this, by indexing the list, would be =Yr'K@K1. However, by using a reduce function on this two element list, we can shorten that by a character.

=Zu*NTY => Z=reduce(lambda N,T: N*T,Y)

And now, for the whole point of this affair, the reduce operation to find the product of the list.

) => End while

Y => print(Y)

On success, print the list.

Example run:

$ cat seq_prod 
JvwKr2 4W-ZJ~@K>JZ1=YurGHK=Zu*NTY)Y

$ cat seq_prod | python3 pyth.py
<debug stuff>
==================================================
[9, 10, 11, 12, 13, 14, 15, 16]

Answer 10

Jelly, 7 bytes

’ḊẆP=¥Ƈ

Try it online!

-1 byte thanks to Shaggy's help!

How it works

’ḊẆP=¥Ƈ - Main link. Takes an integer n on the left
’       - Decrement n
 Ḋ      - Generate the range [2, 3, ..., n-1]
  Ẇ     - Yield all contiguous sublists: [[2], [3], [4], [5], ..., [2, 3, 4, ... n-1]]
     ¥Ƈ - Keep those lists where the following is true:
   P    -   The product of the list...
    =   -   ...is equal to n

Answer 11

Husk, 9 bytes

fo=¹ΠQ↓2ŀ

Try it online!

Answer 12

Vyxal m, 9 7 6 bytes

ḢÞSvΠc

-2 bytes thanks to emanresu A

-1 byte thanks to Steffan

Try it online, or verify more test cases.

Explanation:

Ḣ       # Range from 2 to n-1 (m flag makes it n-1)
 ÞS     # All sublists
   vΠ   # Calculate the product on each
     c  # Contains the input

Answer 13

Java - 115

void f(int i){for(int j=2;j<i;j++)for(int k=1,x=j;(x*=j+k)<i;k++);if(x==i)for(i=j;i<j+k;i++)System.out.println(i);}

Slightly less golfed:

void f(int i) {
 for(int j=2; j<i; j++)
  for(int k=1, x=j; (x*=j+k) < i; k++);
   if(x == i)
    for(i=j; i<j+k; i++)
     System.out.println(i);
}

Answer 14

Matlab (88)

Code expects number to be stored in x and output in l.

for n=2:12
r=ceil(x^(1/n))
for s=-3*n:n
l=r-s+(1:n)
if prod(l)==x
return 
end;end;l=x;end

Since 13! > 2^32 this code searches only for products of length 2 upto 12. This code has a constant runtime of around 0.001s.

Answer 15

Scala - 86

def p(n:Int)=(2 to n).flatMap(i=>(i to n).map(i to _-1).find(_.product==n)).headOption

This code is very inefficient but optimizing it would only add a few more characters. It uses a functional approach to check the products of all possible consecutive sequences. (a consecutive sequence of integers is represented as a Range object in Scala)

ungolfed:

def product(n: Int): Option[Range] = {
  def productStartingAt(start: Int): Option[Range] =
    (start to n-1).map(start to _).find(_.product == n)
  
  (2 to n).flatMap(i => productStartingAt(i)).headOption
}

Answer 16

CJam does not currently work for large numbers due to long computation time

This is my shortest CJam code. Test at http://cjam.aditsu.net/. It works by: defining input as A; creating an array of all numbers from 0 to A-1; Kicking 0; kicking the smallest numbers until multiplying all numbers in the array is not greater than A; checking if it is greater than A; if not, creating an array from 0 to A-2; and repeating until the answer is found. If none is found, an exception is thrown. I didn't consider that spaces between numbers were needed so they are inlcuded in the second code which is 32 characters long.

ri:A,{)\;,1{;(;_{*}*_A>}gA<}g

ri:A,{)\;,1{;(;_{*}*_A>}gA<}g" "*

Answer 17

Dart - 102 chars

This is a slow implementation. It can be made faster but that requires more characters (like doing the loop only until i*i<n)

f(n,[i=2]){
  t(j,p,a)=>p<n?t(++j,p*j,a..add(j)):p>n?f(n,i+1):a;
  for(;i<n;i++)if(n%i<1)return t(i,i,[i]);
}

(The 102 chars is without line breaks and leading spaces).

To use it, do something like:

main() {
  print(f(123456789*123456790));
}

Answer 18

Brachylog, 8 bytes

⟦b₂s.×?∧

Try it online!

How it works

 ⟦b₂s.×?∧   
 ⟦b₂        in the range from 2 to input
    s       any consecutive sublist
            (with longer list tried out first,
             so [input] will be tried last)
     .      is the output, if …
      ×     the product of the list
       ?    is the input.
        ∧   return the output

Answer 19

Japt, 9 bytes

o ã æÈ׶U

Try it

o ã æÈ׶U     :Implicit input of integer U
o             :Range [0,U)
  ã           :Sub-arrays (in order of length)
    æ         :Get the first that returns true
     È        :When passed through the following function
      ×       :Reduce by multiplication
       ¶U     :Test for equality with U

Answer 20

05AB1E, 7 bytes

L¦¨ŒʒPQ

Outputs a list of all possible results.

Try it online or verify all test cases.

Explanation:

L        # Push a list in the range [1, (implicit) input-integer]
 ¦¨      # Remove the first and last values to make the range [2, input)
   Π    # Get all sublists of this list
    ʒ    # Filter this list of lists by:
     P   #  Where the product of the sublist
      Q  #  Is equal to the (implicit) input
         # (after which the filtered list of lists is output implicitly as result)

Answer 21

Javascript, 88

Golfed code:

function f(a){for(i=2;i<a;i++){b=[1];for(j=i;j>1;j--)if((b[0]*=b[i-j+1]=j)==a)alert(b)}}

Easier to read (nicely spaced) code:

function f(a){
    for(i=2;i<a;i++){
        b=[1];
        for(j=i;j>1;j--)
            if((b[0]*=b[i-j+1]=j)==a)
                alert(b);
    }
}

For each number from 2 to the input number, it finds the product of consecutive integers from the current number back down to 2. If this product equals the input number, then the series of consecutive numbers, along with the original input number, is output.

It outputs the input number followed by the consecutive integers whose product is the input number.

For example f(120) produces an alert with the text "120,5,4,3,2" and then a second alert with the text "120,6,5,4".

Answer 22

APL (Dyalog Unicode), 18 bytes

{⍵∊∊{⍵×/x}¨x←1↓⍳⍵}

Try it online!

Explanation

{⍵∊∊{⍵×/x}¨x←1↓⍳⍵} 
           x←1↓⍳⍵  assign range from 2 to n to x
          ¨        map over range using function
    {⍵×/x}         get products of subsets of size ⍵ in x
                   (this gets all reuquired products of consecutive numbers > 1)
   ∊               enlist/flatten the vector of vectors
 ⍵∊                is n present in the products?