Fituvalu

 A set of tools for finding and managing 3x3 magic squares of squares.

Finding a 3x3 square of squares is an ongoing exploration for amateur mathemeticians. As of the time of this writing, nobody has found one with 8 perfect squares. Maybe you can find it! For more information, see an introduction to the subject, the pages on MultiMagie, and the Numberphile video that inspired me to write this software.

This project is for generating and managing 3x3 magic squares that contain perfect squares. It uses libgmp (GNU Multiprecision Arithmetic Library) for arbitrary-precision arithmetic on very large integers. Fituvalu is written to be easily parallelizable with GNU Parallel.

What does the name "Fituvalu" mean?
The word Fituvalu is a compound word of the Samoan words for "seven" (fitu) and "eight" (valu).

Quick Start

To get started you can try:

$ gen-middle-squares -o | gen-six-sq -i -t8 > data

Here we generate a sequence of perfect squares and feed them into gen-six-sq which uses 8 threads to do processing. We use the raw GMP numbers to save time by not having to do base 10 string to integer operations and vice-versa.

Eventually the numbers will get large enough that finding any new 3x3 magic squares with 6 or more perfect squares is a rare occurrence. To do more searching you can pass in another sequence of perfect squares, or move on to other strategies described later.

Introduction to the Tools

There are top level programs that we want to run primarily, and then there are helper programs. These programs are designed in the UNIX fashion; they are command-line programs with the output of one program being passed to the input of another via pipes.

There are four approaches used to create 3x3 magic squares.

• The first way uses co-primes to generate two progressions of perfect squares that intersect. e.g. they share a square in common. This method makes 3x3 magic squares with 5 or more perfect squares. If a program has the word morgenstern, or mn in it, it is referring to this method, which was developed by Lee Morgenstern.
• The second way creates 3x3 magic squares by combining two arithmetic progressions of three perfect squares. This method makes squares with five or more perfect squares.
• The third way creates 3x3 magic squares by providing an arithmetic progression of three perfect squares, and looping values over 2 other cells. This method makes squares with five or more perfect squares.
• The fourth way was already shown in the quick start, and creates 3x3 magic squares by providing a perfect square, and then creating all possible arithmetic progressions of three perfect squares from it, and then looping over values in 2 other cells. This method makes squares with six or more perfect squares.

Common Options

    --in-binary
    --out-binary

When using arbitrary-precision integers it is faster to deal with their raw formats. Many of these programs have an option for reading or writing the raw GMP formats rather than textual representations of numbers. When reading and writing billions of records, the time savings can be considerable. In using these options we avoid doing base 10 text to integer conversions and vice-versa.

Top-level Programs

program: morgenstern-search

Usage: morgenstern-search [--filter=NUM] [--out-binary] [--mem] FILE

This program generates 3x3 magic squares with 5 perfect squares in the hopes that a 6th or 7th perfect square will shows up.

The approach is create two arithmetic progressions of 3 perfect squares with a single square in common. The resulting magic squares can be large!

The standard input provides the parametric MN values -- two values per record to form the basis of the calculation. The small-mn-seq program provides these numbers.

The --filter=NUM option displays magic squares that contain NUM or more perfect squares.

The --mem option reads FILE into memory and treats the standard input differently. The idea here is that the stdin contains the row numbers that we're going to check. Simply put, the row number an index into FILE which is M,N, and then we get P,R as every record from 0 to the record number. This option avoids the generation of duplicate magic squares, and saves a lot of time.

When -i used with --mem, the file that is passed on the standard input needs to be encoded with convert-binary-gmp-records-to-text -i --ull.

There are 8 different types of squares that this program generates. To see what each configuration looks like you can use the --show=TYPE option.

program: morgenstern-search-mnpr

Usage: morgenstern-search-mnpr [OPTION...] [FILE]

Like the previous program, but it takes in records of MNPR co-prime pairs instead of M, N (and then looping over the combinations). Two of the more useful options are: --filter and --threads.

program: scissor-square

Usage: scissor-square [--in-binary] [--out-binary] N1, N2, N3,
  or:  scissor-square [--in-binary] [--out-binary] FILE

Try to create a 3x3 of magic square from two progressions of three squares that have the same difference between the squares, or the differences must be divisible. This program tries create a magic square with the following layouts:

        +------+------+------+     +------+------+------+
        |      |  X3  |  N2  |     |  X2  |      |  N3  |
        +------+------+------+     +------+------+------+
        |  N3  |      |  X1  | and |      |  N2  |  X1  |
        +------+------+------+     +------+------+------+
        |  X2  |  N1  |      |     |  N1  |  X3  |      |
        +------+------+------+     +------+------+------+

The first progression is given as the arguments N1, N2, N3. The second progression is passed in on the standard input. Alternatively you can try the progressions on the standard input with a set of progressions by passing in FILE.

The three values must be perfect squares, separated by a comma and terminated by a newline, and must be in ascending order. This program also generates 3x3 nearly-magic squares.

program: gen-six-sq

Usage: gen-six-sq [OPTION...] [--generate="6:1,6:4,etc"] [--threads=NUM] [FILE]

Generate 3x3 magic squares with 6 perfect squares or more by generating arithmetic progressions of three perfect squares from a given set of perfect squares in FILE. For each progression of three squares we search for magic squares of the following types: 6:1, 6:4, 6:5, 6:7, 6:8, 6:10, 6:12, 6:15, and 6:16. To see the layout of these types, use type-square -s 6:1.

We also inadvertently find magic squares of the forms: 6:2, 6:11, 6:13, and 6:14. Suitable values for --generate are: 6:1, 6:4, 6:5, 6:7, 6:8, 6:10, 6:12, 6:15, and 6:16. When FILE is not specified or it is `-', the squares are read from the standard input.

program: search-61

Usage: search-61 [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:1 given a FILE containing center values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:1 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   |   | X |   |   |   | C |
            +---+---+---+   +---+---+---+
            |   | X | X |   |   | B | E |
            +---+---+---+   +---+---+---+
            | X | X | X |   | A | D | Z |
            +---+---+---+   +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of 2*(B-A) below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE.

program: search-62

Usage: search-62 [--multiply=PERC] [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:2 given a FILE containing top right values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:2 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   | X | X |   |   | Z | B |
            +---+---+---+   +---+---+---+
            | X |   | X |   | C |   | E |
            +---+---+---+   +---+---+---+
            | X | X |   |   | D | A |   |
            +---+---+---+   +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of B-A below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE. The search in this square type is not exhaustive, and the --multiply option helps to limit the search space by controlling the size of D by multiplying C by a certain percentage.

program: search-63

Usage: search-63 [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:3 given a FILE containing center values (n). When FILE is not provided, it is read from the standard input. Center values must not be perfect squares. Magic squares of type 6:3 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            | X | X | X |   | A | C | E |
            +---+---+---+   +---+---+---+
            |   |   |   |   |   | n |   |
            +---+---+---+   +---+---+---+
            | X | X | X |   | F | D | B |
            +---+---+---+   +---+---+---+

Find three number arithmetic progressions that have non-square n at their center. The progressions are A,n,B, C,n,D, and E,n,F. Try every combination of three progressions in every position to find a magic square. There is also a --3sq option to make the program read in arithmetic progressions instead of center values. There is also a --twos option to try every combination of two arithmetic progressions and then calculating the rest to see if it makes a 6:3 square.

program: search-64

Usage: search-64 [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:4 given a FILE containing center values (B). When FILE is not provided, it is read from the standard input. Center values must be perfect squares. This program generates magic squares with at most two numbers being negative. Magic squares of type 6:4 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   | X |   |   |   | Z |   |
            +---+---+---+   +---+---+---+
            | X | X | X |   | A | B | C |
            +---+---+---+   +---+---+---+
            | X |   | X |   | D |   | E |
            +---+---+---+   +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of B-A below D. Z is a square that shakes out. There also a --3sq option to have the program get A,B,C from FILE.

program: search-65

Usage: search-65 [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:5 given a FILE containing center values (B). When FILE is not provided, it is read from the standard input. This program generates magic squares with at most two numbers being negative. Magic squares of type 6:5 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   |   |   |   |   |   |   |
            +---+---+---+   +---+---+---+
            | X | X | X |   | A | B | C |
            +---+---+---+   +---+---+---+
            | X | X | X |   | D | Z | E |
            +---+---+---+   +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of B-A below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE.

program: search-66

Usage: search-66 [--multiply=PERC] [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:6 given a FILE containing bottom right values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:6 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   | X |   |   |   | A |   |
            +---+---+---+   +---+---+---+
            | X | X | X |   | C | Z | E |
            +---+---+---+   +---+---+---+
            |   | X | X |   |   | D | B |
            +---+---+---+   +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards checking for a new square E at a distance of 2*(B-A) below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE. The search in this square type is not exhaustive, and the --multiply option helps to limit the search space by controlling the size of D by multiplying C by a certain percentage.

program: search-67

Usage: search-67 [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:7 given a FILE containing center values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:7 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   |   | X |   |   |   | A |
            +---+---+---+   +---+---+---+
            | X | X | X |   | E | B | Z |
            +---+---+---+   +---+---+---+
            | X |   | X |   | C |   | D |
            +---+---+---+   +---+---+---+
                            +---+---+---+
                            |   |   | C |
                            +---+---+---+
                            | D | B | Z |
                            +---+---+---+
                            | A |   | E |
                            +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of B-A below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE.

program: search-68

Usage: search-68 [--multiply=PERC] [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:8 given a FILE containing top right values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:8 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   |   | X |   |   |   | B |
            +---+---+---+   +---+---+---+
            | X | X |   |   | A | D |   |
            +---+---+---+   +---+---+---+
            | X | X | X |   | Z | C | E |
            +---+---+---+   +---+---+---+
                            +---+---+---+
                            |   |   | B |
                            +---+---+---+
                            | C | E |   |
                            +---+---+---+
                            | Z | A | D |
                            +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of B-A below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE. The search in this square type is not exhaustive, and the --multiply option helps to limit the search space by controlling the size of D by multiplying C by a certain percentage.

program: search-69

Usage: search-69 [--multiply=PERC] [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:9 given a FILE containing top right values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:9 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   |   | X |   |   |   | B |
            +---+---+---+   +---+---+---+
            | X |   | X |   | A |   | D |
            +---+---+---+   +---+---+---+
            | X | X | X |   | E | C | Z |
            +---+---+---+   +---+---+---+
                            +---+---+---+
                            |   |   | B |
                            +---+---+---+
                            | C |   | E |
                            +---+---+---+
                            | D | A | Z |
                            +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of B-A below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE. The search in this square type is not exhaustive, and the --multiply option helps to limit the search space by controlling the size of D by multiplying C by a certain percentage.

program: search-610

Usage: search-610 [--multiply=PERC] [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:10 given a FILE containing top right values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:10 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   |   | X |   |   |   | B |
            +---+---+---+   +---+---+---+
            | X | X | X |   | A | D | Z |
            +---+---+---+   +---+---+---+
            |   | X | X |   |   | C | E |
            +---+---+---+   +---+---+---+
                            +---+---+---+
                            |   |   | B |
                            +---+---+---+
                            | C | E | Z |
                            +---+---+---+
                            |   | A | D |
                            +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of B-A below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE. The search in this square type is not exhaustive, and the --multiply option helps to limit the search space by controlling the size of D by multiplying C by a certain percentage.

program: search-611

Usage: search-611 [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:11 given a FILE containing center values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:11 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   |   | X |   |   |   | A |
            +---+---+---+   +---+---+---+
            | X | X | X |   | Z | B | D |
            +---+---+---+   +---+---+---+
            | X | X |   |   | C | E |   |
            +---+---+---+   +---+---+---+
                            +---+---+---+
                            |   |   | C |
                            +---+---+---+
                            | Z | B | E |
                            +---+---+---+
                            | A | D |   |
                            +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of 2*(B-A) below D. Z is a suare that shakes out. There is also a --3sq option to have the program get A,B,C from FILE.

program: search-612

Usage: search-612 [--multiply=PERC] [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:12 given a FILE containing bottom right values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:12 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   | X |   |   |   | A |   |
            +---+---+---+   +---+---+---+
            | X |   | X |   | C |   | E |
            +---+---+---+   +---+---+---+
            | X | X | X |   | Z | D | B |
            +---+---+---+   +---+---+---+
                            +---+---+---+
                            |   | C |   |
                            +---+---+---+
                            | A |   | D |
                            +---+---+---+
                            | Z | E | B |
                            +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of 2*(B-A) below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE. The search in this square type is not exhaustive, and the --multiply option helps to limit the search space by controlling the size of D by multiplying C by a certain percentage.

program: search-613

Usage: search-613 [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:13 given a FILE containing center values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:13 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            |   | X | X |   |   | Z | A |
            +---+---+---+   +---+---+---+
            | X | X |   |   | E | B |   |
            +---+---+---+   +---+---+---+
            | X |   | X |   | C |   | D |
            +---+---+---+   +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of B-A below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE.

program: search-614

Usage: search-614 [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:14 given a FILE containing center values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:14 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            | X |   | X |   | D |   | A |
            +---+---+---+   +---+---+---+
            |   | X | X |   |   | B | E |
            +---+---+---+   +---+---+---+
            | X |   | X |   | C |   | Z |
            +---+---+---+   +---+---+---+
                            +---+---+---+
                            | D |   | C |
                            +---+---+---+
                            |   | B | E |
                            +---+---+---+
                            | A |   | Z |
                            +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of B-A below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE.

program: search-615

Usage: search-615 [--multiply=PERC] [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:15 given a FILE containing top right values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:15 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            | X |   | X |   | Z |   | B |
            +---+---+---+   +---+---+---+
            | X |   | X |   | A |   | D |
            +---+---+---+   +---+---+---+
            | X | X |   |   | E | C |   |
            +---+---+---+   +---+---+---+
                            +---+---+---+
                            | Z |   | B |
                            +---+---+---+
                            | C |   | E |
                            +---+---+---+
                            | D | A |   |
                            +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of B-a below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE. The search in this square type is not exhaustive, and the --multiply option helps to limit the search space by controlling the size of D by multiplying C by a certain percentage.

program: search-616

Usage: search-616 [--multiply=PERC] [--threads=NUM] [FILE]

Find 3x3 magic squares of the type 6:16 given a FILE containing bottom right values (B). When FILE is not provided, it is read from the standard input. Magic squares of type 6:16 have the following layout of squares vs non-squares:

            +---+---+---+   +---+---+---+
            | X | X | X |   | Z | A | D |
            +---+---+---+   +---+---+---+
            | X |   |   |   | C |   |   |
            +---+---+---+   +---+---+---+
            | X |   | X |   | E |   | B |
            +---+---+---+   +---+---+---+

A,B,C is a three square progression where B comes from FILE. Start iterating D downwards, checking for a new square E at a distance of 2*(B-A) below D. Z is a square that shakes out. There is also a --3sq option to have the program get A,B,C from FILE. The search in this square type is not exhaustive, and the --multiply option helps to limit the search space by controlling the size of D by multiplying C by a certain percentage.

Helper Programs

program: search-progressions

Usage: search-progressions [--in-binary] [--out-binary] [--segment=N/M] [--threads=NUM] [CENTER]

Find arithmetic progressions consisting of two squares around a given CENTER. When CENTER is not provided, it is read from the standard input. The --threads option is used to spread the work across NUM threads, whie the --segment option is used in a parallelization situation to distribute the work across many computers. Some top-level programs can take three square progressions as input and this program can be used to make them.

program: reduce-square

Usage: reduce-square [OPTION...]

Determine what the lowest value is for the given magic square and have it still retain all of the perfect squares.

program: rotate-square

Usage: rotate-square [OPTION...]

Given a magic square, show the rotations and reflections of it.

program: unique-squares

Usage: unique-squares [OPTION...] --sort

Given a set of magic squares, only show the unique ones. E.g. take into account all rotations, reflections and reductions. The --sort option sorts by the magic number.

program: type-square

Usage: type-square [--filter=NUM_SQUARES:TYPE] [---no-show-squares]

Given a magic square determine which of the configurations it is. Using the --filter option, this program filters a given set of magic squares such that they only have the given type. It displays records of the form: 5:12 (e.g. this magic square has 5 perfect squares, laid out in type 12.)

program: sort-square

Usage: sort-square [--prefix=NAME]

Given a magic square, put it in a file called fives, sixes, sevens etc. according to how many perfect squares it contains.

program: odd-square

Usage: odd-square [--even] [--mixed] [--doubly-even]

Given a magic square, show it if it's comprised of odd numbers. The --even option shows even instead of odd, --doubly-even shows the squares where all the numbers are divisible by 4, and --mixed has both odd numbers and even numbers.

program: number-square

Usage: number-square [--min] [--max] [--filter]

Given a 3x3 magic square on the standard input, output the magic number. Only do so if the square is a magic square. Use --min and --max to display the smallest and largest values in the square. Use the --filter=NUM option to show only squares that have NUM as a magic number.

program: check-square

Usage: check-square [OPTION...]

Given a set of 9 numbers on the standard input, check if it's a magic square. Only display it if it is.

program: display-square

Usage: display-square [--number-line] [--no-magic-number] [--show-sums] [--simple]

Pretty-print a 3x3 square and put the values inside the cells. This program will also display the sums of the rows and columns and diagonals when the square is not magic.

program: sq-seq [--out-binary]

Usage: sq-seq [OPTION...] FIRST
  or:  sq-seq [OPTION...] FIRST LAST
  or:  sq-seq [OPTION...] FIRST INCREMENT LAST

Generate a sequence of perfect squares. This program works like seq from GNU Coreutils, but loops over squares. It can be given an increment to loop over every Nth square in the sequence.

program: mn-seq

Usage: mn-seq MAX

Generates a sequence of numbers that has the form: M > N > 0, where M and N are coprime, and with one being even and the other one odd. The output of this program is suitable for input into the morgenstern-search program and find-3sq-progressions-mn programs.

program: mn-expand

Usage: mn-expand [FILE]

Create MNPR records by iterating over MN records provided by mn-seq.

program: mine-3sq-progressions

Usage: mine-3sq-progressions [--show-diff] [--in-binary] [--show-root] [--show-sum]

Accept 3x3 magic squares on the standard input and output any arithmetic progressions that are formed by three perfect squares. The idea here is that we are mining the results of our previously generated magic squares for progressions that can be used to make new magic squares.

program: find-3sq-progressions-sq

Usage: find-3sq-progressions-sq  [--no-root] [--gcd] [SQUARE]

Generate three square progressions by supplying a perfect SQUARE. The --no-root prevents displaying the square root of the third number, and the --gcd option only shows three square progressions that have a greatest common divisor of 1.

program: find-3sq-progressions-mn

Usage: find-3sq-progressions-mn [--in-binary] [--no-root] [--out-binary]

Given a pair of MN coprimes on the standard input, generate three equidistant perfect squares.

How do you use all of this?

One way is to use coprimes to generate magic squares.

$ mn-seq 3500 > /tmp/indata
$ seq 0 `cat /tmp/indata | wc -l` > /tmp/records
$ split -d -n r/4 --suffix-length=3 /tmp/records /tmp/records-
$ seq -f "%03g" 0 3 | parallel -S 4/: 'cat /tmp/records-{} | morgenstern-search /tmp/indata --int -f 6 --mem -t4' > data

In the first step, we make our data file. And in the second step we generate a sequence of row numbers -- it's a bit fancy with the "`" backticks, but it is just finding the number of lines in the file. In the third step we split the records into 4 files and it says r/6 to cause the row numbers to be round-robined, so that high and low record numbers (indices) are evenly distributed in our files. Now, in the fourth step there's a lot going on. We're running seq here and it's one for each of our datafiles (e.g. /tmp/records-000, /tmp/records-001 and so on). Parallel is running 4 processes on this machine (-S f/:), and there are four threads per process (-t4). We have passed in the whole data file here (/tmp/indata because we want to process portions of it, but we're not quite sure yet which portions.

The --mem option causes the program to read in the whole data file into memory (/tmp/indata) and treat the standard input as row numbers (indices), which controls the processing of rows of the data file. The -f6 option only displays magic squares that have at least 6 perfect squares. The --int option speeds up things a bit by using integer processing on M, N, P, R values (taking advantage of the fact that our starting numbers are always less than 2^32-1.)

With the --mem option, the program gets its first M,N pair as identified by the row number (as an index from the standard input_ into /tmp/indata, and then we get our P,R pair as every other M,N pair. Because they're all in memory we can whip through them fast.

The disadvantage of this method is that our whole data file has to be in RAM, and many times if we're doing multple processes like we are here.

With GNU Parallel you can split the work across hundreds of machines. For example -S 3/192.168.1.101 would make three processes start on a remote system. But the data files and binaries have to be copied over first.

Do you want to extend your search? Here's how! In this case we'll be extending our search from 3500 to 5000.

$ mn-seq 5000 > /tmp/5000

we want our row numbers to start after a certain number of rows (after the rows that belong to 3500):

$ mn-seq 3500 | wc -l
2481760
$ cat /tmp/5000 | wc -l
5065076
$ seq 2481760 5065076 > /tmp/records
$ split -d -n r/4 --suffix-length=3 /tmp/records /tmp/records-
$ seq -f "%03g" 0 3 | parallel -S 4/: 'cat /tmp/records-{} | morgenstern-search /tmp/5000 --int -f 6 --mem -t4' > moredata

You can extend your search in this way until your RAM is exhausted. At this point you'll have to omit the --mem option and take the speed hit. The precise details of this is left as an exercise to the reader.

There is also morgenstern-search-mnpr, where all four M,N,P,R values are passed in on every record.

$ mn-seq-small 3500 | mn-expand --int | morgenstern-search-mnpr --int -f6 -t8 | check-square > data

How do I build these programs?

You'll need a GNU/Linux system, with the normal sort of tools installed: GNU Bash, GNU GCC, GNU make, GNU automake, GNU autoconf, GNU libtool, and GNU Coreutils.

Also install libgmp (GNU Multiprecision Arithmetic Library.)

All of these packages are available for installation in the package management system of your GNU/Linux distribution.

If you are using Fedora you would type something like this:

    $ dnf install automake autoconf make gcc libtool gmp-devel

(Bash and Coreutils are already installed by default)

    $ git clone http://sv.gnu.org/p/fituvalu/fituvalu.git
    $ cd fituvalu
    $ ./configure
    $ make
    $ su -c 'make install'

Final Words

I wish you good luck in your search for the 3x3 magic square of squares! If you use this software to find anything interesting, please let me know! You can use the Magic Square Checker if you are unsure.

Or if you intend on running this software on a large number of machines in a serious computational effort, also please let me know. Maybe I can help!

If you have any questions about these tools (or any of the others included in this software), you can contact me by opening a bug on the project page for Fituvalu, or mailing the address included with the software.

This page is licensed under the terms of the Creative Commons Attribution ShareAlike 4.0 Intl License.