"Weird Algorithm" (Collatz) from CSES Problem Set

Question

I had to solve the following problem:

Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one.
For example, the sequence for n=3 is as follows:

3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Your task is to simulate the execution of the algorithm for a given value of n.

Input

The only input line contains an integer n.

Output

Print a line that contains all values of n during the algorithm.

Constraints

1 ≤ n ≤ 10⁶

And this is my code. Let me know what you think:

#include <stdio.h>
#include <inttypes.h>
 
#define MAX_NUMBER 1000000 /* max number to evaluate  */
 
int main( void ) {
    
    /* an unsigned int 64 bytes, portable!  */
    uint64_t n = 0;
 
    /* input */
    do { 
        
        /* scanf() verification; if scanf() doesn't return 1, 
        there's an input problem: the input isn't a number*/
        if ( scanf("%" PRIu64, &n) != 1 ) {
 
            printf("INVALID INPUT, NOT NUMBER\n"); /* say to the user that the input isn't valid  */
            
            while ( getchar() != '\n' ) {} /* "clear" stdin */
 
            /*******************************************************
 
            NOTE: if you're not interesed in why I wrote this statement, 
            don't read this.
            i.e.: if my input is "3dg", the final input is 3dg\n
            but this scanf() uses %d, so it only reads until 3, 
            and "dg\n" are in stdin, so this is basically trash.
            getchar() uses stdin, so basically "clean" stdin. 
            Once time this while is 0, stdin is empty
 
            *******************************************************/
 
            n = -1; /* set n as a invalid input  */
        }
 
    } while( n < 1 || n > MAX_NUMBER );
 
    /* algorithm */
    while ( n != 1 ) {
 
        printf("%" PRIu64 " ", n); /* print the value for create a line of all values */
 
        if ( n & 1 ){ /* odd number */
            n *= 3;
            ++n;
        }else{        /* even number */
            n = n >> 1; /* divides by 2 */
        }
 
    }
 
    printf("%" PRIu64 "\n", n); /* final value: 1 */
 
    return 0;
}

Answer 1

In programming I think commendable practices should be internalised, to be followed out of habit, avoiding needless trouble.

I hold that program source code and parts from it have a way to turn up without "external documentation" that may have accompanied it.

Without a specification in the code, it may be impossible

• to argue about correctness
• to modify/substitute an implementation without breaking existing applications (that relied on documented interface …)

TorbenPutkonen put advice on how to comment well enough .

One good practice is to separate user interface (getting start values) from business logic/code/processing(tripling&incrementing/halving):

This helps to keep procedures short so they can be viewed "at a glance".

(There is a slight problem with this practice and the task at hand: is outputting each number business or interaction? And a slightly non-beginner technique: pass a procedure to process the numbers to a client's (call site's) liking.)

Complementary to processing start values read from standard input is processing command line/program arguments (int main(int argc, char* argv[]).

Using PRIu64 looks a solid practice.

The use of whitespace is slightly inconsistent (e.g. before opening braces) - one more thing a contemporary IDE can take care of.

Two ways to detect overflow short of processing an "unlimited" integer representation like digit strings:

• compare to (UINT64_MAX-1)/3 before multiplication
• handle tripling by two additions, checking sum to be larger than addend

(For an idea whether this is needed I turned to oeis.org.)

Answer 2

How subtle is that? (* NEW *)

People reading this Q&A represent the full spectrum of experience, from novices to battle-hardened professionals. Perhaps not-unnoticed, but, oddly, so far unreported is:

//      if ( scanf("%" PRIu64, &n) != 1 ) {
        if ( scanf("%" SCNu64, &n) != 1 ) {

The almost invisible, likely inconsequential this time, use of the wrong macro is typical of one class of coding bugs: How can something that looks so right be so wrong?

Guidelines and support tools (like the descendants of lint) do their best to help. Heed them, but always recognised C will allow you to write foolish code.
"With great power comes great responsibility"

---

Review

OP is off to a pretty good start on their C adventure.
Very minor layout (whitespace) inconsistencies, not worthy of mention.

As noted in comments below the question, n = -1; is ill-advised.
The negative constant with the unsigned variable creates unnecessary tension.

My first response (in a comment) suggests omitting this statement completely. The considered, expert response regarding this, from @Chux, shows that using n = 0; would ensure that execution would always be predictable.

---

Incantations

A while() loop and a large (peevish) comment have been used to read and discard 'rubbish' characters that a user may have typed on the same line.

Suggested:

if( scanf( "%" PRIu64 "%*[^\n]", &n ) != 1 ) {

would similarly dispose of possible trailing rubbish, LEAVING only the 'whitespace' character LF (linefeed) in the input buffer. In MANY (but not ALL) cases, this residual whitespace will not cause problems for subsequent scanf() invocations. As the OP's experiences with scanf() broaden and diversify, they are advised to return to the documentation often in order to solidify and consolidate their concepts of its behaviour.

Consider using this format specification (incantation called a "scanset") with scanf() instead of an explicit while() and getchar()...
Mixed use of scanf() with C's other input functions (eg: getchar(), and especially fgets()) can be ill-advised.

One other thing:

while ( getchar() != '\n' ) {} /* "clear" stdin */

takes no account of the possibility that EOF is returned (until forever) by getchar(). There are a number of situations where stdin will not be providing a LF. (Things are never as simple as they first appear!)

Personality: I enjoy discovering uplifting 'Easter Eggs' of authors' personalities in embedded comments (and frequently try my best to be 'unbusinesslike', too.) Consider your reader(s). If straying from 'business', make sure your comment seeks to lighten the reader's day, not darken it...

---

Code to the problem statement

... the algorithm multiplies it by three and adds one.

            n = ( 3 * n ) + 1; // parentheses superfluous

The compiler will likely emit the same machine code for this version.

Seemingly trivial here, 'direct mapping' between a mathematical formula and its expression in a programming language becomes more important when those formula are more complex.

---

// comments

/* This (block) style of commenting works, but is considered 'old-fashioned'. */

//
// You are free to use whichever style you prefer in your own programs.
// When working with code in a group, stick to one style agreed to by the majority.
//

Tip:
A recent project was peppered with several tracing (aka "print debugging") printf() statements similar to:

                ...
/**/            printf( "yadda yadda %d\n", varX );
                ...

The /**/ at the margin marked these lines as distinct from the surrounding code.

While there are various (proper) ways to facilitate dis-/en-abling these helpful statements, it was quick-and-dirty to simply add/remove one '/' from the front of these lines:

//**/            printf( "yadda yadda %d\n", varX );  // entire line now 'disabled'

'Print debugging' (to trace the flow or intermediary results of working code) is another 'tool for the toolbox' that may be useful to you someday.

---

Been there; done that

Coding a tool to play with the Collatz Conjecture is a valid exercise. Its precepts are simple, and its behaviour 'curious' to observe. (It has been empirically tested using 'seeds' up to some very large number of digits without encountering any dragons or unicorns. An amateur is unlikely to have the compute power available to push the proven boundary much higher.)

Noteworthy is the 4 -> 2 -> 1 'loop' at its end. Spot the 2² -> 2¹ -> 2⁰ happening?

Rather than using base-10 (decimal) to report the sequence of calculated values, octal output provides a possibility to recognise patterns, especially in the lower digits of the results.

The OP might allow the user enter the 'seed' as either decimal ("255") or octal ("0377").
Make this a learning experience.

Answer 3

This comment is an exaggeration:

    /* an unsigned int 64 bytes, portable!  */
    uint64_t n = 0;

It's portable only across targets that can provide such a type with no padding bits. Although that includes the vast majority of platforms being manufactured today, truly portable code will use uint_fast64_t (or perhaps uint_least64_t), which the C standard says must be available everywhere.

---

There's no good reason for the input limit (MAX_NUMBER) to be a preprocessor macro. Prefer to use a constant, which makes it strongly typed and controls the scope.

---

We could avoid the need for this comment:

            n = n >> 1; /* divides by 2 */

If we wrote that as n /= 2, it would be self-documenting (any reputable compiler will emit the same object code for both expressions).

Answer 4

There's definitely an opportunity to factor your code out into functions which will make it easier to manage than a single monolithic main.

As an example of what greybeard has suggested, imagine a get_uint64 function. There's nothing particularly special about this function. The logic should be self-explanatory.

uint64_t get_uint64(
    uint64_t lower_bound,
    uint64_t upper_bound,
    char *err_msg
) {
    for (;;) {
        uint64_t n;
        if (scanf("%" PRIu64, &n) == 1 && 
            n >= lower_bound &&
            n <= upper_bound
        ) {
            return n;
        }

        fprintf(stderr, "%s\n", err_msg);
        while (getchar() != '\n') {}            
    }
}

But this cuts a big chunk out of your main function and makes it much easier to read.

It also means that you can address any concerns about the implementation of get_uint64 without worrying about impacting the rest of your program. You may, for instance, wish to replace scanf and getchar with a call to fgets and sscanf.

#include <stdio.h>
#include <inttypes.h>
 
#define MAX_NUMBER 1000000 
 
int main(void) {
    uint64_t n = get_uint64(1, MAX_NUMBER, "INVALID INPUT, NOT NUMBER");
 
    while ( n != 1 ) {
        printf("%" PRIu64 " ", n); 
 
        if (n & 1) { 
            n *= 3;
            ++n;
        } else {        
            n = n >> 1; 
        }
    }
 
    printf("%" PRIu64 "\n", n); 
 
    return 0;
}

You might next create a collatz_next function.

uint64_t collatz_next(uint64_t n) {
    if (n & 1) { return n * 3 + 1; }
    else { return n / 2; }
}

At which point we can write the following, including swapping the while loop for a for loop.

#include <stdio.h>
#include <inttypes.h>
 
#define MAX_NUMBER 1000000 
 
int main(void) {
    uint64_t n = get_uint64(1, MAX_NUMBER, "INVALID INPUT, NOT NUMBER");
 
    for (; n != 1; n = collatz_next(n)) {
        printf("%" PRIu64 " ", n);
    }
 
    printf("%" PRIu64 "\n", n);
 
    return 0;
}