Counting with composites Please advise

In summary, the conversation revolved around counting with composite numbers and determining the standard for counting all primes to infinity. The original premise was that if all composites can be counted, then the missing numbers would be primes. The group discussed different ways to efficiently generate and handle large numbers, and suggested using a BigInteger package and log4j logging. The conversation also touched on using different programming languages and tools for math exploration and development. Overall, the group was intrigued and encouraged the speaker to make their work public.
  • #1
idiom
20
1
Counting with composites... Please advise

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.
 
Physics news on Phys.org
  • #2


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


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


idiom said:
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?
 
  • #5


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


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


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


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


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.
 
  • #11


Found this web page on computational math

http://userpages.umbc.edu/~rcampbel/NumbThy/Class/BasicNumbThy.html [Broken]

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 by a moderator:
  • #12


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


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


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


Indeed there is. Good luck with your work!
 
  • #16


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


Using a java app currently
 
  • #18


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.
 
  • #19


Fantastic thanks for the info:
 
  • #20


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:

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BzmRGf7l85GRNzNhZWQ4MzAtMDMzNC00ZjY4LWJlNzQtMjBlNTQ0OGJiM2U0&hl=en_US&pli=1 [Broken]

This is posted on my research website. I hope it can offer you some insight.

https://sites.google.com/site/primenumbertheory/ [Broken]

It is however, my contention that the computational difficulty involved in manipulating/finding sufficiently large primes will never be solved with great satisfaction.

Shalom
 
Last edited by a moderator:
  • #21


i agree so far every algorithm tried has failed. It seems that you need an algorithm that shifts gears when the previous one fails or learns from its failures.

Like the n^2 + N + 41 for n<=40 developing an algorithm to modify the equation for the next range and then then next... and determining what the new range is.

Just thinking.
 
  • #22


Indeed, also from my own experience in number theory this particular problem seems like one that demands the very information you are trying to obtain in order to solve it. In this way primes are both a fascinating enigma and a rather bothersome artifact of the set of naturals.
 
  • #23


very true. I once had an epiphany where I was thinking so if I take a list of primes and make a product then add one I'll have a new prime to add to my list (I was impressed by Euclid's proof). But I assumed that it was the next prime which it wasn't and so another great idea comes crashing down.

2 . 3 = 6 ==> 7

2 . 3 . 7 = 42 ==> 43

2 . 3 . 7 .43 = 1806 ==> 1807 which factors into 13x139 bust!
 
  • #24


The solution presented seems to have the problem of being non-deterministic. I am offering a deterministic solution for discussion. That is we can precisely calculate all of the composites in a deterministic fashion for any given number range. The primes themselves are the numbers missing from the sequence of composites.

So the question put forth is there any other methods of deterministic composite number generation?
 
  • #25


Speaking as a mathematician, deterministic means not probabilistic. The solution offered is deterministic but on a heuristic time scale. To my knowledge all such deterministic algorithms are in this way lacking. There are many probabilistic seekers/tests as well. The sieve of Eratosthenes is the most simple prime algorithm. It too is deterministic and seeks primes by determining composites, but it is very heuristic.
 
  • #26


Sorry about my terminology. Would you consider directly calculating all the composite numbers (Composites) in a range ( any give range you pick) heuristic? Or is it just heuristic if you use the result to find primes?
 
  • #27


When I say directly I mean each iteration gives a valid result.
 
  • #28


Both are actually heuristic (given what is generally common to academia and what I have observed from my own research). That doesn't mean yours is heuristic -it is possible you have discovered something others have missed.

Mathematicians seek a transcendental function --call it P such that a natural value input corresponds to a unique prime number. Now the word transcendental is used with regard for the underlying rigor: it has been proven --in fact has long since been proven-- that no polynomial will generate primes nor any algorithm that is reducible to a polynomial.

Now when it comes to what you speak: finding primes by determining the compliment --the set of composites-- this has been approached in a myriad of different ways --all of them very heuristic (logarithmic computing time/effort). The problem is if you have an algorithm that generates all composites and then fills those empty nodes with the primes you are either using a program that is flawed, recursive, non-deterministic, or is storage consuming. In any case the prognosis is poor. I should qualify this by saying that I am not yet old enough and jaded enough to believe it impossible that you haven't found a better idea than anybody else; it just seems unlikely.
 
  • #29


Best reply on the board yet! I have looked at a myriad of methods just as you describe and I agree with your conclusions. As for the primes themselves they manifest themselves in the calculations which a mathematician of your caliber could probably extract more efficiently then me. I have found the method to be much more efficient for factoring composites then anything I have been able to find, which also makes for a good primality test.

Believe I can eliminate flawed and non-deterministic. There is storage consumption but I believe it is a much smaller scale then conventional methods. The efficiency becomes particularly apparent when using a targeted range.
 
  • #30


Hi, idiom,
do you have already a "big number" implementation of your algorithm? If so, could you post the elapsed time of your algorithm when factoring each of the numbers of the sequence 10^n+1, for as large an 'n' as you can wait? Namely, in pseudocode,

n=1
while true {
n = n * 10

factor(n+1) // and print the elapsed time of this computation
}

(If you don't have yet a "big number" implementation, obviously the next step is to write one.)
 
  • #31


Have someone working with me on the code. He is pretty busy so it may take him some time to work through his stack.
 
  • #32


If it gives you some freedom, you can try learning Python. It's picked up quickly, tutorials are available (http://docs.python.org/tutorial/introduction.html), and it has "big number" support built-in, and used seamlessly without you doing anything.
 
  • #33


Thanks for the tip
 
  • #34


Interesting thread. By range, what do you mean? a specific grouping that will be of different sizes for increasingly larger numbers , or any range from say 0 to infinity?
 

1. What are composites?

Composites are materials made up of two or more different components that work together to create a new material with improved properties.

2. How does counting with composites work?

Counting with composites involves breaking down a larger number into smaller, more manageable parts using composite numbers. This can help simplify complex calculations and make them easier to understand.

3. What are some examples of composites?

Some common examples of composites include concrete, fiberglass, and plywood. These materials are made up of a combination of different components, such as cement and aggregate in concrete, or glass fibers and resin in fiberglass.

4. What are the benefits of counting with composites?

Counting with composites allows for more efficient and accurate calculations, as well as a better understanding of how numbers can be broken down into smaller parts. It can also help with problem-solving and critical thinking skills.

5. How can I incorporate counting with composites into my daily life?

Counting with composites can be applied in various ways, such as budgeting, cooking, and even playing games. By breaking down numbers into smaller parts, you can make tasks like calculating expenses or measuring ingredients easier and more manageable.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Linear and Abstract Algebra
Replies
22
Views
4K
  • Linear and Abstract Algebra
Replies
6
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
990
  • Linear and Abstract Algebra
Replies
6
Views
5K
  • General Math
Replies
1
Views
1K
  • General Math
Replies
2
Views
1K
  • General Math
Replies
2
Views
1K
Replies
16
Views
470
  • Calculus and Beyond Homework Help
Replies
3
Views
503
Back
Top