Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
@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. –  Dimitrije Kostic Nov 13 '11 at 21:10
6  
@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. –  ItsNotObvious Nov 13 '11 at 21:10
    
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 –  simplicity Nov 13 '11 at 21:18
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. –  Mariano Suárez-Alvarez Nov 23 '11 at 3:07

3 Answers 3

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.

share|improve this answer
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. –  Mbel Nov 13 '11 at 21:55

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.

share|improve this answer

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,

share|improve this answer
    
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. –  Mbel Nov 13 '11 at 21:42
2  
That is the same ; you're just taking one step of the sieve out... –  Patrick Da Silva Nov 13 '11 at 21:46
    
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. –  Mbel Nov 13 '11 at 22:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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