# Counting squarefree 3-almost primes. (Solved!)

Right so we're gonna define a 3-almost prime as $n = p_1\cdot p_2\cdot p_3$ and a squarefree 3-almost prime is a 3-almost prime such that $p_1\neq p_2 \neq p_3$.

My question is this; For a given number $N$ how many squarefree 3-almost primes are there less than or equal to $N$? I'm looking for an exact answer like the one found in this answer for squarefree 2-almost primes. I've also found this paper which looks promising but I have yet to wrap my head around it.

Can anybody point me in the right direction?

Edit #1: right so having looked around on the internet I've discovered that: $$\pi_3(n) = \sum _{i=1}^{\pi \left(\sqrt{n}\right)} \sum _{j=i}^{\pi \left(\sqrt{\frac{n}{p_i}}\right)} \left(\pi \left(\frac{n}{p_i p_j}\right)-j+1\right)$$ gives the number of 3-almost primes equal to or less than $n$.

I also know that the only way a 3-almost prime can fail to be square free is if one of its prime factors is repeated. So I would think that $f(n) = \pi_3(n) - \pi(\sqrt{n})$ get me somewhere close to what I want because $\pi(\sqrt{n})$ is the number of squarefull 2-almost primes.

Edit #2: I have a feeling that I'm going to end up with a function $f(n) = \pi_3(n) - \sum q(m)\pi(\sqrt{m})$ can't quite figure out what it should be yet.

Edit #4: I think I've found a working formula. It appears that $$f(n) = \pi_3(n)-\sum _{i=1}^{\frac{n}{6}} \pi \left(\sqrt{\frac{n}{p_i}}\right)$$ works. But I'm a little iffy on the upper bound for the summation. I've checked it against precalculated values of f(n) and it appears to work. But I feel that its way to high. Can anybody see an easy a way to reduce it?

Edit #5: It appears I can use PrimePi[n] as an upper bound for the sum. Still think its kinda big.

• Just to make sure I understand what you are counting, what is f(n) for n = 50, 100, 150 and 200? – ErikR Feb 6 '15 at 16:46
• So what I was trying to count is numbers of the form $p_1p_2p_3$ with distinct $p_i$. For 50,100,150,200 I get 2,5,11,19. Counting numbers with 3 (not necessarily distinct) prime factors is given by the $\pi_3$ function. In my answer I provide a summation that subtracts the count of numbers with three prime factors that are not square free. – AvatarOfChronos Feb 6 '15 at 22:12
• For $n=10^{13}$ I get $1860310801454$. Figured I'd include this for anybody else that wants to test their functions. – AvatarOfChronos Feb 6 '15 at 22:14
• btw, this is a nice C++ library for computing pi(n): github.com/kimwalisch/primecount – ErikR Feb 9 '15 at 21:03
• Thats an interesting library to know about I'll definitely look into it. – AvatarOfChronos Feb 9 '15 at 23:51

What about using this formula for $f(n)$:

$$f(n) = \sum _{i=1}^{\pi \left(\sqrt{n}\right)} \sum _{j=i+1}^{\pi \left(\sqrt{\frac{n}{p_i}}\right)} \left(\pi \left(\frac{n}{p_i p_j}\right)-j\right)$$

Of course, you can stop the inner summation when $p_i p_j p_j >= n$.

It turns out that you can use the answer here to find all of the non-squarefree 3-almost primes and you end up with this as your final solution:

$$f(n) = \pi_3(n) - \sum_{q\le n^{\frac{1}{2}}} \pi\bigg( \frac {n}{q^2} \bigg)$$

The summation in this answer is much faster to perform than in the questions edit #4.

Does this formula count what you are interested in?

$$f(n) = \sum_{i=1}^a \sum_{j=1}^{b(i)} \pi ({n \over {p_i\cdot p_j}}) - i$$ where $a = \pi(\sqrt{n/2})$ and $b(i) = \pi ( \min( p_i-1, \frac{n}{p_i^2}))$

It may look hairy, but the idea is simply this:

1. Choose the middle prime $p_i$.
2. Iterate over possible values for the smallest prime $p_j$
3. The expression $\pi( \frac{n}{p_i\cdot p_j} ) - i$ counts the number of ways to choose the largest prime.

-- primes is the (infinite) list of primes
f n = sum $do (i,q) <- zip [1..]$ takeWhile (\q -> 2*q*q <= n) primes
let m = min (q-1) (n div (q*q))
let c = primeCount (n div (p*q)) - i

• So I've checked your function for a range of values and it does appear to be counting the right things. Interestingly in my mathematica implementations (using a ParallelSum on 8 cores) your function seems to take a lot longer to evaluate for $n = 10^{10}$ and higher which was the range I was working in. – AvatarOfChronos Feb 6 '15 at 22:43