0
$\begingroup$

I implemented the Collatz procedure in C++ and simulated all numbers up to n (I did it up to 100000). The program counted the total number of primes and the total number of composites hit (only out of the odd numbers). Additionally, it calculates the average ratio of primes hit during the procedure for every number up to n. It seemed strange to me, that even at the scale of 100000, nearly half of all odd numbers hit were primes. Is there any reason for this? Here is my code.

#include <bits/stdc++.h>
using namespace std;

vector<bool> is_prime;

void prime_sieve(uint64_t n)
{
    is_prime = vector<bool>(n + 1, 1);

    for (size_t i = 2; i <= n; i++)
    {
        if (is_prime[i])
        {
            for (size_t j = 2 * i; j <= n; j += i)
                is_prime[j] = 0;
        }
    }
}

int main()
{
    prime_sieve(1000000000);
    uint64_t n;
    cin >> n;

    uint64_t primes = 0, composites = 0;
    double prime_ratio = 0.0;

    for (uint64_t i = 1; i <= n; i++)
    {
        uint64_t x = i, curr_primes = 0, curr_composites = 0;

        while (x != 1)
        {
            if (x & 1)
            {
                if (is_prime[x])
                    curr_primes++;
                else
                    curr_composites++;
                x = 3 * x + 1;
            }
            else
            {
                x /= 2;
            }
        }

        if (curr_primes || curr_composites)
            prime_ratio +=
                (double)curr_primes / (double)(curr_primes + curr_composites);

        primes += curr_primes;
        composites += curr_composites;
    }

    cout << primes << ' ' << composites << '\n'
         << prime_ratio / (double)n << '\n';
}
```
$\endgroup$
6
  • 3
    $\begingroup$ Your question asks about numbers of form $3x+1$ (nowhere except in tag it mentions Collatz), but your code checks odd numbers in the Collatz sequence before applying $3x+1$, those are two different things... $\endgroup$
    – Sil
    Commented Nov 25, 2022 at 10:36
  • 1
    $\begingroup$ Note that you don't count the even numbers in the sequence, which are all composite. Note also that the only obvious thing you can say about $3x+1$ is that it's definitely not divisible by $3$ or $x$ - if $x$ is small then this will significantly affect the probability of $3x+1$ being prime. $\endgroup$ Commented Nov 25, 2022 at 10:38
  • $\begingroup$ You should compare the number of $3n+1$ primes in an interval, to the number of $3n+2$ primes in the same interval, to see if there is any statistically significative difference. $\endgroup$ Commented Nov 25, 2022 at 10:43
  • 1
    $\begingroup$ Do you count the hit prime numbers in a single trajectory or in all trajectories upto $10^5$ ? Do you count duplicates as another hit prime ? $\endgroup$
    – Peter
    Commented Nov 25, 2022 at 10:46
  • $\begingroup$ I meant the numbers in a Collatz trajectory, not ones of the form 3x + 1, sorry for the confusion. The number of primes hit in all trajectories up to 10^5 is counted, multiple hits are counted multiple times. $\endgroup$
    – Finn
    Commented Nov 25, 2022 at 16:36

1 Answer 1

0
$\begingroup$

There is a small mistake in the calculation of primes_ratio / n: you ignore n = power of two. But that error is only 20 in the numbers up to a million. Another small problem is that you are limited to 64 bits, so you will have no numbers above 2^64, which would be least likely to be prime (and when you ignore overflow some multiples of 3 sneak in).

The numbers that you check are never divisible by 2 or 3, so they are 3 times more likely to be primes. But if you start with a number of 1,000,000, each step multiplies it by 3/4 on average, so ln x has a linear distribution among the numbers you check. A random number around 10^6 is prime with probability 1 / ln x ≈ 1/13.8. Your numbers are odd and not divisible by 3, therefore prime with probability about 1/4.6. For your numbers, on an exponential scale, they are prime with probability 1/2.3.

The first number you examine is less likely to be prime, and the last numbers on the trajectory are the same for many numbers so “probabilities” don’t really work, so the actual results may be off a little bit.

$\endgroup$
1
  • $\begingroup$ Thanks for this answer. But why are the numbers I check never divisible by 3? The counter for prime / not prime is incremented before doing 3x + 1. So the only thing we can say is, that the number is odd. $\endgroup$
    – Finn
    Commented Nov 27, 2022 at 19:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .