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.

$\endgroup$
  • $\begingroup$ Do you need an exact answer or a good approximation? $\endgroup$ – El'endia Starman Apr 9 '12 at 1:39
  • $\begingroup$ Exact. It'll need to work with other power combinations. It doesn't necessarily have to be able to go up to 10^{15}, but the higher I can get an exact answer the better. $\endgroup$ – Dan Apr 9 '12 at 4:26
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Apr 12 '12 at 5:45
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.