9
$\begingroup$

Is there an easy way to compute the following question:

How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?

The only thing that strikes me as a possibility is iterating through the various primes and finding the number of primes such that $2^2 3 p_3<10^{15}$, etc, which would give me

$\operatorname{primepi}[10^{15}/(2^23)]+\operatorname{primepi}[10^{15}/(2^25)]+\operatorname{primepi}[10^{15}/(2^27)]+\cdots$

But that gets me no where fast. I'm mostly looking for "Is there an easy way to do this?" and hints at what it might be, I'm not actually looking for it to be solved for me, just a push in the right direction.

My other issue is that my primepi function I have written in python doesn't really support going up this high... I end up having to turn to wolfram alpha to get many of the values and that is no way to make an automated computation.

  • 2
    Getting an exact count can't be any easier than getting an exact count of the number of primes up to $10^{15}/12$, so you may be asking for too much.2012-04-12

1 Answers 1

0

This Wolfram's Mathematica code gives the answer, but it will take ages for calculating up to $10^{15}$. The variable MAX is the upper limit.

MAX = 10^3; count = 0; For[n = 1, n < MAX, n++,     array = FactorInteger[n];    (* factorizes N in a product of prime powers *)     If[Length[array] == 3,       (* if N is composed by exactly 3 primes *)         If[Or[                   (* then it will check their exponents *)             And[array[[1]][[2]] == 2, array[[2]][[2]] == 1, array[[3]][[2]] == 1],             And[array[[1]][[2]] == 1, array[[2]][[2]] == 2, array[[3]][[2]] == 1],             And[array[[1]][[2]] == 1, array[[2]][[2]] == 1, array[[3]][[2]] == 2]              ], (* if the exponents are (2,1,1) or (1,2,1) or (1,1,2) *)             count++   (* then it increases the count variable *)         ]     ] ] Print[count]; 

I've tested it up to $10^{9}$ and got exactly $68391432$ numbers.