Register to reply

Counting with composites.... Please advise

by idiom
Tags: composites, counting
Share this thread:
idiom
#1
Jan26-12, 09:57 AM
P: 20
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.
Phys.Org News Partner Science news on Phys.org
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces
jedishrfu
#2
Jan26-12, 10:22 AM
P: 2,777
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
#3
Jan26-12, 10:44 AM
P: 20
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
#4
Jan26-12, 01:15 PM
P: 84
Counting with composites.... Please advise

Quote Quote by idiom View Post
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.
and how exactly do you generate all the composites?
idiom
#5
Jan26-12, 04:19 PM
P: 20
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
#6
Jan26-12, 06:14 PM
P: 2,777
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
#7
Jan26-12, 07:33 PM
P: 20
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
#8
Jan26-12, 09:42 PM
P: 252
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
#9
Jan26-12, 10:29 PM
P: 20
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
#10
Jan26-12, 10:36 PM
P: 252
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
#11
Jan27-12, 02:09 AM
P: 2,777
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
#12
Jan27-12, 08:27 AM
P: 20
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
#13
Jan27-12, 08:43 AM
P: 252
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
#14
Jan27-12, 09:25 AM
P: 20
Would have already posted, but there is a proprietary advantage of factoring very large numbers.
DivisionByZro
#15
Jan27-12, 09:26 AM
P: 252
Indeed there is. Good luck with your work!
jedishrfu
#16
Jan27-12, 09:39 AM
P: 2,777
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
#17
Jan27-12, 10:25 AM
P: 20
Using a java app currently
jedishrfu
#18
Jan27-12, 12:48 PM
P: 2,777
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

Good luck on your quest.


Register to reply

Related Discussions
Proof of composites Linear & Abstract Algebra 3
Help with composites please! Calculus & Beyond Homework 0
Continuity Of Composites Calculus & Beyond Homework 5
Continuity Of Composites Calculus & Beyond Homework 1
FEM for composites in SolidWorks Mechanical Engineering 11