Prime Patterns

[William Hemsworth]

Hi everyone.
Here is a program I made which will find patterns in a list of primes.
It does this by finding the difference between each prime and adding them to a vector like this:

Primes:      2 3 5 7 11 13
              ^ ^ ^ ^  ^
Difference:   1 2 2 4  2

After it has all the differences between the primes it then checks for patterns by using a nested loop to check different parts of the vector with each other.

Protend these are the results in the vector, is would match up these numbers and display the first prime in the pattern along with the match length.

Differences: 1 2 2 4 2 3 1 1 2 2 4 2

1 2 2 4 2 3 1 1 2 2 4 2
|_______| --> |_______|

Match Length: 5

#include<iostream>
#include<vector>
using namespace std;

typedef unsigned int UINT;

#define MIN(a,b)   ((a)<(b)?(a):(b))
#define MAX(a,b)   ((a)<(b)?(b):(a))

template<typename type>
bool IsPrime(type val) {
   if (val == 2) return 1; else
   if (val < 2 || val % 2 == 0) return 0;
   bool prime = 1;
   register type vd2 = val/2;
   for (register type i = 3; i < vd2;i+=2) {
      if (!(val%i)) {
         prime = 0;
         break;
      }
   }
   return prime;
}

UINT MatchLength(const UINT *a1, const UINT *a2) {
   UINT len = 0, _max = MAX(a1, a2) - MIN(a1, a2);
   for (; len < _max && a1[len] == a2[len]; ++len);
   return len;
}

int main() {
   cout << "Enter filter: ";
   UINT filter;
   cin >> filter;

   cout << "\nEnter range of primes: ";
   UINT primeCount;
   cin >> primeCount;

   vector<UINT> primesDifs;
   vector<UINT> primeNums;

   UINT oldPrime = 0;

   cout << "\nLoading primes...\n";

   for (UINT i = 0; i < primeCount; ++i) {
      if (IsPrime<UINT>(i)) {
         primesDifs.push_back(i - oldPrime);
         primeNums.push_back(i);
         oldPrime = i;
      }
   }
   primesDifs.push_back(0);
   cout << "Finding patterns...\n\n";

   UINT length = primesDifs.size();
   UINT matchLength;

   for (UINT i = 0; i < length; ++i) {
      for (UINT j = i; j < length; ++j) {
         matchLength = MatchLength(&primesDifs[i], &primesDifs[j]);
         if (matchLength >= filter) {
            cout << "Match Length: "
                << matchLength
                << '\t'
                << primeNums[i]
                << '\t'
                << primeNums[j] << '\n';
         }
      }
   }
   cout << "\nDone";

   cin.ignore();
   cin.ignore();
   return 0;
}

When the program starts try giving the following inputs and look at the results:

Enter Filter: 10           (minimum match length)

Enter range of primes: 200000

By looking at the results you can see it can't be a coincidence that 7 results with 10+ matches all have something in common.

• Firstly the last didget of each matched prime is the same, this happends for 99% of the time when the filter is 10, but as the filter decreases this doesn't happen as much. Try it with a filter of 5 and you will see.
• The last four results all occur in a very small range. (12329 to 12373) and (36479 to 36523) out of a total of 200000 possible results.

Now Im curious of whats giving these results and if there are any other methods of finding patterns that could be useful. So if you know any other ways of doing this please post them here :), also I woulden't mind any other opinions and comments.

Thanks for reading.

NOTE: I just realized that you put in there that "suppose" these are the output vectors, so the whole below post was completely a waste of time, no point in reading.

I didn't really look at the code at this point, but if your code outputs

Differences: 1 2 2 4 2 3 1 1 2 2 4 2

The above "differences" imply you have the values as primes:
2,3,5,7,11,13,16,17,18,20,22,24,26 if I did my math right
16,18,20,22,24 and 26 aren't Prime numbers so the coincidence of the numbers found are possibly code induced, not actual coincidences of prime numbers,

I'll have to look how you're calculating your Prime numbers,

I actually tried working on a simple program to start outputting prime numbers but it quickly became a pain, cause you have to account for all numbers that are below the current number being a possiblity of a divisor of the current number

I'll try to take a look at it tommorrow or the next time I'm at a computer.

[Adak]

I'm not familiar with C++, but a few points on prime numbers:

If no divisor is found w/o remainder less than or equal to the value of the square root of the number, then the number is prime. This really speeds up your testing.

Numbers which divide evenly by 2,3,5, or 7, should not even be tested as a divisor.

Just glancing over the code for finding prime numbers, it doesn't look right. Have you compared it's output with a reference list of prime numbers?

[William Hemsworth]

Nope, perhaps you could give a good example of a well optimised prime number generator ?

[Shaun32887]

I actually tried working on a simple program to start outputting prime numbers but it quickly became a pain, cause you have to account for all numbers that are below the current number being a possiblity of a divisor of the current number

Well not ALL, just every integer up to that numbers square root. :)

[William Hemsworth]

Alright, ive optimized by making it go up to the square route of the value :icon_smile:

template<typename type>
bool IsPrime(type val) {
   if (val == 2) return 1; else
   if (val < 2 || val % 2 == 0) return 0;
   bool prime = 1;
   register type _max = sqrt((double)val) + 1;
   for (register type i = 3; i < _max; i += 2) {
      if (!(val%i)) {
         prime = 0;
         break;
      }
   }
   return prime;
}

I noticed a huge increase in speed when using this.
How else could it be optimized?

[n1337]

Well not ALL, just every integer up to that numbers square root. :)

Yes, Shaun is correct. However there is more...A related theorem says that every number is either prime itself, or else is a product of primes. I forget who proved this (Euclid?) but here is a proof (I did it quickly, so it might by slightly sloppy :)):

Let n be an integer greater than 1. We must show that n is either prime or a product of primes. If n is prime, then we are done (clearly the result follows). If n is not prime, then n is composite, and thus there exist integers x and y such that x*y=n. Now, if x and y are primes, then we are done and n is a product of primes. If not, then x and/or y can be divided further into a product of smaller integers. Clearly the process iterates until we have broken the integers into primes (i.e. we are bounded below by 1, and since we are dealing with integers, the process repeats finitely many times). Thus the result follows...(I know this is really quick so you can search for a better? proof online...)

From this result you can see that you do not need to test EVERY integer up to a given number n to determine whether n is prime. Rather, since n is either prime or a product of primes (as we just showed), you only need to determine whether n is divisible by any prime p less than the integer square root of n. Thus you can build a table to help speed up the process (memoization).

There are also a few different algorithms for finding primes. One is the Sieve of Eratosthenes. Another is the Sieve of Atkin (which is more complicated, but I'm told is faster if properly optimized...) You can probably find more with a quick google search. (Note I didn't read your code at all so I apologize if I am being repetitious and/or ignorant).

This link has some general information about prime numbers, and this link has some more fascinating prime number related ideas.

Hope that helped...and goodluck!

Cheers!

[Prabakar]

I just want to say one more optimization. Instead of using the regular math::sqrt() function which returns a double if we write our own code we need not give importance to the decimal value hence speeding up the process. Hope this helps:)