Counting with composites..... Please advise

jedishrfu

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.

idiom

Fantastic thanks for the info:

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:

https://docs.google.com/viewer?a=v&p...hl=en_US&pli=1

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

https://sites.google.com/site/primenumbertheory/

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

Shalom

jedishrfu

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.

MechaMiles

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.

jedishrfu

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!

idiom

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?

MechaMiles

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.

idiom

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?

idiom

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

MechaMiles

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.

idiom

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.

dodo

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.)

idiom

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

dodo

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.

idiom

Thanks for the tip

lostcauses10x

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???