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[3]{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.

  • $\begingroup$ Just to make sure I understand what you are counting, what is f(n) for n = 50, 100, 150 and 200? $\endgroup$ – ErikR Feb 6 '15 at 16:46
  • $\begingroup$ 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. $\endgroup$ – AvatarOfChronos Feb 6 '15 at 22:12
  • $\begingroup$ For $n=10^{13}$ I get $1860310801454$. Figured I'd include this for anybody else that wants to test their functions. $\endgroup$ – AvatarOfChronos Feb 6 '15 at 22:14
  • 1
    $\begingroup$ btw, this is a nice C++ library for computing pi(n): github.com/kimwalisch/primecount $\endgroup$ – ErikR Feb 9 '15 at 21:03
  • $\begingroup$ Thats an interesting library to know about I'll definitely look into it. $\endgroup$ – AvatarOfChronos Feb 9 '15 at 23:51

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

$$f(n) = \sum _{i=1}^{\pi \left(\sqrt[3]{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$.

| cite | improve this answer | |

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.

| cite | improve this answer | |

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.

Some Haskell code:

-- primes is the (infinite) list of primes
-- primeCount n = pi(n)

f n = sum $ do
      (i,q) <- zip [1..] $ takeWhile (\q -> 2*q*q <= n) primes
  let m = min (q-1) (n `div` (q*q))
  p <- takeWhile (<= m) primes
  let c = primeCount (n `div` (p*q)) - i
  return c
| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – AvatarOfChronos Feb 6 '15 at 22:43

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.