# Collatz Conjecture

Discussion in 'C Programming' started by Dexter, Apr 26, 2008.

1. ### DexterGuest

In a programming book, I found this recursive algorithm which always
returns 1 regardless of the value of the input parameter

==================

int collatz (int n) {
if (n == 1)
return 1;
else{
if ( n%2 == 1)
return collatz(3*n+1);
else
return collatz(n/2);
}
}

==================

The author of the book asserts its unproven that it will indeed always
return 1

Dexter, Apr 26, 2008

2. ### Antoninus TwinkGuest

On 26 Apr 2008 at 18:16, Dexter wrote:
> In a programming book, I found this recursive algorithm which always
> returns 1 regardless of the value of the input parameter

Here's a *non*-recursive algorithm which always returns 1 regardless of
the value of the input parameter:

int f(int n)
{
return 1;
}

Antoninus Twink, Apr 26, 2008

3. ### Lew PitcherGuest

In comp.lang.c, Dexter wrote:

> In a programming book, I found this recursive algorithm which always
> returns 1 regardless of the value of the input parameter
>
> ==================
>
> int collatz (int n) {
> if (n == 1)
> return 1;
> else{
> if ( n%2 == 1)
> return collatz(3*n+1);
> else
> return collatz(n/2);
> }
> }
>
> ==================
>
> The author of the book asserts its unproven that it will indeed always
> return 1

In at least one case, it will not return 1

If n == 0 then it will never return at all.

--
Lew Pitcher

Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------

Lew Pitcher, Apr 26, 2008
4. ### santoshGuest

Dexter wrote:

> In a programming book, I found this recursive algorithm which always
> returns 1 regardless of the value of the input parameter
>
> ==================
>
> int collatz (int n) {
> if (n == 1)
> return 1;
> else{
> if ( n%2 == 1)
> return collatz(3*n+1);
> else
> return collatz(n/2);
> }
> }
>
> ==================
>
> The author of the book asserts its unproven that it will indeed always
> return 1

See:

<http://mathworld.wolfram.com/CollatzProblem.html>
<http://en.wikipedia.org/wiki/Collatz_conjecture>
<http://www.numbertheory.org/php/collatz.html>

There is an ongoing thread over in comp.programming on this problem.

santosh, Apr 26, 2008
5. ### christian.bauGuest

On Apr 26, 7:16 pm, Dexter <> wrote:
> In a programming book, I found this recursive algorithm which always
> returns 1 regardless of the value of the input parameter
>
> ==================
>
> int collatz (int n) {
>   if (n == 1)
>     return 1;
>   else{
>     if ( n%2 == 1)
>        return collatz(3*n+1);
>     else
>        return collatz(n/2);
>   }
>
> }
>
> ==================
>
> The author of the book asserts its unproven that it will indeed always
> return 1

If he or she makes that claim, then the author is completely wrong.

On many implementations, calling this function will result in a stack
overflow whenever the function argument is a negative number. It will
also result in stack overflow on many implementations if the argument
is an odd integer between INT_MAX / 3 and INT_MAX / 3 * 2.

christian.bau, Apr 27, 2008