Collatz Conjecture

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

  1. Dexter

    Dexter Guest

    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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Dexter

    Lew Pitcher Guest

    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
    #3
  4. Dexter

    santosh Guest

    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
    #4
  5. 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
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kent Paul Dolan

    hailstone conjecture, addendum

    Kent Paul Dolan, Jul 25, 2003, in forum: Java
    Replies:
    0
    Views:
    474
    Kent Paul Dolan
    Jul 25, 2003
Loading...

Share This Page