Lab: Disproof by Counterexample

CS 278 Lab: Disproof by Counterexample
Nowadays some proofs are generated by computer. In 1976, the four color theorem was the first
major theorem to be verified using a computer program.
In this assignment you will write a computer program to disproof a statement by finding a
counterexample. The statement is the following:
Every odd number from 3 onwards can be written as the sum of a prime number and
twice a square.
Some odd numbers (that are greater than or equal to 3) can be written as the sum of a prime
number and twice a square. For example, 3=3+2(02
), 5 = 3+2(12
), 7=5+2(12
), 9=7+2(12
),
11=3+2(22
), 13=5+2(22
), 15=7+2(2
2
), etc. But not all of the odd numbers can be written like that.
You need to write a program that would find the smallest counterexample, that is, the smallest
odd number (≥3) that cannot be written as the sum of a prime number and twice a square. (Hint:
The smallest counterexample lies between 1000 and 10000.)
One way to solve it is the following: generate a list of squares and check odd numbers to see if
the number minus twice a square is a prime.
You need to do the following:
(1) Write a method that takes a natural number n as a parameter and determines if n is a prime
number.
(2) Generate a list of the first 100 squares (from 0 to 99) and put them in an array of size 100.
(100 is enough because 1002=10000 and we know that there is a counterexample between 1000
and 10000.)
(3) For every odd number n starting from 3 check whether it can be written as the sum of twice a
square and a prime number. To do it, go through the squares in the squares array. For each
square, multiply it by 2 and subtract the result from the number n. Use your method from (1) to
check whether the difference is a prime number or not. If it is not a prime number then do the
same for the next square in the squares array. Otherwise, if the difference is prime, the number n
can be written in the desired form so you need to check the next odd number. Continue until you
find the smallest counterexample.
(4) Output the smallest counterexample which you find.
What to submit:
 Submit the source code of your program using Canvas.
 If you write your program in a programming language other than Java, then submit
instructions on how to compile and run your program on CS machines.