The Magic Square of Substraction: A 'Classic Discovery'

NATURAL NUMBERS

exploring the undesigned
intelligence of the numberverse

Part 1: The Magic Square of Substraction: A 'Classic Discovery'

First published March 3
Revised March 12, 2008

Read about Fermat's factorization method.

Part 2
The Magic Square of Addition: A Deterministic Algorithm to test compositeness.

I recently "found" two perfect square rules that were formative in formulating this algorithm. They are discussed in:
Q-Paired Primes: Two Interesting Rules.

It's sometimes worth stating the obvious in case it gets overlooked. The difference between any two adjacent perfect squares is always an odd number. The difference in the interval between two adjacent perfect squares is always 2. If you put these two basic facts together, you see that through subtraction of perfect squares you will be able to derive every odd number in the number line except for 1.

If you're not sure about this, simply look at the lists of perfect squares on this site. These lists contain three columns of data: the root of the perfect square, the perfect square itself, and the interval between the perfect square and the previous one. This interval is the difference or product of perfect square subtraction.

In number theory, the fundamental theorem of arithmetic (or unique-prime-factorization theorem) states that every natural number greater than 1 can be written as a unique product of prime numbers.

So, for example, the unique prime factorization of 999 is: 3 * 3 * 3 * 37.

We can now state a "fundamental theorem of perfect square subtraction" such that every odd natural number is the subtractive product of two, and only two, adjacent perfect squares.

You will see that to obtain through subtraction, say, 999, you will need to subtract some relatively large perfect squares. The unique perfect square subtraction that produces 999 is: 249001- 250000.

Incidentally, the formula for deriving any odd number with perfect square subtraction can be expressed this way:

N = (Int(N / 2) +1) ^ 2 - Int(N / 2) ^ 2

In some recent research, I spent a lot of time looking at the behavior of fixed values added to perfect squares - in particular the occurrence of primes at regular paired intervals. You can read about it in the following columns:

Q-Paired Primes: The Investigation Continues...

What are Biquadratic Paired Primes?

While this work produced some interesting results, I had been overlooking a far more fantastic and fertile field of investigation: subtracting fixed values from perfect squares.

A square with curves...

Using the algorithm with a fixed number of rows and separating the minus-square multiples and nonmultiples produce these distinctive distributions.

Non-minus-square-multiples* distribution for the first 1000 perfect squares

Minus-square-multiples* distribution for the first 1000 perfect squares

*Numbers that are evenly divisible by their respective minus-squares (see main article).

Download XLS file (642KB)
Workbook contains two worksheets and no macro code.

2500 Years Ago, the Greeks discovered a method for determining the longest measure that equally divides two line lengths - a method that uses only subtraction...

Named after Euclid, who first recorded it, the Euclidean algorithm is one of the oldest and greatest algorithms known to mathematics. Its simplicity and effectiveness still set a standard for modern mathematicians.

The subject of this topic is not the Euclidean algorithm - you can read about it here - although it is certainly an inspiration for this discussion about a deceptively simple but powerful method for generating composite numbers using the subtraction of perfect squares. The method is also a means for determining primality by elimination: a technique that does not require trial division or modular arithmetic.

The Basic Idea

The initial idea comes from the following observation: The number that immediately precedes a perfect square is never prime with the single exception of 4 - 1 = 3.

	Perfect Square	Perfect Square - 1
	4 (2 * 2)	3
	9 (3 * 3)	8 (2 * 2 * 2)
	16 (4 * 4)	15 (3 * 5)
	25 (5 * 5)	24 (2 * 2 * 2 * 3)
	36 (6 * 6)	35 (5 * 7)
	49 (7 * 7)	48 (2 * 2 * 2 * 2 * 3)
	64 (8 * 8)	63 (3 * 3 * 7)
	81 (9 * 9)	80 (2 * 2 * 2 * 2 * 5)
	100 (10 * 19)	99 (3 * 3 * 11)

Now 1 is 1, but it's also the first perfect square: 1 * 1 = 1, so is it the oneness of 1 that ensures that PS -1 is always always a composite number - or is it because of its property of squareness...?

It seemed possible that if this rule held for PS-1, it might hold for PS-N, where N is another perfect square - just maybe....

The huge surprise is that the rule holds true for every perfect square. In every case - with the important and irregular exception of the first subtraction (the first row in the table), which we will talk about in a moment - the numbers produced by subtraction of perfect squares are composite numbers:

PS	PS-1	PS	PS-4	PS	PS-9	PS	PS-16	PS	P-25	PS	PS-36	PS	PS-49
4	3	9	5	16	7	25	9	36	11	49	13	64	15
9	8	16	12	25	16	36	20	49	24	64	28	81	32
16	15	25	21	36	27	49	33	64	39	81	45	100	51
25	24	36	32	49	40	64	48	81	56	100	64	121	72
36	35	49	45	64	55	81	65	100	75	121	85	144	95
49	48	64	60	81	72	100	84	121	96	144	108	169	120
64	63	81	77	100	91	121	105	144	119	169	133	196	147
81	80	100	96	121	112	144	128	169	144	196	160	225	176
100	99	121	117	144	135	169	153	196	171	225	189	256	207

So, to make sure you understand what this table shows, you're looking at a matrix of perfect squares (and the results of subtracting them). The perfect squares are increasing by one square in every row and in every other column. The columns are one perfect square less than the corresponding squares in the rows - and all we're doing is simply subtracting them and showing the result in the alternating columns.

For clarity, let's refer to the perfect squares that are being subtracted as "minus-squares" - so if 16 - 9 = 7 and 25 - 9 = 16, the minus-square is 9 in both cases:

PS PS-9

16 7

25 16

Now notice that the perfect squares in the 1st, 3rd, 5th, 7th, 9th, and 11th columns are shifting up each time by one square. That's simply because the minus-square cannot be greater than the perfect square. So when subtracting 4, the first perfect square to be considered is 9; when subtracting 9, the first perfect square to be considered is 16, and so on.

The first row

The first row is created by the first subtraction: the minus-square is one square smaller than the perfect square: 4-1, 9-4, 16-9, 25-16, 36-25, 49-36, 64-49, and 81-64. Let's look a little harder at what's happening in the first-row results:

It actually looks pretty simple: the results are increasing by 2 for each minus-square. That happens to be exactly the difference in the increase between perfect squares - more about what this difference means in this article.

It turns out that 9 - 4 = 5 is a prime number of course. In other words, this is a single exception (like 4 - 1 = 3) to the otherwise compositeness of all perfect squares minus 4. Similarly, 36 - 25 = 11 and 64 - 49 = 12 are also exceptions to the otherwise uniform compositeness of their respective columns.

However 25 - 26 = 9 and 81 - 64 = 15 are definitely composite. There are no exceptions to compositeness in these columns.

If we were hoping to find some kind of transparent pattern to the exceptions we will be disappointed. But we should not give up too easily.... Because it so happens that this table has a very nice property - the property of repetition or reoccurrence....

PS	PS-1	PS	PS-4	PS	PS-9	PS	PS-16	PS	P-25	PS	PS-36	PS	PS-49
4	3	9	5	16	7	25	9	36	11	49	13	64	15
9	8	16	12	25	16	36	20	49	24	64	28	81	32
16	15	25	21	36	27	49	33	64	39	81	45	100	51

Prime numbers can only occur once in this table, but composites can occur once, twice, or more than two times. So in this tiny sample, 9 cannot be a prime because it has already occurred in the table as a perfect square (the product of 3 * 3). 15 cannot be a prime because it has already occurred in the table as the composite product of a perfect square subtraction (16 - 1).

Thus we have a two-part test for primality:

A positive requirement: The number must occur in the first perfect square subtraction (the first row).
A negative requirement: The number cannot already have occurred, either as as perfect square or as the product of perfect square subtraction.

That's it in a nutshell. You now have a complete algorithm for determining compositeness and primality that requires neither division nor exponentiation.

Some open questions

One big open question is how many rows does the table need to have to ensure that the compositeness of the first-row nonprimes can be proved by prior occurrence. This is important as it determines the efficiency of the algorithm for proving primes.

The number of rows needed to prove composites progressively increases, from about 20 rows for primes under 1000, to about 50 rows for primes under 5000, to about 100 rows for primes under 10000. But this is very approximate, and does not take into account that the row depth requirement actually decreases almost geometrically after the first few columns. This will be a subject of the next column on this topic.

However, if your aim is to safely generate the largest number of composites, you can go as deep as you can in terms of number of rows. You can be assured that every number generated will be composite except those that appear in the very first row. The arithmetic operations are so simple that, even though the numbers rapidly become very large as the row depth increases, the performance impact is not even a consideration.

There are a few complexities that I didn't mention. All composite numbers appear unless they are alternate multiples of 2 - for example: 6, 10, and 14 do not. Multiples of 4 do appear - for example, 8, 12, and 16. The reason for this is not that simple to explain and may be related to the concept of quadratic reciprocity. This needs to be researched.

Another feature of the table are the factor "rays" (or curves) that emanate from the top left corner and traverse without breaks through the table at various angles. Shown in orange below, these are numbers that are evenly divisible by their respective minus-squares - thus, 9 is a factor of 27, 72 and 135. Notice that the interval between multiples of a perfect square increase by row (or square) with each successive column (or minus-square).

PS	PS-1	PS	PS-4	PS	PS-9	PS	PS-16	PS	P-25	PS	PS-36	PS	PS-49
4	3	9	5	16	7	25	9	36	11	49	13	64	15
9	8	16	12	25	16	36	20	49	24	64	28	81	32
16	15	25	21	36	27	49	33	64	39	81	45	100	51
25	24	36	32	49	40	64	48	81	56	100	64	121	72
36	35	49	45	64	55	81	65	100	75	121	85	144	95
49	48	64	60	81	72	100	84	121	96	144	108	169	120
64	63	81	77	100	91	121	105	144	119	169	133	196	147
81	80	100	96	121	112	144	128	169	144	196	160	225	176
100	99	121	117	144	135	169	153	196	171	225	189	256	207

It appears that, for the odd minus-square columns, a number that is not a multiple of the minus-square is always coprime, or relatively prime, to the minus-square. This needs to be verified.

Well, all that remains is to make the code available to demonstrate these findings... Enjoy!

VBA Code for Excel:

Option Explicit

Private narray() As Long

Private Sub Workbook_Open()
    Rotations
End Sub

Private Sub Rotations()
    Dim n As Long
    Dim nc As Long
    Dim psquare As Long
    Dim minus As Long, pminus As Long
    Dim square As Integer
    Dim col As Integer, ct As Integer, row As Integer
    Dim blprime As Boolean

With Worksheets(1)
        .Cells.ClearContents
        .Cells.ClearFormats
        col = 0

For minus = 1 To 250

pminus = minus ^ 2
            ReDim Preserve narray(nc)
            narray(nc) = pminus
            col = col + 1
            .Cells(1, col).Value = pminus
            .Cells(1, col).Interior.Color = vbYellow
            row = 1
            ct = 1
            nc = nc + 1

'           For square = 1 To 1000             'Try this for a larger set of results
            For square = minus To minus + 100

psquare = square ^ 2

If psquare - pminus > 0 Then

blprime = False
                    ReDim Preserve narray(nc)
                    narray(nc) = n
                    n = psquare - pminus
                    row = row + 1
                    .Cells(row, col).Value = Trim$(n)

If ModOp(n, pminus) = 0 Then
                        .Cells(row, col).Font.Color = vbBlue
                    End If

If row = 2 Then
                        If IsUnique(n) Then
                            .Cells(row, col).Font.Color = vbRed
                            .Cells(row, col).Font.Bold = True
                            blprime = True
                        End If
                    End If

'Uncomment this code and function below to certify the results are correct
'                    If blprime = False Then
'                        If IsPrime(n) Then
'                            .Cells(row, col).Interior.Color = vbGreen
'                        End If
'                    ElseIf blprime = True Then
'                        If IsPrime(n) = False Then
'                            .Cells(row, col).Interior.Color = vbMagenta
'                        End If
'                    End If
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

nc = nc + 1
                End If

DoEvents
            Next

DoEvents
        Next

End With
End Sub

Private Function IsUnique(n As Long) As Boolean
    Dim na As Long

For na = 0 To UBound(narray)        'An optimized check could be about (UBound(narray) * 0.7)
        If n = narray(na) Then
            IsUnique = False
            Exit Function
        End If
    Next
    IsUnique = True
End Function

'Uncomment this function and code above to certify the results are correct
'Private Function IsPrime(pt As Variant) As Boolean
'    Dim ff As Variant
'
'    If pt > 2 Then
'        If ModOp(pt, 2) = 0 Then
'            IsPrime = False
'            Exit Function
'        End If
'        For ff = 3 To Sqr(pt) Step 2
'            If ModOp(pt, ff) = 0 Then
'                IsPrime = False
'                Exit Function
'            End If
'            DoEvents
'        Next
'    End If
'
'    IsPrime = True
'
'End Function
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

Private Function ModOp(Value1 As Variant, Value2 As Variant) As Double
    Dim vratio As Variant

vratio = CDec(Value1) / CDec(Value2)
    ModOp = CDec(vratio) - Int(vratio)

End Function

All you have to do is to select everything in the text area above and drag or copy it to the Excel Visual Basic Editor, dropping it into the VBAProject ThisWookbook object. Save and exit the file. Then reopen it, and the code will autostart providing that your macro security is not high or very high.

Part 2: A Deterministic Test for Compositeness Using Perfect Squares...

Michael M. Ross