Counting with composites..... Please advise

idiom

What is the standard for counting with composite numbers?
If I can count to infinity with all odd composites and factor them, would that be considered key to counting all primes to infinity. By default all missing odd numbers in the sequence would be Prime. Having difficulty finding the precedent for this.

My composite number line is growing to infinity without missing a composite, so at what point can we say all primes are the numbers that fall between, which leaves us with all primes to infinity?

Please Advise.

jedishrfu

I don't think this is solvable or has been solved. What you're saying is if you can count the composites in a given range of numbers then by simple arithmetic you'll know how many primes are there. I think we only have bounding values for the number of primes in a given range.

idiom

What I am actually saying is I can generate all the composites, that part of the problem is solved. Conversely I can also find all the composite factors.

epsi00

and how exactly do you generate all the composites?

idiom

Have only tested the number set up to the first 100 primes. The original premise remains. If I can generate all composites (by themselves) then by default do I have all the primes? (the primes are the missing numbers from the set. As an example if I take the odd set of numbers ( 9 15 21 25 27) the primes are the missing odd numbers (11 13 17 19 23). If I run this set to infinity then the primes are the missing odd numbers. I would like a community consensus to validate my proposition.

jedishrfu

check this definition in wikipedia basically a number is either composite or it is prime by definition. so if you can generate the list of composite numbers then the missing ones will be primes. The caveat is of course is if your algorithm truly filters out composites only.

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

idiom

Yes that is the caveat and right now it appears to be working perfectly. However I will need help setting the algorithm to test to very large numbers. I am very confident because the math is sound. Very excited about the fact the method can also be used to factor composite numbers quickly.

Thanks for the positive input. It seems obvious to me the result of generating each and every composite leaves nothing but primes, but the results seem almost too good to be true.

I have no reason to believe the results will falter for large numbers but of course more thorough
testing is needed.

DivisionByZro

But the problem isn't necessarily being able to create composites, it's being able to handle large numbers efficiently. What do you think the time complexity of your algorithm is? Answering that will tell you if you have a good method. If time didn't matter we could use the Sieve of Eratosthenes, but it's not feasible for large N.

idiom

Yes good point. The method allows targeting of a select segment without knowing the preceeding primes. If you are interested in a segment of large numbers you can generate the composites for that segment only. The Sieve of Eratosthenes appears incapable of doing that.

DivisionByZro

When I say "large N", I hope you don't think it to mean large as in 100000, or 1000000. Large N is something such as : N = 2^400. That's pretty big.
2^400 only has 121 digits. Some numbers used in cryptography are much larger.

http://blogs.scientificamerican.com/...enge-factored/

jedishrfu

Found this web page on computational math

http://userpages.umbc.edu/~rcampbel/...icNumbThy.html

It has some discussion on primality tests... Which you find interesting...

If you're doing this via computer then you'll have to consider using a BigInteger package because you'll run into number limits for integers at 2^16 or 2^32 or whatever largest integer the CPU can handle. After that you need to use a software solution like BigInteger to get beyond it and software solutions run slower.

idiom

Yes I am considering very large numbers. That is what makes the method useful. I can zero in on specific number ranges without sieving an enormous quantity of numbers.

DivisionByZro

Well now I'm intrigued. if your technique does indeed work as you are saying, then I'm puzzled. You should consider making your work public. It's the best way to get true feedback.

idiom

Would have already posted, but there is a proprietary advantage of factoring very large numbers.

DivisionByZro

Indeed there is. Good luck with your work!

jedishrfu

some things you can do to test your algorithm is to get a list of known primes and especially mersenne primes and try them out to see if they are factorable. Next would be composite numbers that passed some primality test to see if they are factored.

What language are you using for the algorithm?

idiom

Using a java app currently