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?

  • 3
    @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.2011-11-23

3 Answers 3

4

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.

  • 1
    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.2011-11-13
3

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,

  • 0
    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.2011-11-13
2

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.