Collatz conjecture

collatz.c

/* 
 * Verifies the Collatz conjecture up to N positive integers.
 * The program searches backwards starting from 1 to form a tree, where each integer n has children 2n and (n-1)/3 if odd,
 * and then searching this tree breadth-first without forming it.
 */

#include <stdio.h>
#include <stdlib.h>

#define N 1000
#define SIZE N
#define QTYPE unsigned int

struct queue {
    size_t size, start, end; /* always start <= end <= size */
    QTYPE *arr;
};

/* don't take NULL arguments */
void make_queue(struct queue *);
void enqueue(struct queue *, QTYPE); 
void free_queue(struct queue *);
QTYPE dequeue(struct queue *); /* undefined output if queue is empty */
int empty(struct queue *);

int main()
{
    size_t count = 0, t = 0;
    QTYPE n;
    struct queue q;
    make_queue(&q);
    if (q.arr == NULL)
        return 1;
    
    /* push 1 into the queue */
    enqueue(&q, 1);
    
    while (!empty(&q) && count < N) {
        n = dequeue(&q);
        
        if (n < N)
            ++count;
        
        enqueue(&q, 2 * n);
        if (!((n - 1) % 3) && ((n - 1) / 3 & 1)) /* (n-1)/3 is an odd integer, so that 3n+1 applied to it is n */
            enqueue(&q, (n - 1) / 3);
    }
    
    printf("Took %zu searches to verify the conjecture for the first %d positive integers.\n", q.end, N);
    free_queue(&q);
    return 0;
}

void make_queue(struct queue *q)
{
    q->size = SIZE;
    q->start = q->end = 0;
    q->arr = calloc(q->size, sizeof(QTYPE));
}

void enqueue(struct queue *q, QTYPE n)
{
    if (q->end == q->size) {
        q->size *= 2;
        q->arr = realloc(q->arr, q->size);
    }
    if (q->arr != NULL)
        q->arr[q->end++] = n;
}

void free_queue(struct queue *q)
{
    free(q->arr);
}

QTYPE dequeue(struct queue *q)
{
    return q->arr[q->start++];
}

int empty(struct queue *q)
{
    return q->arr == NULL || !(q->end - q->start);
}