Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
1  
This puzzle, as stated, is not a good fit for this site's format. This site is for contests where there's a good way to decide a winner (e.g., shortest code, fastest code, most upvotes, etc.). You haven't provided any such way. –  Chris Jester-Young Aug 8 at 14:25
2  
I recommend you make this a code-golf (shortest code.) you need to put some limits on it though. For example numbers 0 to 1000000, max execution time 10 sec, etc. –  steveverrill Aug 8 at 14:40
    
Tried to edit it to salvage this question. But I haven't made any questions before, so if you see anything, please do edit. –  bitpwner Aug 8 at 15:53
    
@bitpwner Aside of few typos, seems fine to me. Voted to reopen. –  Sieg Aug 8 at 16:08
5  
I think you mean 30=5*6. –  Kyle Kanos Aug 8 at 18:30

14 Answers 14

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;
}
share|improve this answer

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]
share|improve this answer
    
Sorry, I forgot to define some input. –  Falko Aug 9 at 0:16
1  
replace c=c+1, i=i+1 with c+=1, i+=1 –  Gerrat Aug 9 at 0:54
1  
Oh yeah, didn't think about +=. But I miss ++ in Python... –  Falko Aug 9 at 0:59
1  
if s>=n and if s/n are equivalent, so you can provide all solutions in the same number of characters. –  isaacg Aug 9 at 3:54
1  
You can save three characters by changing s=s*(i+c) to s*=i+c. –  El'endia Starman Aug 9 at 11:43

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)) () () () ())
share|improve this answer

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 226 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.                                             ";
share|improve this answer

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;
}
share|improve this answer

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);}}
share|improve this answer
    
Nice, very simple and elegant! Definitely worked for some of the smaller numbers I threw at it. Then I gave it 50815512 (7128 x 7129) and it went into an infinite loop. Is it overflowing when it tries to compute 7128 x 7129 x 7130 = 362314600560? –  Todd Lehman Aug 8 at 22:54
    
thanks! apparently the condition k < n goes too high because of k *= l++. i could append unsigned long long to the beginning but... that would ruin lives –  bebe Aug 8 at 23:05

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!

share|improve this answer
    
this idea came to my mind too and it looks very efficitent but i doubt it can be shortened enough "to be qualified". –  bebe Aug 9 at 0:10
1  
@bebe it's 258 chars, not too bad for PHP. If I weren't so lazy and obstinate I'd do it in a real language. :P –  Sammitch Aug 9 at 0:25
    
X!/Y! is the product of integers N such that Y<N<=X. Does that help at all? –  githubphagocyte Aug 11 at 2:31

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]
share|improve this answer

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);
}
share|improve this answer
    
Eh, you created a function and print the return value. Haven't seen that done here before. –  Sieg Aug 8 at 20:11
    
I can't get it to print anything...But if it would give me some output, you can golf System.out.println down to System.out.print and the semicolon at the end of for(int k=1,x=j;(x*=j+k)<i;k++) is not only unnecessary but also causes errors. –  Qwix Aug 8 at 20:16
    
This doesn't work for me. x, j, k are out of scope in the last if/for blocks because of a ;. If I remove the ;, it doesn't print anything. –  Geobits Aug 8 at 20:17
1  
@Qwix Changing to print would mean he needs to add a whitespace character to avoid numbers running together. –  Geobits Aug 8 at 20:18
1  
@Geobits Good point! I probably would have seen that if it had given me some output. –  Qwix Aug 8 at 20:22

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.

share|improve this answer

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
}
share|improve this answer

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" "*
share|improve this answer
    
I think your answer is too slow to be valid. Remember, it must complete in no more than 5 minutes on any valid 32 bit integer. How long does it take on 3600060000 == 60000*60001? –  isaacg Aug 12 at 17:28
    
fair point, I'll rework it and post if it is short –  kaine Aug 12 at 17:29
    
If you're going to rework it, please delete this answer until then, or else somehow indicate that is not currently valid. –  isaacg Aug 12 at 22:10

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));
}
share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.