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

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more

The Power Sum, a recursive problem by HackerRank

-
Image
Another one by HackerRank:  https://www.hackerrank.com/challenges/the-power-sum : Find the number of ways that a given integer,  , can be expressed as the sum of the   power of unique, natural numbers. Input Format The first line contains an integer  .  The second line contains an integer  . Constraints Output Format Output a single integer, the answer to the problem explained above. Sample Input 0 10 2 Sample Output 0 1 Explanation 0 If   and  , we need to find the number of ways that   can be represented as the sum of squares of unique numbers. This is the only way in which   can be expressed as the sum of unique squares. Sample Input 1 100 2 Sample Output 1 3 Explanation 1 Sample Input 2 100 3 Sample Output 2 1 Explanation 2  can be expressed as the sum of the cubes of  .  . There is no other way to express   as th
Read more