1. Jan 26, 2012

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?

2. Jan 26, 2012

Staff: Mentor

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.

3. Jan 26, 2012

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.

4. Jan 26, 2012

epsi00

and how exactly do you generate all the composites?

5. Jan 26, 2012

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.

6. Jan 26, 2012

Staff: Mentor

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

7. Jan 26, 2012

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.

8. Jan 26, 2012

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.

9. Jan 26, 2012

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.

10. Jan 26, 2012

DivisionByZro

11. Jan 27, 2012

Staff: Mentor

Found this web page on computational math

http://userpages.umbc.edu/~rcampbel/NumbThy/Class/BasicNumbThy.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.

Last edited: Jan 27, 2012
12. Jan 27, 2012

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.

13. Jan 27, 2012

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.

14. Jan 27, 2012

idiom

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

15. Jan 27, 2012

DivisionByZro

Indeed there is. Good luck with your work!

16. Jan 27, 2012

Staff: Mentor

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?

17. Jan 27, 2012

idiom

Using a java app currently

18. Jan 27, 2012

Staff: Mentor

thats good, its not the fastest but is a very useful language for math exploration.

Not directly connected to your work but useful info:

You should look into log4j logging so that you can track your algorithm as it does its computations. log4j collects and prints runtime info to a log along with the message text you provide. I use it to collect timing between statements. Its something that can be turned on and off via a properties file.

Another tool you might consider is the Open Source Physics toolkit which has charting capabilities that you could use to plot results or timings as you estimate the speed of your algorithm with larger and larger numbers.

H2 Database, a pure java-based database useful for storing your results or factorings... in a searchable fashion without worrying about data storage limits.

Some other cool things to check out:
- using scala instead of java, scala is statically type OO + Functional Programming language
- NetBeans for development IDE

19. Jan 27, 2012

idiom

Fantastic thanks for the info:

20. Feb 2, 2012

MechaMiles

Hope it's not too late to offer my insight. The notion of grappling the problem of primes via composites definitely has precedent. I offer the following thesis: