Register to reply

Counting with composites.... Please advise

by idiom
Tags: composites, counting
Share this thread:
Jan27-12, 12:58 PM
P: 20
Fantastic thanks for the info:
Feb2-12, 12:17 PM
P: 6
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:

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

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

Feb2-12, 12:34 PM
P: 3,002
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.
Feb2-12, 12:38 PM
P: 6
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.
Feb2-12, 12:51 PM
P: 3,002
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!
Feb2-12, 05:36 PM
P: 20
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?
Feb2-12, 05:43 PM
P: 6
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.
Feb2-12, 06:03 PM
P: 20
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?
Feb2-12, 06:05 PM
P: 20
When I say directly I mean each iteration gives a valid result.
Feb2-12, 06:18 PM
P: 6
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.
Feb2-12, 07:12 PM
P: 20
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.
Feb2-12, 11:06 PM
P: 688
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,

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.)
Feb3-12, 08:19 AM
P: 20
Have someone working with me on the code. He is pretty busy so it may take him some time to work through his stack.
Feb4-12, 03:49 AM
P: 688
If it gives you some freedom, you can try learning Python. It's picked up quickly, tutorials are available (, and it has "big number" support built-in, and used seamlessly without you doing anything.
Feb4-12, 11:50 AM
P: 20
Thanks for the tip
Feb13-12, 09:35 AM
P: 94
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???

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