The Nazca Primes

-
The Nazca Lines are considered one of the most intriguing mysteries of ancient societies. They consist of several drawings of gigantic images, mostly animals and images resembling humans, created by the Nazca culture, around 650 AD. The images are so big that they only make sense when observed from extremely high altitudes:

“The Astronaut”, in the Nazca Desert (source: Bing Images)

The purpose of the hundreds of such drawings remains a mystery. Scientists and anthropologists continue their studies and excavations in order to solve this mystery. But in August 2007, a group of Israeli and Iranian anthropologists made a very surreal discovery when excavating the caves of the Nazca Desert in southern Peru.

Excavations of the caves in the Nazca Desert, August 2007 (source: Bing Images)
Amongst several new (albeit small) drawings found in some of the caves in that region, one particular drawing caught the eye of the researches: first, there was a sequence of a 3x3 numbers written in one stone, and the sequence was:
With the following text right below the numbers:
“ويجب أن يكون هناك دائما يعبي. الأرقام، ومجموع الأرقام. ويجب أن يكون هناك دائما يعبي. الأرقام. مجموع الأرقام. في كل الاتجاهات. قد وتتكون من الكون بالضبط 482139064 تركيبات. يعبي. يجب أن تكون دائما!”
Whose translation to English is the following:
“And there shall always be primes. The numbers, the sum of the numbers. And there shall always be primes. The numbers. The sum of the numbers. In all directions. And may the universe be composed of exactly 482,139,064 combinations. Primes. They shall always be!”
For the past several years scientists have been trying to decipher the meaning of these numbers as well as the text associated with them. Earlier this year a new article entitled “The Prime Stone – Unveiling the Meaning of the Nazca Numbers” (by Ioran Olecram) was published in the journal Matematica which provides a fascinating explanation to this particular drawing. First, the 3x3 matrix of course consists of prime numbers only (this was known before). Moreover, if you add up the elements of any row, any column or any diagonal, the result… is also a prime number! For instance, add up the second row and the resulting number would be: 5+13+19 = 37, which is a prime number! Now, sum up the elements in the diagonal: 3+13+7 = 23, another prime number! It is unclear how such an old and obscure civilization would have such an advanced knowledge of mathematics. It is unclear also how they managed to put together not only the matrix of these numbers, but also how they knew the properties of prime numbers, since it is believed that such concepts were only known and developed in far-away parts of the planet. The final mystery to be solved was the phrase:
“And may the universe be composed of exactly 482,139,064 combinations”
What is the meaning of the number 482,139,064? It turns out that, if you take all the prime numbers from 0 to 100 (which were the basic numbers used at that time) and you try to create 3x3 matrix of such prime numbers in a way to honor the properties that:
Prime Stone Properties
a)      All the numbers in the matrix are prime numbers
b)      All the numbers in the matrix are unique
c)       The sum of all the elements in any row is a prime number
d)      The sum of all the elements in any column is a prime number
e)      The sum of all the elements in any of the two diagonals is a prime number
You end up… with… amazingly… and astonishingly… exactly… (how the heck did they do that?!)… 482,139,064 different combinations!!!
There is a theory that the Nazca civilization was colonized by extra-terrestrial beings. Certainly the findings of the “Prime Stone” paper will reenergize and heat up this conversation again.
In order to prove/disprove these findings, you need to write an algorithm that takes as input three parameters:
-          N: the dimensions of the matrix (NxN)
-          L: the lower-bound of the prime numbers
-          U: the upper-bound of prime numbers
And returns the number of different combinations of the “Prime Stone” (based on the above properties) using primes in the [L, U] range. For example: for N = 3, L = 35 and U = 71:
PrimeStone.exe 3 35 71
Output should be:
Total solutions found: 936
One of the solutions, for instance, is this one:
71 67 59
47 43 41
61 53 37
And if you can… run against N = 3, L = 0 and U = 100, and see if you get the same result as the Israeli/Iranian team of scientists!
Solution
Since the problem is asking for all the combinations, it should be clear that we’re looking for a brute-force approach (unless the Nazca folks knew of a better, faster way). So the approach should be backtracking. But the search space can be pruned, and that’s when the tradeoff space vs. time come into play. There are certain techniques that can be used to speed up the search:
1)      Calculate and cache the list of prime numbers between [L, U]. You can even use the Sieve of Eratosthenes to find these primes.
2)      Keep a tab of the current sum of the elements for each row, column and diagonal. Hence you’ll need an extra 2*N + 2 space (array of int) to store this data.
3)      Also, keep a tab of the current count of elements for each row, column and diagonal (again, another 2*N + 2 space).
4)      Using the info in {1,2,3}, at each point in the recursive iteration, check whether the column, or row, or diagonal has been filled completely, and if so, check whether the sum is a prime number or not, and if it isn’t, skip this iteration. This is accomplished by the multiple if conditions inside the main loop – here is an example:
if (count[n + c] >= n && !mapOfPrimes[sum[n + c]])
In the example above the code is checking on the spot that the col has not reached its capacity yet, and if it did, that the current sum is a prime number.
The backtracking strategy uses a linear counter to access the position in the matrix – notice how we can get the column and row numbers based on this linear counter:
int r = currentPosition / n;
int c = currentPosition % n;
Also, another minor trick is to randomize the position of the elements in the list of prime numbers. This is particularly useful when trying to find any solution for large input values. The randomization trick is done by adding a non-deterministic if clause:
                        if (rd.Next(0, 10) < rd.Next(0, 5))
                        {
                            primeNumbers.AddLast(i);
                        }
                        else
                        {
                            primeNumbers.AddFirst(i);
                        }
And that’s it. Code is below. Turns out that the Nazca people were right. Before looking at the code, however, there is one extra interesting fact about this problem: it turns out that there is no solution for this problem if N is an even number. The proof for N > 2 and N even is easy: there is only one even prime number (2), and since there are at least 4 rows, one of the rows won’t contain a 2, so the row will contain only odd numbers. If you add up an even number of terms of odd numbers, you will end up with an even number, which won’t be the number 2, hence not a prime number! The proof for the case when N = 2 is a very ingenious one, but unfortunately this post would become a little too long if it was copied/pasted here (that's actually a lie. I don't know if there is a solution for N = 2). Now the code:
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
 
namespace PrimeStone
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 0;
            int initNumber = 0;
            int endNumber = 0;
            bool printStones = false;
            if (args.Length != 4 ||
                !Int32.TryParse(args[0], out n) ||
                !Int32.TryParse(args[1], out initNumber) ||
                !Int32.TryParse(args[2], out endNumber) ||
                (!args[3].Equals("p") && !args[3].Equals("-p")))
            {
                Console.WriteLine("Usage: PrimeStones.exe <n> <init number> <end number> <p or -p>");
                Console.WriteLine("Limit the numbers to small ones... Use p for printing the stones or -p for supressing them");
                return;
            }
 
            printStones = args[3].Equals("p");
 
            FindPrimeStones(n, initNumber, endNumber, printStones);
        }
 
        static void FindPrimeStones(int n, int initNumber, int endNumber, bool printStones)
        {
            int numberSolutionsFound = 0;
            if (n > 1)
            {
                bool[] mapOfPrimes = GenerateMapOfPrimes(endNumber * n);
 
                LinkedList<int> primeNumbers = new LinkedList<int>();
                for(int i=0;i<mapOfPrimes.Length;i++)
                {
                    if (i>=initNumber && i<=endNumber && mapOfPrimes[i])
                    {
                        if (rd.Next(0, 10) < rd.Next(0, 5))
                        {
                            primeNumbers.AddLast(i);
                        }
                        else
                        {
                            primeNumbers.AddFirst(i);
                        }
                    }
                }
 
                int[] used = new int[endNumber + 1];
                int[] sum = new int[2 * n + 2];
                int[] count = new int[2 * n + 2];
                int[,] board = new int[n, n];
 
                FindPrimeStonesInternal(n,
                                        0,
                                        ref primeNumbers,
                                        ref numberSolutionsFound,
                                        ref board,
                                        ref sum,
                                        ref count,
                                        ref mapOfPrimes,
                                        ref used,
                                        printStones);
 
            }
 
            Console.WriteLine("Total solutions found: {0}", numberSolutionsFound);
        }
 
        static void FindPrimeStonesInternal(int n,
                                            int currentPosition,
                                            ref LinkedList<int> primeNumbers,
                                            ref int solutionsFound,
                                            ref int[,] board,
                                            ref int[] sum,
                                            ref int[] count,
                                            ref bool[] mapOfPrimes,
                                            ref int[] used,
                                            bool printStones)
        {
            //Base
            if (currentPosition >= n * n)
            {
                solutionsFound++;
                if (printStones)
                {
                    Print(solutionsFound, board, n);
                }
                return;
            }
 
            //Induction (backtracking)
            int r = currentPosition / n;
            int c = currentPosition % n;
 
            foreach(int candidate in primeNumbers)
            {
                if (used[candidate] == 0)
                {
                    //Check row:
                    sum[r] += candidate;
                    count[r]++;
                    if (count[r] >= n && !mapOfPrimes[sum[r]])
                    {
                        sum[r] -= candidate;
                        count[r]--;
 
                        continue;
                    }
 
                    //Check col:
                    sum[n + c] += candidate;
                    count[n + c]++;
                    if (count[n + c] >= n && !mapOfPrimes[sum[n + c]])
                    {
                        sum[n + c] -= candidate;
                        count[n + c]--;
 
                        sum[r] -= candidate;
                        count[r]--;
 
                        continue;
                    }
 
                    //Check diag1
                    if (r == c)
                    {
                        sum[2 * n] += candidate;
                        count[2 * n]++;
                        if (count[2 * n] >= n && !mapOfPrimes[sum[2 * n]])
                        {
                            sum[2 * n] -= candidate;
                            count[2 * n]--;
 
                            sum[n + c] -= candidate;
                            count[n + c]--;
 
                            sum[r] -= candidate;
                            count[r]--;
 
                            continue;
                        }
                    }
 
                    //Check diag2
                    if (r + c == n - 1)
                    {
                        sum[2 * n + 1] += candidate;
                        count[2 * n + 1]++;
                        if (count[2 * n + 1] >= n && !mapOfPrimes[sum[2 * n + 1]])
                        {
                            sum[2 * n + 1] -= candidate;
                            count[2 * n + 1]--;
 
                            if (r == c)
                            {
                                sum[2 * n] -= candidate;
                                count[2 * n]--;
                            }
 
                            sum[n + c] -= candidate;
                            count[n + c]--;
 
                            sum[r] -= candidate;
                            count[r]--;
 
                            continue;
                        }
                    }
 
                    //Now call recursively
                    used[candidate] = 1;
                    board[r, c] = candidate;
                    FindPrimeStonesInternal(n,
                                            currentPosition + 1,
                                            ref primeNumbers,
                                            ref solutionsFound,
                                            ref board,
                                            ref sum,
                                            ref count,
                                            ref mapOfPrimes,
                                            ref used,
                                            printStones);
 
                    used[candidate] = 0;
 
                    //Row
                    sum[r] -= candidate;
                    count[r]--;
 
                    //Col
                    sum[n + c] -= candidate;
                    count[n + c]--;
                   
                    //Diag1
                    if (r == c)
                    {
                        sum[2 * n] -= candidate;
                        count[2 * n]--;
                    }
                   
                    //Diag2
                    if (r + c == n - 1)
                    {
                        sum[2 * n + 1] -= candidate;
                        count[2 * n + 1]--;
                    }
                }
            }
        }
 
        static void Print(int solutionNumber, int[,] board, int n)
        {
            Console.WriteLine("Solution number #{0}", solutionNumber);
 
            for (int r = 0; r < n; r++)
            {
                for (int c = 0; c < n; c++)
                {
                    Console.Write("{0} ", board[r,c]);
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }
 
        static bool[] GenerateMapOfPrimes(int n)
        {
            if (n <= 0)
            {
                return null;
            }
 
            bool[] mapOfPrimes = new bool[n];
 
            for(int i=0;i<n;i++)
            {
                mapOfPrimes[i] = true;
            }
 
            //Special cases
            mapOfPrimes[0] = false;
            if (n > 1)
            {
                mapOfPrimes[1] = false;
            }
 
            int boundary = (int)Math.Sqrt(n) + 1;
 
            for (int i = 2; i <= boundary; i++)
            {
                for (int j = i; i * j < n; j++)
                {
                    mapOfPrimes[i * j] = false;
                }
            }
 
            return mapOfPrimes;
        }
    }
}

 


Comments

Post a Comment

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

-
Image
To solve this Advent of Code (parts 1 and 2), I used Breadth-First Search (BFS) to keep moving the guard as well as Finite State Machine (FSM) to control the directions. This solves part 1 easily. Part 2 can be solved using the same technique, takes a little longer since you need to try every empty cell, but it eventually does the trick (takes a min or so). Code is down below, cheers, ACC. Day 6 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); List map = new List (); int startRow = 0; int startCol = 0; while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); map.Add(new StringBuilder(line)); int indexStart = line.IndexOf('^'); ...
Read more

Golang vs. C#: performance characteristics (simple case study)

-
Image
This is an interesting example to study the performance characteristics of Golang compared to C# for a very particular case (not generalized though).  The same code was written in C# and Golang (literally translated from one to the other). Below you'll be able to see the source code for both. The problem is a simple post-order DFS in a tree-like graph. The code in C# times out (TLE = Time Limited Exceeded). The code in Golang not only works but beats 100% of the other Golang submissions. Take a look the image below: Some potential reasons for the performance gains from Go in this particular example are: 1. Language and Runtime Differences:    Go is compiled directly to machine code, while C# typically runs on a virtual machine (CLR).    Go has a simpler runtime with less overhead compared to the .NET runtime.    Go's garbage collector is designed for low latency, which can lead to better performance in some scenarios. 2. Data Structures:    G...
Read more

Advent of Code - Day 7, 2024: Backtracking and Eval

-
Image
Problem today requires backtracking and eval (evaluating a mathematical expression in the format of a string). Glad that it used a left-2-right evaluation, makes for an easy parsing and not overly complicated evaluation function. Code is down below for parts 1 and 2. Cheers, ACC. Day 7 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; long retVal = 0; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); string[] parts1 = line.Split(':'); long target = Int64.Parse(parts1[0]); string[] numbers = parts1[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); if (TryAll1(numbers, target, "", 0)) r...
Read more