X2X4 Factoring Puzzle

[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

True or false?  X4 - X2 is a multiple of 12 for every integer value of X.     I ran across a similar question (but not the answer) in a newsgroup the other day.  I liked it so well that I decided to write a program.  

Background & Techniques

This isn't really much a  program, but it is an interesting example of the power of factoring in mathematical proofs.    Of course, a computer program can't really check every integer value of X, so we'll settle for checking as many as we can.  Just remember, we may experimentally prove falsehood for any proposition about "all" or "none" of the members of an infinite set, but we can never experimentally prove it to be true.  

For 32 bit integers (the normal Integer type), the maximum value is around 2 billion, so our X4 calculation should not get larger than this.  To ensure that, we'll user the Power function to set a stopping value for X at the 4th root of the maximum integer value.   We'll display an error message if we find a value of  X4 - X2 that is not a multiple of 12.  This loop only takes a few lines of code.  If we find a value of X which is not a multiple of 12 we have proven the proposition false.   If all values checked are multiples of 12, we haven't really proven anything (but it sure would make to suspect that it's true).     

Just for fun, we'll also check using 64 bit integers(Int64 type).  The primary difference here is that DO loop control variables must be 32 bit integers, so we'll use a WHILE loop to test all the values.

The most interesting part is the mathematical proof that the proposition is true.   The proof goes like this:  Factor the expression as X4-X2 as XX(X2-1) which factors further as XX(X-1)(X+1).  If this expression is to be divisible by 12, it must be divisible by 4 and by 3.  Let's see first if it is divisible by 3.  Notice that the number in question has 3 consecutive integers as factors (X-1), X, and (X+1).  For any 3 consecutive integers, one of them is divisible by 3.  I'll put a more rigorous proof of that in the Math Topics section, but for now, just try a few sets of 3 consecutive integers and you'll agree ([2,3,4], [13,14,15], etc.).  

So our number is divisible by 3, but is it divisible by 4?   Assume X is even, then the XX part of the expression is divisible by 4, right? ("even" means X=2Y  for some Y, so XX= (2Y) (2Y)=4YY which is a multiple of 4).  But what if X is odd?  Then the factors (X-1) and (X+1) are both even and, by the same reasoning, their product is a multiple of 4.  The original expression is divisible by 3 and by 4, so it is divisible by 12.  Q.E.D. as the mathematicians like to say, which stands for some Latin words that mean "That's what we set out to prove".  The last word of Q.E.D. is Demostrandum - you can look up the others.  (try "Q.E.D. abbreviation" in search)

Running/Exploring the Program

bulletBrowse source extract
bulletDownload source 
bulletDownload  executable  

Suggestions for further exploration

Can you prove that X5-X3 is a multiple of 24?

 

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