Collatz

import java.util.PriorityQueue;
import java.util.Random;

public class Main3 {
    public class Tuple implements Comparable<Tuple> {
        final int hash;
        final long value;

        public Tuple(long value, int hash) {
            this.value = value;
            this.hash = hash;
        }

        @Override
        public boolean equals(Object tuple) {
            if (tuple instanceof Tuple) {
                Tuple tupleCasted = (Tuple) tuple;
                return tupleCasted.hash == this.hash && tupleCasted.value == this.value;
            } else {
                return false;
            }
        }

        @Override
        public int compareTo(Tuple tuple) {
            return tuple.hash - this.hash;
        }
    }

    PriorityQueue<Tuple> queue = new PriorityQueue<Tuple>();
    Random random = new Random();
    int R = Integer.MAX_VALUE - 1;
    int a = 1 + random.nextInt(R - 1);
    int b = random.nextInt(R);
    int maxMapSize;
    Tuple newTuple;

    public int hash(long number) {
        return 1 + (int) (((long) a * number + b) % R);
    }

    public void  maybeAdd(long number) {
        newTuple = new Tuple(number, hash(number));

            if (queue.size() < maxMapSize) {
                if (!queue.contains(newTuple)) {
                    queue.add(newTuple);
                }
            } else if (queue.peek().hash > newTuple.hash && !queue.contains(newTuple)) {
                queue.poll();
                queue.add(newTuple);
            }
    }

    public long algorithmD(int maxValue) {
        queue.clear();
        a = 1 + random.nextInt(R - 1);
        b = random.nextInt(R);

        for (int i = 1; i <= maxValue; i++) {
            long currentNumber = i;

            maybeAdd(currentNumber);

            while (currentNumber != 1) {
                if ((currentNumber % 2) == 0) {
                    currentNumber = currentNumber / 2;
                } else {
                    currentNumber = currentNumber * 3 + 1;
                }

                maybeAdd(currentNumber);
            }
        }

        return ((long) queue.size() * R / queue.peek().hash);
    }

    public Main3(int maxValue, int maxMapSize) {
        this.maxMapSize = maxMapSize;
        int rounds = 100;
        long[] correctReults = new long[]{
            22, 251, 2228, 21664, 217212, 2168611
        };
        long[] results = new long[rounds];
        long totalSum = 0;

        for (int i = 0; i < rounds; i++) {
            results[i] = algorithmD(maxValue);
            totalSum += results[i];
        }

        totalSum /= rounds;
        double percentile = Math.abs((double) totalSum / correctReults[(int) Math.log10(maxValue) - 1]);
        System.out.println(maxValue + " |C_N|: " + totalSum + " (" + String.format("%.2f", Math.abs(1 - percentile) * 100) + "%)");
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 6; i++) {
            new Main3((int) Math.pow(10, i), 1000);
        }
    }
}