Prime Numbers

[storm5510]

The problem with checking numbers with terminating digits of 1,3,7 and 9 is that they will include multiples of 3 such as 9,(15),21, 27, 33, 39,...,just keep adding 6 to these numbers and the pattern repeats.(includes terminating digit 5) as 1,7,3,9,5,1,7,3,9,5,...,None of these numbers in this sequence towards infinity are prime.

Calculating Digital Roots is a method of summing individual digits of any number to a single digit number between 1 and 9.

9 = 9
21 = 2 + 1 = 3
27 = 2 + 7 = 9
33 = 3 + 3 = 6
39 = 3 + 9 = 12 = 1 + 2 = 3

31 = 3 + 1 = 4
37 = 3 + 7 = 10 = 1
43 = 4 + 3 = 7



Any numbers with Digital Root of 3, 6 or 9 will not be a prime number. So calculating digital roots is useful method of 'rooting out' odd numbers which terminate with 1,3,7,9, that have digital roots of 1,4,7 and 2,5,8 but not 3,6 or 9.

I just got up from a nap and looked at this again and it makes perfect sense:

2 = 2
3 = 3
5 = 5
7 = 2
11 = 1 + 1 = 2
13 = 1 + 3 = 4
17 = 1 + 7 = 8
19 = 1 + 9 = 10 = 1 + 0 = 1
23 = 2 + 3 = 5
29 = 2 + 9 = 11 = 1 + 1 = 2

Those above are a small handful of little primes. It's a continual adding of digits until you have only one digit:

102 breaks up into 1 + 0 + 2. Add that and you get 3.

Amazing and simple. Implementation into code may be tough. I'll try it with VB6 first.

[Nightwalker83]

SieveOfEratosthenes and EulersSieve in post #17 There is just a small difference between the two, but that has a considerable difference on performance.

What I'm getting at is just removing the even numbers from the start hence, only finding the odd numbers. This is because 2 can divide into any even number.

[storm5510]

Once I started coding, it was actually really simple, and is it ever fast!

I need to test it more then I'll post it here.
.
.
Edit: There seems to be a problem. I'm getting a lot of non-prime numbers. I need to do more studying.

[storm5510]

If you are attempting to discover new primes then I strongly suggest you narrow the field by just focusing on ODD Numbers with DIGITAL ROOTS of 1,4,7,2,5,8. These numbers will be either primes or products of primes > 3 multiplied by primes > 3.

All other numbers:

EVEN numbers with digital roots 1,4,7,2,5,8
ODD & EVEN numbers with digital roots 3,6,9

will be multiples of 2 or 3 or multiples of both 2 & 3.

This would be okay if the products of primes could be removed.

[TriLogic]

This would be okay if the products of primes could be removed.

There are MANY WAYS to remove products of primes from this sequence. see PM

[storm5510]

There are MANY WAYS to remove products of primes from this sequence.

If you could elaborate further, I would be grateful.

[Pradeep1210]

What I'm getting at is just removing the even numbers from the start hence, only finding the odd numbers. This is because 2 can divide into any even number.

That's exactly what it does. Since 2 is the smallest number, it eliminates all multiples of 2 (i.e. all even numbers) in the first loop. Then continues with 3 then 5 then 7 and so on.

The only difference between the two algorithms that make a performance difference is that while in SieveOfEratosthenes a number can come for elimination more than once, in EulersSieve any number can come for elimination only once.

[storm5510]

Euler's Sieve is fine except for one thing. It relies on a list of primes previously found. I cannot do that. I have no limitation of numbers to sieve out. There could end up being billions(s). An array cannot hold all that, and the time involved in processing the contents, if it could hold it, would be really protracted.

I also have to periodically stop the program. Once done, any list would be gone. Using a list is simply not practical.

[Nightwalker83]

That's exactly what it does. Since 2 is the smallest number, it eliminates all multiples of 2 (i.e. all even numbers) in the first loop. Then continues with 3 then 5 then 7 and so on.

The only difference between the two algorithms that make a performance difference is that while in SieveOfEratosthenes a number can come for elimination more than once, in EulersSieve any number can come for elimination only once.

Ah ok cool!

[Code Doc]

Storm, I modified my code to run a little faster by ignoring even numbers. The prime numbers are now being written to a random access file as long integers. It will stop when the [2^31 - 1] limit is reached. I am predicting a final file size of about 1.6 Gb and am tracking the execution time. So far, it has been running 36 hours, and I am now generating big primes at the rate of about 20,000 per minute. Total file size is 160,000 Kb, so we are perhaps at the 10% point.

As expected, the program is slowing down as the numbers get larger. When it first took off, the primes were banging out at 500,000 per minute. Regardless of the lethargy at the top end, it's fun to occasionally watch Explorer update the file size as the primes are found and stored. I have made no concerted effort to shut down other programs, but most of the time I only run three or four in multi-tasking mode.

Now, what should I do with my 430 million or so long integer primes when it's all finished?

[storm5510]

@ Code Doc:

Well, I'm not going to be able to touch that on speed. I had to restart mine over again yesterday. That's what I get for experimenting with the code. I corrupted my data files. I have recovered back to 194 million primes in 2,164 data files.

I use registry keys in the program so I can stop it and restart again where it left off. I have it update these at 60 second intervals, or when I stop the program.

As the numbers have gotten larger, the per-file iteration time has increased. It is at 1.12 minutes per file with primes above 4 billion in value. When this time passes 5 minutes, I'll stop the process and wait for something new to come along to speed it back up again. Not sure what that will be yet. I started messing with this in 2005 on a P4. I gave it up when per-files time passed 5 minutes also.

What I mean by "per-file" is the amount of time it takes to create a 1 megabyte data file. I could have gone much larger with the data files, but I wanted Notepad to be comfortable with them and not crash.

[Code Doc]

Notepad? I would never allow that to constrain the processing. You can always write simple utility programs to extract the primes for subfiles that you can then tweak to display in Notepad, list boxes, grids, or whatever.

So, all my long integers are packed into one file that in essence represents a huge lookup table. The file is now approaching 180,000 Kb as I write. That's 45 million primes gathered to date.

I considered rewriting some of the code so that checking for previous primes could be done within the collection file to skip them and possibly improve speed. We used to do this years ago by reading in 1 Mb chunks into huge memory arrays as they became available. However, I think that read and skip routine could actually slow down the code inside the main loop. I may experiment with that after the file is completely built.

I suppose one possible use for this master file is that you can then check extremely fast if any number less that 2^31 is a prime using a search through the file. We can experiment with optimal search routines. Other than that, I am not sure what to do with the primes. Any other ideas?

[storm5510]

Notepad? I would never allow that to constrain the processing...

I considered rewriting some of the code so that checking for previous primes could be done within the collection file to skip them and possibly improve speed...

I suppose one possible use for this master file is that you can then check extremely fast if any number less that 2^31 is a prime using a search through the file...

If someone that is very low on the computer literacy scale were to get a hold of these, well, you know. Besides, I don't see it as a constraint.

I still don't feel trying to use any type of list is practical if one has no limit of what they're trying to discover.

Speaking of limit, why 2^32?

[jemidiah]

2^32 is (about) the maximum size of an integer using 32 bit machines. Past that, the computer will either have to use floating point, causing you to lose low-order bits [i.e. 999999999999999999999 becomes 999999999999000000000], or you'll have to use more complicated representations, likely chaining together some integers.

What's the maximum size your function needs to handle?

[storm5510]

This is why VB6 had a limitation on some features, like Mod, for example. It dates back to 1998, and things were not nearly as advanced as now.

The "Double" data type has been around for a long as I can remember. At the same time, I've seen large numbers lose some of their "weight" at the lower end, as in the example above.

[Code Doc]

Storm, I am only using long integers to store primes less then 2^31. After that, I will move on to stage II and use an 8-byte currency data type to hold larger ones. That will retain 15-digit accuracy to the left of the decimal and prime numbers up to 9,223,372,203,685,477. Even when stored packed, the collection of these enormous primes may exceed the capacity of my 160 Gb back up hard drive.

My long integer prime number file has now reached 250 Mb and contains about 63 million primes. The largest is just under 300,000,000. I'm about at the 15% mark in collecting them all for stage I in the processing. The collection rate had now dropped to 14,000 per minute or 20 million per day.

I project that just before the last long integer prime is found, the collection rate will have dropped to about 1200 per minute. That's the price of progress.

Now, what did you say we should do with all of them?

[storm5510]

Now, what did you say we should do with all of them?

Was you not telling me of someone who wanted all primes up to 10^10?



Edit: I'm past 55 hours total run time. 286 million primes found. Current max value is above 6 billion.

[Code Doc]

Storm said, "I'm past 55 hours total run time. 286 million primes found. Current max value is above 6 billion."
--------------
Terrific! Your program's collection rate now exceeds mine, assuming that you have found all the prime numbers. I have collected and stored only 70 million of them and I imagine the largest one is still much less than a billion in magnitude.

However, I'm only using one file to store them all. You said you are using several thousand files? How do you intend to track all of them? Lose a few and you are toast.

[storm5510]

Storm said, "I'm past 55 hours total run time. 286 million primes found. Current max value is above 6 billion."
--------------
Terrific! Your program's collection rate now exceeds mine, assuming that you have found all the prime numbers. I have collected and stored only 70 million of them and I imagine the largest one is still much less than a billion in magnitude.

However, I'm only using one file to store them all. You said you are using several thousand files? How do you intend to track all of them? Lose a few and you are toast.

76 hours at 7.4 billion magnitude.

I'm using WinRAR to archive them in groups of 100. There are 36 archives so far. I need to catch it up again. There is an "index" file that is updated which gives the starting value of each data file. Below is an excerpt:

P_003886.Txt Start = 7464216839
P_003887.Txt Start = 7466202691
P_003888.Txt Start = 7468184309
P_003889.Txt Start = 7470172309
P_003890.Txt Start = 7472164769

I keep duplicates of the archives on an external hard drive. I won't lose anything.

My algorithm is very simple, testing each value for divisibility from 3 to N - 2 stepping in multiples of two; odd values only, excluding five.

[Code Doc]

Is N the size of the number being tested or its square root? You only have to check numbers for divisibility that are smaller than the square root of the number being considered.

[storm5510]

Sorry, its square root.

[storm5510]

100 hours total run time now with over 407 million primes found.

[Code Doc]

I now have 100 million primes found and stored. I found out something dreadful. My machine appears to not calculate any primes when it drops into sleep mode. I have Windows doing this automatically after 3 hours of keyboard and mouse inactivity, so I have lost lots of real time calculations during the past few days.

My largest prime stored is still just under 1 billion, so you are running circles around me.

[storm5510]

I don't know about you're computer, but mine "appears" to shut completely down when it enters standby mode. No amount of mouse movements or keyboard presses will bring it back. I have to press the power button. If I had to guess, I would say it only does RAM refresh during standby.

[storm5510]

I just passed 10^10 magnitude. It took 121.6 hours. I have 484.3 million primes stored in archives. The percentage is 9.1.

The next milestone would be 10^11. If one does the progression, it would take 1,216 hours to reach it. That's just over 50 days total run time.

[Code Doc]

Progress report:
My largest stored prime number just exceeded 3 billion. These numbers are being stored inside only two files, and the second one advances steadily in size. The first file requires 410.6 Mb of disk storage and contains all primes from 2 to 2^31.

The second file is now about 320 Mb in size and contains all primes exceeding 2^31. The program will eventually top out when the largest prime exceeds 10^10, although I could extend it to the limit of an external hard drive or with primes reaching 10^15 (whichever comes first) using no more than 8 bytes per prime.

This is truly an interesting project, but I fear that I am creating King Kong. What do I do with the beast after I create it?

Any suggestions?

[storm5510]

@Code Doc:

I am back up to 152 million written. No data corruption this time. I think I know what the problem may have been:

DataFile.WriteLine(Cstr(Number))

If I am not mistaken, this is trying to do a double conversion to a string. The WriteLine method is described as "writing the string equivalent" of any expression.

DataFile.WriteLine(Number)

Changing it to this, or back to this, whichever, removed the corruption. It is possible it may have changed it on one of my many touch-ups.

This is truly an interesting project, but I fear that I am creating King Kong. What do I do with the beast after I create it?

Keep adding to it. If you get tired of it, the interest will return. It always has for me. Even if it took years waiting on new hardware.

[storm5510]

I had to trash all my data again. I still have corruption problems. Non-numeric characters appearing in my numeric values. Not sure I will be able to solve the problem.

[Code Doc]

Storm, that is a nightmare. I thought best to extract all prime numbers up to 10^10 before doing any validity testing. I have thus far found and stored all primes reaching about 6.1 x 10^9, so I am getting close. My two files that together store them all now total 1.6 Gb in size.

I wish there were some way I could help at this end. I feel your pain.

[storm5510]

@Code Doc:

It was all for nothing. Read the link below.

http://www.vbforums.com/showthread.php?t=585609

[Code Doc]

Storm, I think my approach still makes the most sense. Build the data in a random acces fille stored packed as long integers and eventually as currency data types for the monsters over 2^31. Then when the files are eventually assembled, write code to play them back out as strings for visual display, examining whatever pieces of the files that you want to show.

[storm5510]

..Build the data in a random acces fille stored packed as long integers and eventually as currency data types for the monsters over 2^31...

When you say "random access" do you actually mean sequential? You are writing them one following the previous?

I thought about other file modes. .Net is a little tricky on that. I have no good examples to follow. Besides, I'm already back up to 1.6 GB of data.

[Code Doc]

When you say "random access" do you actually mean sequential? You are writing them one following the previous?

I thought about other file modes. .Net is a little tricky on that. I have no good examples to follow. Besides, I'm already back up to 1.6 GB of data.

No, it's not a sequential file, even though it is being assembled one record at a time. When built, any record on the file can then be accessed by an immediate leap to a specifiic record--such as record number 100 million, and the prime number can be immediately revealed. The only thing I have to do in code is examine the value of the desired prime number. If over 2^31, then I switch to the big primes being stored as currency.

Your progess is excellent. The value of the most recent prime that I have collected is about 6.9 billion. Total file size has now reached 2 GB.

[storm5510]

...Your progess is excellent. The value of the most recent prime that I have collected is about 5.9 billion. Total file size has now reached 1.8 GB.

I'm back above 6 billion in magnitude and have 3.4 GB stored. 72.8 hours run time.

I understand your file format now. Writing as sequential, but in a way that can enable reading as random. A user defined "type" with each record being the same size. I considered something like that. It would have been more drive-space efficient, but with two rather large drives, I opted for plain text stacked; not CSV.

Sooner or later, a better algorithm is going to be a must. I'm still searching. It's hard to find anything practical with examples easy to understand.