3
$\begingroup$

I am asking myself if instead of working with the primes in the calculation of $\pi(x)$ up to $x$, we instead work with the composite numbers and then using a simple subtraction to get $\pi(x)$. After all it must be much easier to deal with the composite numbers. We only need to look at $x/3$ to get $\pi(x)$ since $2/3$ of the numbers are multiples of $2$ and $3$. So we can write $c(x)+\pi(x) = x/3$ ( and add the $2$ coming from primes $2$ and $3$ ) to get the correct result ( $c(x)$ being of course the number of composite up to $x/3$ not included the multiples of $2$ and $3$ of course).

We know how to produce the composite numbers, but we don't know if a given number is a prime without testing it. What would be wrong with that?

$\endgroup$
4
  • 6
    $\begingroup$ @simplicity Watch your etiquette: math.stackexchange.com/faq#etiquette . If you think the question doesn't merit attention, then downvote it. But don't insult people. $\endgroup$ Nov 13, 2011 at 21:10
  • 6
    $\begingroup$ @simplicity That's just rude. I've seen you throwing around words like "stupid", "dumb" and "silly" in this and other commentary. Do everyone a favor and save that denigrating sort of language for somewhere else. $\endgroup$ Nov 13, 2011 at 21:10
  • $\begingroup$ Generally to see if something is prime or not isn't even that hard. It can be done in polynomial time en.wikipedia.org/wiki/AKS_primality_test $\endgroup$
    – simplicity
    Nov 13, 2011 at 21:18
  • 3
    $\begingroup$ @Mbel, this site does not work well if you use it to suggest new approaches to problems. If you think you have a useful and promising approach to something, then carry it out. «What would be wrong with that?» is not a real question as far as math.stackexchange goes. $\endgroup$ Nov 23, 2011 at 3:07

3 Answers 3

4
$\begingroup$

Legendre's formula counts composites to count primes.

The inclusion-exclusion nested sums are counting how many composites of certain forms there are. Used in a certain way, you can extract the count of primes $< n$ from it. It's basically the sieving process rewritten as a formula.

The fastest published combinatorial method for counting primes is, in fact, based on this identity (with a lot of other development), so it's not a crazy thought. Just not really a new one.

See this paper for a version of that algorithm with a lot of work done to it.

$\endgroup$
1
  • 1
    $\begingroup$ Maybe not a new idea but certainly a simpler one to implement if we limit the counting to only those composite in the two arithmetic progressions 6k+1 and 6k-1. Composite are produced by multiplication so their indices can be produced but not that of a prime. There are really simple formula for producing the indices ( without doing repeated multiplications ). Those indices are then eliminated from the original list of indices and what's left is the primes' indices. The count follow. $\endgroup$
    – Mbel
    Nov 13, 2011 at 21:55
3
$\begingroup$

I must say, even if what you say sounds like an idea, it is definitively not new. The reason why we don't use this much is because it's like one of the oldest ideas in the world, i.e. a sieve, which means we look at the integers up to $x$ and determine which of them are composite by ruling them out. Look at this link to explain how it goes :

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Hope that helps,

$\endgroup$
3
  • $\begingroup$ I know the idea of a sieve is not new. The "new" thing here is that we do not consider all the numbers up to x but only x/3. In other words, we only consider the composite numbers in 6k+1 and 6k-1 progressions and deduce π(x) by substraction once we have counted all the composite numbers in those two progressions. $\endgroup$
    – Mbel
    Nov 13, 2011 at 21:42
  • 2
    $\begingroup$ That is the same ; you're just taking one step of the sieve out... $\endgroup$ Nov 13, 2011 at 21:46
  • $\begingroup$ True but the counting here involves producing indices of the composite numbers and eliminating them from the original list of indices to be left with only the primes' indices. The count follows. $\endgroup$
    – Mbel
    Nov 13, 2011 at 22:05
2
$\begingroup$

I think this idea is essentially quite good, if very well studied. The idea underlies the expression

$r_n = 1 - \prod_{k=1}^{n}{(1-\frac{1}{p_k})} $

which can be used to establish a floor for proportion of composites on $[1,p_n$-primorial] (and other intervals). While one would like to have that $1-r_n$ gives the proportion of primes, that is not the case. It does give an upper bound to the percentage of primes, but is not very useful. Not a bad idea, though, much less a silly one.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .