Collatz sequence of a number

Question

I'm trying to find the Collatz sequence of a number. The following code runs into infinite loop for number 113383.

int collatz(long number)    {
int length = 1; //length of the sequence
while (number != 1) {
    printf("%ld-", number);
    if ((number % 2) == 0)
        number /= 2;
    else
        number = (number * 3) + 1;
    length++;
}
return length;
}
int main()  {
printf("%d", collatz(113383));
return 0;
}

EDIT: The Collatz Conjecture Says the next number in sequence is n/2 if number is even 3n+1 if the number is odd terminate if number is 1

@Kamiccolo was crossing INT_MAX at a point. Thanks for the help. — SureshS, Aug 31 '13 at 02:41
Changing `long number` to `unsingned long` might fix that. Because biggest number in chain produced by `collatz(113383)` exceeds 2^31-1 (signed long) limit. And default type (signed, usingned) of long varies between compilers. — Kamiccolo, Aug 31 '13 at 02:47
@Kamiccolo: Not so -- barring a massive bug, `long` is always precisely equivalent to `signed long` on any C or C++ compiler. — Jerry Coffin, Aug 31 '13 at 04:06
@JerryCoffin, ooops, sorry, my mistake. Thinking of int and writing about longs at late night is no good :) — Kamiccolo, Aug 31 '13 at 11:39
@Kamiccolo: `int` is the same as `long` in this respect. The type you're thinking of is `char` (I.e., "plain" `char` may be equivalent to either `unsigned char` or `signed char`). — Jerry Coffin, Aug 31 '13 at 15:16
Just have solved this euler, 64 bit integer arithmetics is enough. you need operations: a+b,a<<1,a>>1. my code output: "[4407.990 ms] Problem014. 837799" non parallel win32 code on AMD A8-5500 3.2GHz, for now is this the (massively) slowest euler problem from 1-14. before optimization it took about 22 seconds — Spektre, Sep 12 '13 at 17:29
get inspired by that duplicate question (added lookup table) so runtime is now acceptable [ 406.955 ms] — Spektre, Sep 12 '13 at 17:48

score 1 · Answer 1 · answered Aug 31 '13 at 02:48

You aren't checking whether the number is overflowing your long. Try adding the following print in your loop:

...
      if (number*3+1 < number) {
        printf("overflow after %d iterations\n", length);
        break;
      }
      number = (number * 3) + 1;
...

Note that whether this overflows a long will depend on the system/target:

/tmp/c $ gcc -o collatz -m32 collatz.c
/tmp/c $ ./collatz 
overflow after 120 iterations
/tmp/c $ gcc -o collatz -m64 collatz.c
/tmp/c $ ./collatz 
<answer redacted>

You might also consider using a unsigned long long which should be large enough for this problem even in 32-bit.

Collatz sequence of a number

1 Answers1