0

Hi I am new to C and I chose a project to get better
I wanted to make a program that would brute force every number if it is according to Collatz conjecture.

Collatz conjecture:

For those who do not know what Collatz conjecture is click here
Summary:
If a number is odd it is multiplied by 3 and increased by 1
If even it is divided by 2
This is repeated until it reaches 1

My code:

#include <stdio.h>
int main(){
    int n, x, a, b;
    n = 5; //number we check first (has to be bigger than 4 because 4,3,2,1 is a loop)
    //n is later on a number that is currently being tested
    //all numbers smaller than 2 ** 64 were brute force tested and are according to Collatz's conjecture
    x = n; //x begins as n and then changes according to rules of cenjecture until it reaches 1
    a = 1; //a is set to 1 until x = 1 which means that number n is according to conjecture
    b = 1; //creates an infinite loop

    while(b == 1){ //runs forever
        if(a == 1){
            if(x == 1){
                a = 0;              //if x reaches 1 (number n is according to conjecture) a is set to 0 and n is increased by 1 ===
            }                       //                                                                                            ||
            else{                   //                                                                                            ||
                if(x % 2 == 0){     //                                                                                            ||
                    x = x / 2;      //                                                                                            ||
                }                   //                                                                                            ||
                else{               //                                                                                            ||
                    x = x * 3 + 1;  //                                                                                            ||
                }                   //                                                                                            ||                  
            }                       //                                                                                            ||
        }                           //                                                                                            ||
        else{                       //                                                                                            ||
            printf("%d \n", n);     //                                                                                            ||
            n = n + 1;              //             <<<<<============================================================================
            x = n;                  //
            a = 1;                  //
        }
    }
}

Problem:

The problem is that when I run it it stops on number 113383 and has problems with it. I even let it run for more than 5 minutes but it did not do anything. I even tried to run the same number in my python program which test input number and it had it in no time. I tried to start with n = 113384 and it worked and stopped again on 134378.

Is number 113383 anyhow different in C or is there a flaw in my code.

Please help if you can.
Thank you very much

Barmar
  • 741,623
  • 53
  • 500
  • 612
Oliver Kurnava
  • 71
  • 9
  • 1
    If you want an infinite loop you can just write `while (1)`, you don't need an extra variable `b`. – Barmar Sep 09 '21 at 14:27

1 Answers1

3

Try declaring the variable as a "long int" this could be due to the maximum size of an int witch is –32,767 to 32,767

Zachary Gagnou
  • 31
  • 2
  • 2
    `int` is usually 32 bits. Your range is for `short`. – Barmar Sep 09 '21 at 14:31
  • In fact the number sequence starting from 113383 reaches a maximum value of 2482111348, which is too large for a signed 32-bit int – r3mainer Sep 09 '21 at 14:32
  • The upper limit of `int` is `2,147,483,647` – Barmar Sep 09 '21 at 14:32
  • 1
    The *minimum* range of an `int` specified by the standard is –32,767 to 32,767, however most modern implementations have a range of -2147483648 to 2147483647. – dbush Sep 09 '21 at 14:36
  • This is indeed the correct assumption: the number in `collatz(113382)` not representable anymore with 31 bits is teh one after `827370449` because `(827370449 * 3 + 1) - 2^31 = 334627700`. This will cause a negative number in most cases (but it is still UB!) which would be `-1812855948` here. You might use a larger integer type but at least check for overflow. – deamentiaemundi Sep 09 '21 at 14:43
  • @Barmar That is just false. For a 32 bit variable use `int32_t` – 12431234123412341234123 Sep 09 '21 at 14:53
  • @12431234123412341234123 In most implementations, `int32_t == int`. – Barmar Sep 09 '21 at 14:55
  • @deamentiaemundi Unfortunately, C doesn't provide a way to check for overflow, you have to avoid it in the first place. You could use a variable for the maximum `n` where `n*3+1` fits, and check before doing the multiplication. – Barmar Sep 09 '21 at 14:57
  • @Barmar Out of 6.5 ISAs (The .5 is for AMD64 + x86_32) i wrote code, only 2.5 of this have `INT_MAX == INT32_MAX`. I don't think `INT_MAX == INT32_MAX` is true for most ISAs. Compilers of neither AVR, X86_16, PIC12, PIC16, PIC18, MSP430 nor 8051 use 32 bit for an `int`. The C standard says a `int` has at least 15 value bits, not 32 nor 31. – 12431234123412341234123 Sep 09 '21 at 14:59
  • @12431234123412341234123 Microcontrollers are a special case. – Barmar Sep 09 '21 at 15:02
  • @Barmar yes, but you can only put so much into a comment. I would have uses an unsigned type and a helper variable to keep it simple and do something like: `tmp = x * 3 + 1; if(tmp < x){ printf("Overflow at x = %u \n", x); break; }x = tmp;` Not the most elegant solution, admitted, just an example. – deamentiaemundi Sep 09 '21 at 15:03
  • @Barmar No. They provide a freestanding environment like specified in the C standard. The C standard is pretty clear: A `int` has at least 16 usable bit. Don't use C code and assume a `int` is more than 16 bit without checking `INT_MAX` or something like that. – 12431234123412341234123 Sep 09 '21 at 15:06
  • The basic issue is that whatever type you use, you'll eventually run into a limit. The limit the OP ran into is clearly for 32-bit signed integers. – Barmar Sep 09 '21 at 15:07