Interesting 2013

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

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 372036 =  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 -  2 - 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.

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 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.  

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 +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). 

 

Running/Exploring the Program 

bulletDownload  executable
bulletDownload source  (Note: the UComboV2 unit now resides in our library zip file of commonly used units.  Library file DFFVLIB13 or later is required to recompile this program )
bulletDownload current library file (DFFLibV15) to recompile.

 

Suggestions for Further Explorations

What is the smallest number that requires 6 squared terms to match its value? ( Or 2, 3, 4, or 5 terms?)
   

 

Original:  January 4, 2013

Modified:  May 15, 2018

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.