### Problem Description

This program checks some interesting properties claimed for the year 2013 in
a recent newspaper article. Specifically that 2013 is the first of three
consecutive years which each have exactly three prime factors. The second
claim is that 2013 is the smallest integer which requires 6 terms to represent
it as the sum and difference of squares.

### Background & Techniques

The article is available at
http://fullcomment.nationalpost.com/2012/12/31/john-chew-jonathan-kay-how-is-2013-interesting-let-us-count-the-ways/.

The claim:

*"2013 happens to be one of those numbers with
three prime factors (like 1,001, discussed above):
2013 = 3 x 11 x 61. ... 2014 is also a
year with three prime factors, because 2014 = 2 x 19
x 53. And get this: The same is true about 2015,
which equals 5 x 13 x 31.There won’t be another
three consecutive years that are the products of
three prime numbers until 2665 — more than half a
millennium from now!"
*

Well, except there are more sets even in this century
which meet the requirement (e.g. **2035 =
5 x 11 x 37**, **2036 = 2 x 2 x 509, 2037 =
3 x 7 x 97). ** If we modify the claim
to be "3 different prime factors" however, 2665 is
the next occurrence. The program included here
calculates solutions with or without the uniqueness
requirement.

The second claim:

*"Imagine a game whereby you make numbers by
adding or subtracting squares of prime numbers.
E.g., ***30 = (5 x 5) + (3 x 3) — (2 x 2)**. 2013 is the
smallest number that needs at least six squares to
make."

Not even close. There are actually 5 solutions with
4 terms (e.g. **
2013 = + 4 (2**^{2}) - 9 (3^{2}) + 169 (13^{2}) + 1849
(43^{2})). There are also 2 solutions with 5 terms, and
251olutions with 6 terms! The
program automatically displays the first 10
solutions of each size but it will take a couple of
minutes to examine all possible
solutions for the 6 term case. As a
matter of interest, I searched for the "real"
smallest number that requires 6 terms. If term
values are limited not to exceed the target number,
the smallest is **2074 = -** **
2**^{2 }-^{ }2^{2 }
- 3^{2 }+ 7^{2 }+ 16^{2} +
41^{2 } =^{ }- 4 - 4 - 9 + 49 +
361 + 1681. I suspect^{ }that if
term sizes are not limited, any given even number
may be expressed as the difference between the
squares of just two primes (which will always be
even unless one of the primes id 2) but I haven't
proved or found a proof of that.

**Non-programmers are welcome to read on, but may want to jump to bottom of
this page to download the executable program now.**

**Programmer's Notes:**

**This started out to be a simple program to post in the Beginners section
of the Delphi techniques category, but proved to be a ways beyond simple.
**

**First claim:**

For the first claim, we ended up using "**TPrimes**" class from **
Mathslib** unit to find factors of consecutive sets of years for the first
claim. The uniqueness checkbox was easy to test since TPrime's **
Getfactors** function returns factors in increasing order and if two adjacent
factors are identical, the solution rejected.

Without the seconds claim, the program could have remained in the Beginner
category, but the the second claim is a different story. Evaluating all
expressions made up of sums and differences of squares took some head scratching
to figure out. Here is what I came up with eventually:

**Second Claim - Generating terms:**

We will tackle the problem in two stages. First generate a set of
values to test along with their squares, and then insert all combinations of
plus and minus operators to apply to each value. I arbitrarily restricted
the range of squared values to the target year, the terms range from 1 to
sqrt(year). Library unit **UComboV2** has has an option to return
combinations (from 1 to 6 numbers) with repeats. So for example if we were
evaluating the **4** terms **[1,2,3,4]** looking for sets of **2** the
**10** squared "**combinations with repeats**" would be **(1,1), (1,4),
1,9), (1,16), (4,4), (4,9), (4,16), (9,9), (9,16), (16,16). **Now we need to
apply the 4 ways to apply 2 operations to 2 positions to each set giving **40**
expression to test. In practice, for **2013**, we generate the **
15,000,000** or so combinations of **6** terms, reduce term values by **1**
to create values ranging from **0** to **44** and then ignore **0**
values so we effectively evaluate expressions with** 1** through **5**
terms as well as those with all **6** non-zero terms without running separate
scans.

**Second Claim - Generating operations:**

For 6 terms, there are **2**^{6} or **64** arrangements
of + and - operations to try. The binary representations of values 0 to
63, effectively identify which operations to apply to which term, for
example for the 11th test, the binary representation is **001011** so we'll
apply operations **+,+,-,+,-,-** to the 6 squared terms in that order.
If looping** from 0 **to **63** with variable "**i**", then to
get the sign for a particular term, "**and**"** i **with a particular bit
position (**1,2,4,8,16,** or **32**) and assign **"+"** to the term if
the result is **0** and "**-**" if the result is **1**.

**Addendum **

**March 1, 2013: ** **Version 2,** posted today, corrects an
oversight in the original which reported solutions for Claim 2 based on sums of
squares of integers without requiring that the integers be prime. Although
the number of solutions of each length was reduced, it is still the case that
2013 does not required 6 terms, 4 terms are enough. I also reduced the
number of solutions by eliminating those with offsetting terms (adding **+p**^{2}
- p^{2} for any prime **p** to any 4 term solution formerly made
a new 6 term solution. Not anymore.

I also added a second search button for Case 2 to find the actual
smallest number requiring 6 terms. Starting with year2000 and restricting
term value to be less than the target year, 2074 is the
smallest year requiring 6 terms. With the same term size restriction, 15
is the smallest requiring 6 terms. (Use the program if you need help
finding the expression.
J)

**March 3, 2013:** It didn't take long to make a second version;
Version 2.1 has two significant changes.

I realized that the change to check only prime squares in Case 2 shoulf low
much faster searching. Instead of searching combinations of all numbers up
to the maximum term size, it was only necessary to check squares of primes.
Pre-selecting primes reduced search times by a factor of 100. The basic
Case 2 search now finds all 98 expressions evaluating 2013 in 0.2 seconds
compared to over 20 seconds in the previous version!

A seconds change tested what happens if maximum term value is allowed to
exceed the target year. It turns out that letting terms up to twice as
large the year being tested allows all years from 2013 to 10,000 be represented
with 5 or fewer terms! Also starting from year 1 with term size
restricted to year size, 11 is the smallest requiring 6 terms (4+4+4+4+4-9=11).
If we allow larger term sizes then there is a solution for year 2:
(9+9-4-4-4-4=2).

### Running/Exploring the Program