[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
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/.
"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 (22) - 9 (32) + 169 (132) + 1849 (432)). 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 = - 22 - 22 - 32 + 72 + 162 + 412 = - 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.
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.
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 26 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.
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 +p2 - p2 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).
Suggestions for Further Explorations
Copyright © 2000-2018, Gary Darby All rights reserved.