🧮
Primes
Week 8
You are interested in number theory and want to find primes that are either 1 less or 1 greater than a square number - i.e. x^2 ± 1
These numbers also have practical uses in some cryptography (Gaussian lattices), error-correcting codes like BCH etc
The range of x values to test should be from 1 to 10,000
The amount of numbers that match either the minus 1 or plus 1 rule should also be output
You are also curious about the difference between consecutive x values that for have numbers that match this criteria - will the gap between them remain constant, grow linearly, exponentially or be completely random
Below shows the expected data and format for running your program for that values 1 ≤ x ≤ 10
Note: the empty new lines can after the "Difference" (etc) be either included or not (answer will be correct regardless) - they are just added to separate the output and make it more readable
1^2 + 1 = 2 Difference: 1 2^2 - 1 = 3 Difference: 1 2^2 + 1 = 5 Difference: 0 4^2 + 1 = 17 Difference: 2 6^2 + 1 = 37 Difference: 2 10^2 + 1 = 101 Difference: 4 --- Counts --- MinusOneCount: 1 AddOneCount: 5
You program's output should match this format exactly
Below is the same output, but with comments, explaining what is happening - you should NOT include comments in your answer
1^2 + 1 = 2 //x starts at 1. x ^ 2 + 1 = 2 which is prime Difference: 1 //if we assume the initial previous x value was 0, then there is a difference of 1 between 0 and 1 2^2 - 1 = 3 Difference: 1 //last x value with a valid prime was 1 - so there's a difference of 1 between 1 and 2 2^2 + 1 = 5 Difference: 0 //0 difference between 2 and 2 4^2 + 1 = 17 Difference: 2 //2 difference between 2 and 4 6^2 + 1 = 37 Difference: 2 //2 difference between 4 and 6 10^2 + 1 = 101 Difference: 4 //4 difference between 6 and 10 --- Counts --- MinusOneCount: 1 //only 2^2 - 1 satisfied the "x ^ 2 - 1 = prime" equation AddOneCount: 5 //5 numbers satisfied "x ^ 2 + 1 = prime"
It's not required for the challenge, but you might like to try running your code for values of x into the millions, billions or beyond - you will likely want to optimise your code with approaches like a segmented sieve, wheel factorisation, Pollard's Rho algorithm, multithreding etc
Hints
Hints will be released at the start of each of the following days - e.g. the start of day 3 is 48 hours after the challenge starts
| Release Day | Hint |
|---|---|
| 2 | To determine whether a number is or isn't a prime, it might be useful to make use of the mod function/operator |
| 3 | We can naively loop from 2 to n and check if our number mod by any of them is equal to 0 - if it is, this means the number can be wholly divided, hence isn't prime - any number that is hence divisible by none of the numbers we tested therefore IS prime |
| 4 | To be more efficient, we can consider the symmetrical nature of factors - e.g. 24 / 4 = 6, just as 24 / 6 = 4. We therefore only have to check up to the floor (rounding down) of the square root of n, since going beyond this would mean we would be checking a larger value of a factor pair, which is redundant |
| 5 | It's also not required to check odd values of x above 1 - since any odd value squared will be odd, then if we either add or subtract 1, the result will become even - yet 2 is the only even number |