🧮

Primes

Week 8

Submit Answer Submit Code Solution See Hints See Solutions

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
3
4
5
8 2026