# Why do the odd numbers in a Collatz trajectory hit so many Primes?

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';
}
$$$$
`
• 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...
– Sil
Commented Nov 25, 2022 at 10:36
• 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. Commented Nov 25, 2022 at 10:38
• 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. Commented Nov 25, 2022 at 10:43
• 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 ? Commented Nov 25, 2022 at 10:46
• 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.
– Finn
Commented Nov 25, 2022 at 16:36