So, Prime Filters?

[Jarhyn]

I've had a bug in my brain since reading to a shamefully early point in Fundamentals of Mathematics.

There was a question about proving something or other about the expression of all exponents as a unique product of prime squares.

Anyway, there wasn't much in the book about prime number theory up to that point and I wanted to just fuck around with a computer and I wanted to write something to fairly quickly calculate "whatever the next prime" was.

I started writing numbers in various bases, first unary (which is really just strings of 1's, where 0 would have to be "1-1"), then in binary, then in trinary, etc. and then saw the pattern of where primes occurred being only where they are the only base so far with a "zero" at its one's place, using a spreadsheed and some copy/paste mod operator. Essentialy, there are "holes" in the field of "zeroes" at every prime that can be answered by creating a new "zero" in the field.

This probably isn't interesting either.

But I wrote an algorithm that rolls a wheel for every prime found so far and determines if they all come up empty.

I'm aware there's probably some more efficient structures I could use, but this is what I have...

// number_stuff.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <cstdint>
#include <vector>
#include <map>

int main()
{
	//calculate all 64 bit prime numbers? sure, why not
	uint64_t val = 1;
	uint64_t jump = 1;
	std::vector<uint64_t> primes;
	std::map<uint64_t, int64_t> counters;
	

	do
	{
		uint64_t numPrimes = primes.size();
		uint64_t highest = 1;
		std::map<uint64_t, uint64_t> is_not;
		val += jump;

		bool bFound = false;

		for (int i = 0; i < numPrimes; i++)
		{
			int prime = primes[i];
			int counter = counters[prime];
			counter -= jump;
			while (counter < 0) 
				counter += prime;
			
			//a zero was found in the counter pool, not prime.
			if (!counter)
				bFound = true;			

			counters[prime] = counter;
		}
		if (!bFound)
		{
			printf("%d\r\n", val);
			primes.push_back(val);
			counters[val] = val;
		}
		else
		{
			printf("miss: %d\r\n", val);
		}
		for (uint64_t prime_idx = 0; prime_idx < primes.size(); prime_idx++)
		{
			//we need to find the hole. For each prime, there is certainly a place
			//the hole will not be: at its next basic zero.
			is_not[counters[primes[prime_idx]]] = counters[primes[prime_idx]];
		}

		for(highest = 1; is_not.count(highest); highest++);
		
		jump = highest;

	}while (val < 20000);
	printf("%d, %d\r\n", val, primes.size() -1);
}

Anyway, after I wrote something that worked mostly after the way I worked the spreadsheet analysis.

After writing my program, I looked up something about calculating the next prime and came on this thing about prime sieves, and I figure this must be some variant of an existing thing. And then it was past the time I generally like to stay awake for the night. Something about using optimizations with base 60 numbers?

There are apparently 2262 primes less than 20k according to google, so this is seeming to yield a correct answer (the actual size needs adjustment since it adds an extra prime).

It also yields a depressing number of misses that I need to track down.

Enjoy criticizing the thing I wasted my Sunday afternoon on.

 

[Swammerdami]

I once won an on-line programming contest where, among other things, I needed to determine primality quickly. My comments are probably irrelevant to your question, but here goes anyway:

(1) A micro-optimized nextprime() function may use a form of the weird Duff's Device if you're familiar with that!

(2) Ignoring tiny 1-digit primes, there are only 8 possible primes in any range N <= p < N+30, so a precomputed table of, say, 10 million bytes will dispose of the primality test for any candidate less than 300 million.

(3) For numbers larger than 300 million I used the high-speed  Fermat primality test with base 2. If it passed that test, I repeated the Fermat test with bases 3 and 5 (and sometimes 7, 11, 13, 17). If it passed all these tests I called it a prime.

(4) There are "pseudoprimes" which will pass these tests even though they're composite. Fortunately they were much too rare to matter in my application. (BTW, there are an infinite number of  Carmichael number which are composite numbers that flunk the Fermat test in EVERY base.)

(5) To avoid running the Fermat tests, I checked for divisibility by specific primes, including 30 largish numbers just to detect some of the pseudoprimes. The largest of these divisors was 34501, needed to detect the pseudoprime 2,380,603,501 = 34501 * 69001.

(6) There are probabilistic tests slower than, but with lower error rates than, Fermat's test but they weren't needed to win that on-line contest!

 

[steve_bank]

Wasted?

I have not played a video gane since around 1983, and that was an arcade game.

I heard it said learning something new is the best entertainment .

I can follow the code top down execution, but without knowing the include files and the objects I can not work out the details.

 

[Jarhyn]

Wasted?

I have not played a video gane since around 1983, and that was an arcade game.

I heard it said learning something new is the best entertainment .

I can follow the code top down execution, but without knowing the include files and the objects I can not work out the details.

The idea is that for every prime found, a counter is started. The next prime is not any number which lands on an drained counter, as each counter represents the ones place of a "prime base", and the very definition of a prime is that it is only first expressable in its own base with an empty "ones" position, as restatements of what a prime is.

At each jump, all counters are iterated by the jump, checked to see if they landed on zero, and then if they did not (zeroes indicate factors) then it is added to the list of primes, and the list of counters.

The next stage of the process is learning how to apply rules for scaling up efficiency. After all, there is a cadence buried in the rhythm of any given set of primes which repeats it's candidate timings. This cadence would grow in complexity with each additional base, but I suppose could be of arbitrary size.

The origins of the project were "what is the highest number of contiguous primes we can count?"

 

[Swammerdami]

The origins of the project were "what is the highest number of contiguous primes we can count?"

I don't understand your project well, but this reminds me of a fact of number theory that strikes me as an amazing example of mathematicians' reach:

It is known that there is an unusually large number of primes near 10⁹⁶⁰⁸ even though few, if any, of the particular primes of this size are known!

I think this was discovered by, or based on other discoveries by, John Littlewood. This page may be a starting-point, though the whole topic is complicated and confusing.

 

[Jarhyn]

The origins of the project were "what is the highest number of contiguous primes we can count?"

I don't understand your project well, but this reminds me of a fact of number theory that strikes me as an amazing example of mathematicians' reach:

It is known that there is an unusually large number of primes near 10⁹⁶⁰⁸ even though few, if any, of the particular primes of this size are known!

I think this was discovered by, or based on other discoveries by, John Littlewood. This page may be a starting-point, though the whole topic is complicated and confusing.

So, the overall thrust is thus: every number is capable of being expressed as some product of primes raised to exponents.

Next is this idea of "bases", which is to say, a number for which the digits are 0 to N-1. Prime numbers are, thus, numbers for whom, when it is expressed in all bases, it is the only number for which there is no 'tens' place.

So for three, in base 3, the number is 10b3, but 2 is 11b2, 111b1, and 3b6, etc. For all bases greater than three, we will not be at 10 yet, and for all numbers less than 3, the number terminates with nonzero: only prime%prime == 0; for all nonprime number A there is some number where A!=B where A%B = 0.

I also know that there cannot be a prime in 3. And there cannot be a prime in 1, as that is the next of 2, so the next prime is at the "hole" where we have not ruled it out: it's at 5.

This falls down in that it does not currently rule out multiples, and so it finds 16 (13+3, since 2 is already ruling out 14) and then has to actually check it, at which point it sees the zero on 2.

 

[Jarhyn]

The origins of the project were "what is the highest number of contiguous primes we can count?"

I don't understand your project well, but this reminds me of a fact of number theory that strikes me as an amazing example of mathematicians' reach:

It is known that there is an unusually large number of primes near 10⁹⁶⁰⁸ even though few, if any, of the particular primes of this size are known!

I think this was discovered by, or based on other discoveries by, John Littlewood. This page may be a starting-point, though the whole topic is complicated and confusing.

Just so you understand what I mean here...

So, there's an action of this particular formulation that will jump to a non-prime number because it doesn't mark off more than a single destination per prime. Look at the following execution:

The filter finds "2" and adds it to a list. 2"s counter starts containing "2", which says "there shall be no prime, 2 steps from here."

Then when it goes to say "where may the next prime be?" It constructs a list. This list contains "2". Starting at "1" it finds the first number of steps where a prime may be. This means the "first hole" is "1" step. Step forward 1.

Now that the number is three, decrement the counters by that number of steps, as they must count.

Now we know that there may not be a prime in a single step, and there are no primes FIVE steps out, and there are no primes 3-2=1 steps.

So one jump and five jumps ruled out the first hole is at 2.

Seven, my counters are 1, 2, 3, 7: our next prime is at 4 steps (11).

At 11, my counters are 1, 1, 1, 3, 11, indicating prime in 2

At 13, though, my counters are 1, 2, 4, 1, 9, indicating 16. 16 is not prime and has been indicated because the algorithm does not know to also add multiples to the list.

That said, when it iterates it will see a zero count on 2: 1-3=-2, -2+2 = 0, and so it finds a zero count, triggering a search for a jump again.

 

[Swammerdami]

Is your approach fundamentally different from the  Sieve of Eratosthenes ?