Prime Number Finder v2 and Goldbach Conjecture
- George Fane
- Sep 11, 2019
- 3 min read
These programs mark the deeper dive into Number Theory that I mentioned in my Factors and Prime Numbers article.
Prime Number Finder v2
I developed a better method to find primes than the method in the first version of Program Prime Number Finder (PNF). This came about largely by accident.
I watched a Numberphile video about the Goldbach Conjecture, which posits that any even number greater than 2 can be written as a sum of two primes. I resolved to create a program that could output the primes as row and column headers then output their sums in a grid pattern. I decided to write fresh PNF code, even though I usually copy and paste my old programs when I need their function again.
I tried to write this code in PNF v2 identically to that in PNF v1 without reference to the latter. However, they differed:
where the programs find all prime numbers below num.
When I looked back to PNF v1 after finishing PNF v2, I was surprised that they diverged in concept. I clearly remember thinking, while building PNF v2, that the contained method was the way I had always found primes: counting the number of factors out of [2, a], where a is a natural number below num, and hoping for only one factor: a itself (I now realize I could have hoped for zero factors out of (1, a)). I had surprised myself with PNF's inefficiency.
*Note: I later programmed an even better way to find primes.
**Note: In the penultimate sentence of the most recent paragraph, I use two colons. If sentence structure with colons can be described as Syntactical: Descriptive, I embedded a descriptive phrase within another. If necessary, embedding really should be used. It reduces the number of words necessary to convey a message while not unduly burdening a reader. In short, it is concise and understandable.
***Note: I am further surprised that my v2 code does not look much shorter, one of my metrics for efficiency, than v1. I suppose that computers perform addition faster than division, though.
I included a position finder for some inputted prime because it would help in determining the size of my Goldbach Conjecture program output. Finding position entailed moving through the array of primes and testing if each matched the inputted prime.
Goldbach Conjecture
Every even number is posited to be a sum of primes, per the Goldbach Conjecture. This has held true for the largest testable evens but has not been rigorously proven. I wanted to create a visual representation of the conjecture.
Program
First, primes must be found. I copied my method from PNF v2, which I really should have pasted as a function.
Afterwards, the sums of primes must be found. In an earlier draft of this program, I did not include the first row nor first column, meaning that the number 4 would output in the top left corner as the sum of prime[0] and prime[0], which is 2. I remember this development as another instance when arrays starting at 0 confused me. I ended up treating the output as a matrix: I filled the first row and column (row 0 and column 0) with the primes. Afterwards, I made the usual structure for filling two dimensional arrays: a for loop moving across the columns within a for loop moving down the rows. However, I didn't store anything; the two for loops merely kept track of the row and column, and which primes to add.
In that earlier draft, the alignment of columns was awful. Back then I placed a space after each number, meaning that the lower rows, containing sums of higher and higher primes, have more digits and push sums after it further to the right. I thought of a way to track the number of digits in a number. I realized that taking the log in Base 10 and storing the value as an integer variable would work. For consecutive integers a and b, if double variable c falls between a and b, c is stored as a when converted to an integer:
The number of digits d in 98 and 10 will both be stored as 1. From there, 3-d spaces are outputted before each number. Sums in the hundreds have a d-value of 2 and will have one space before them. Sums less than 10 have a d-value of 0 and will have three spaces before them.
Every natural even integer possible under the sum of the highest primes appears to exist within the Goldbach output. While this is not a proof by any means, I enjoyed the challenge of improving my prime-finding process and outputting assorted sums.
Thank you for reading!
George Fane
Comments