IntStream.range(0, 1_000_000) stops at 113383 (Project Euler: Longest Collatz Sequence)

Question

I have a strange problem in my code to answer this:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

public class Problem14 extends Problem<Integer> {
    private final int maximum;

    public Problem14(final int maximum) {
        this.maximum = maximum;
    }

    @Override
    public void run() {
        result = IntStream.range(1, maximum).boxed()
                .peek(System.out::println)
                .collect(Collectors.toMap(i -> i, i -> (int)Iterators.intStream(new CollatzGenerator(i)).count()))
                .entrySet().stream()
                .peek(System.out::println)
                .max(Comparator.comparingInt(Map.Entry::getValue))
                .get().getKey();
    }

    @Override
    public String getName() {
        return "Problem 14";
    }
}

---

public abstract class Problem<T> implements Runnable {
    protected T result;

    public String getResult() {
        return String.valueOf(result);
    }

    abstract public String getName();
}

---

public class CollatzGenerator implements PrimitiveIterator.OfInt {
    private int current;

    public CollatzGenerator(final int start) {
        if (start < 1) {
            throw new IllegalArgumentException("generators.CollatzGenerator: start < 1: start = " + start);
        }
        this.current = start;
    }

    @Override
    public boolean hasNext() {
        return (current != 1);
    }

    @Override
    public int nextInt() {
        int returnInt = current;
        if (current % 2 == 0) {
            current /= 2;
        }
        else {
            current = 3 * current + 1;
        }
        return returnInt;
    }
}

---

public abstract class Iterators {
    //...

    public static IntStream intStream(final PrimitiveIterator.OfInt iterator) {
        return StreamSupport.intStream(
                Spliterators.spliteratorUnknownSize(iterator, 0), false
        );
    }

    //...
}

Calling code is along the lines of:

new Problem14(1_000_000).run();

So to rephrase, the problem is that the program never terminates, what I do see is that it prints all integers from 1 to 113383, presumably from the first .peek(System.out::println) call.

Also an extra question is that, currently I box my IntStream to a Stream<Integer> to be able to do .collect(Collectors.toMap(i -> i, i -> (int)Iterators.intStream(new CollatzGenerator(i)).count()))...
I'd like to get rid of the boxing and use the IntStream::collect method, however I do not understand how to do it.

Answer 1

So to rephrase, the problem is that the program never terminates, what I do see is that it prints all integers from 1 to 113383, presumably from the first .peek(System.out::println) call.

This is happening because you are assuming all the numbers that will be generated in the collatz will be in range of a int type. But it's not. That is why it is failing. Try making everything to long - PrimitiveIterator.OfLong, StreamSupport.longStream, etc., and it will work.

I'd like to get rid of the boxing and use the IntStream::collect method, however I do not understand how to do it.

I don't understand why you would like to do that. Boxing will still be done somewhere, as you can't create a Map of primitive int. Still, if you want, you would in fact need to do some more work. Here's how you do it:

@Override
public void run() {

    ObjIntConsumer<Map<Integer, Long>> objIntConsumer = 
            (map, value) -> map.put(value, Iterators.longStream(new CollatzGenerator(value)).count());

    BiConsumer<Map<Integer, Long>, Map<Integer, Long>> biConsumer = 
            (targetMap, accumulatorMap) -> targetMap.putAll(accumulatorMap);

    result = IntStream.range(1, maximum)
            .collect(LinkedHashMap::new, objIntConsumer, biConsumer)
            .entrySet().stream()
            .peek(System.out::println)
            .max(Comparator.<Entry<Integer, Long>>comparingLong(entry -> entry.getValue()))
            .get().getKey();
}

Answer 2

I have made short code in C that works to "infinite" using big numbers (I have ended at 104282959 where I killed it).. It checks that numbers converges to one (when proved, continue with next unchecked)..

There are few optimizations, it can be littlebit confusing. But I have not read any paper about that, so there can be more optimizations..

There is no waranty that it works well..

//gcc main.c -lgmp

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

void collatz_conjucture(mpz_t *res, mpz_t n)
{
  mpz_mod_ui(*res, n, 1UL);
  if(mpz_cmp_ui(*res, 1UL) == 0) {
    mpz_mul_ui(*res, n, 3UL);
    mpz_add_ui(*res, *res, 1UL);
    //mpz_fdiv_q_ui(*res, *res, 2UL); //Posible to uncomment, skip one step of computation (always odd after even), but it will slow down increment of next
  } else {
    mpz_fdiv_q_ui(*res, n, 2UL);
  }
}

int main(int argc, char **argv)
{
  // Init
  mpz_t current_b, next_b;
  mpz_init_set_str(current_b, "1", 10);
  mpz_init_set(next_b, current_b);
  //Starts computation - i means step
  for (unsigned long i = 0; i < 0xFFFFF; ++i) {
  //for (;;) { // replace above for infinite
    mpz_set(current_b, next_b);
    do {
      if(mpz_cmp(current_b, next_b) == 0) {
        mpz_add_ui(next_b, next_b, 1UL);
      }
      collatz_conjucture(&current_b, current_b);
    } while (mpz_cmp(current_b, next_b) > 0);
    char *result = mpz_get_str(NULL, 10, next_b);
    printf("%s\n", result);
    free(result);
    result = NULL;
  }
  mpz_clear(current_b);
  mpz_clear(next_b);
  return 0;
}