IBM Ponder This, April 2019

IBM Ponder This is awesome.

For 20 years they have been posting a math/coding/esoteric challenge once a month, and when you nail the answer, you get your name posted on a web site. Wow, name posted on a web site!!! 😊

IBM Ponder This this month (April 2019) is the following:

Find nine different prime numbers that can be placed in a 3x3 square in such a way that the average of every row, column, and diagonal is also a prime number.

Here are the steps that I took to solving this problem, and I’ll explain each one of them:

  1. Sieve
  2. Cache
  3. Backtrack
  4. Prune
  5. Trial-N-Error
Sieve: first apply the sieve of Eratosthenes to produce as many primes as you want, in N^2 time and N space
Cache: cache the primes, you don't want to be performing the same test over and over again
Backtrack: backtracking is a technique commonly used in Algorithms to perform a depth-first-search in order to find a solution
Prune: you need to prune the backtracking by cutting short the search space as soon as you don't find a possible path. I use a helper class "PrimeLine" to keep track of the calculation for each line and as such prune the search space whenever I hit a line that is not a potential candidate for the solution
Trial-N-Error: Even with the above, we're talking about a potentially large search space, in the order of N^9, where N is the max number of primes. Assume that N = 10^4, this is a massive search area: 10^36, or 2^288. Big number (to give you an idea, the number of atoms in the universe is about 2^640). Hence at this point you need to think about some trial and error approaches. When I ran the code for the first time, it did not work since I was going from the smaller primes to the larger ones. I decided to conjecture that the solution would start with bigger primes first. So the backtrack goes in descending order from the large primes to the small ones. It worked.

Code is below, cheers, ACC.


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
using System.Numerics;

namespace IBMPonderThisApril2019
{
 class Program
 {
  public static int[] primesCache = null;
  public static Hashtable primesCacheHT = new Hashtable();
  static void Main(string[] args)
  {
   //Prime the cache
   PrimesSieve();
   Console.WriteLine("Number of Primes: {0}", primesCache.Length);

   PrimeLine[] rows = new PrimeLine[3];
   for (int i = 0; i < rows.Length; i++)
   {
    rows[i] = new PrimeLine();
   }
   PrimeLine[] cols = new PrimeLine[3];
   for (int i = 0; i < cols.Length; i++)
   {
    cols[i] = new PrimeLine();
   }
   PrimeLine diag1 = new PrimeLine();
   PrimeLine diag2 = new PrimeLine();

   int numberOfSolutions = 0;
   int MAXSOLUTIONS = 100;
   Process(0, primesCache.Length - 1, new int[9], rows, cols, diag1, diag2, ref numberOfSolutions, MAXSOLUTIONS);
  }

  public static void PrimesSieve()
  {
   int MAXSIEVE = 10000;
   bool[] sieve = new bool[MAXSIEVE];

   sieve[0] = sieve[1] = true;
   for (long i = 2; i < MAXSIEVE; i++)
   {
    for (long j = i; i * j < MAXSIEVE; j++)
    {
     sieve[i * j] = true;
    }
   }

   int countCache = 0;
   for (int i = 0; i < MAXSIEVE; i++)
   {
    if (!sieve[i])
    {
     countCache++;
     primesCacheHT.Add(i, true);
    }
   }

   primesCache = new int[countCache];
   int index = 0;
   for (int i = 0; i < MAXSIEVE; i++)
   {
    if (!sieve[i])
    {
     primesCache[index++] = i;
    }
   }
  }

  public static bool Process(int index,
           int primesCacheIndex,
           int[] primes,
           PrimeLine[] rows,
           PrimeLine[] cols,
           PrimeLine diag1,
           PrimeLine diag2,
           ref int numberOfSolutions,
           int maxSolutions)
  {
   if (index >= primes.Length)
   {
    numberOfSolutions++;

    Console.WriteLine("Solution {0}:", numberOfSolutions);
    for (int i = 0; i < primes.Length; i++)
    {
     Console.Write("{0} ", primes[i]);
     if ((i + 1) % 3 == 0)
     {
      Console.WriteLine();
     }
    }
    Console.WriteLine();

    return numberOfSolutions >= maxSolutions;
   }

   int r = index / 3;
   int c = index % 3;

   for (int candidateIndex = primesCacheIndex; candidateIndex >= 0; candidateIndex--)
   {
    int candidate = primesCache[candidateIndex];

    //Rows
    rows[r].Add(candidate);
    if (rows[r].count == 3 && !rows[r].IsAvgPrime())
    {
     rows[r].Remove(candidate);
     continue;
    }
    //Cols
    cols[c].Add(candidate);
    if (cols[c].count == 3 && !cols[c].IsAvgPrime())
    {
     //Remember to remove the row
     rows[r].Remove(candidate);

     cols[c].Remove(candidate);
     continue;
    }
    //Diag 1
    if (r - c == 0)
    {
     diag1.Add(candidate);
     if (diag1.count == 3 && !diag1.IsAvgPrime())
     {
      //Remember to remove the row and col
      rows[r].Remove(candidate);
      cols[c].Remove(candidate);

      diag1.Remove(candidate);
      continue;
     }
    }
    //Diag 2
    if (r + c == 2)
    {
     diag2.Add(candidate);
     if (diag2.count == 3 && !diag2.IsAvgPrime())
     {
      //Remember to remove the row, col and diag1
      rows[r].Remove(candidate);
      cols[c].Remove(candidate);
      if (r - c == 0)
      {
       diag1.Remove(candidate);
      }

      diag2.Remove(candidate);
      continue;
     }
    }

    primes[index] = candidate;
    if (Process(index + 1, candidateIndex - 1, primes, rows, cols, diag1, diag2, ref numberOfSolutions, maxSolutions)) return true;

    //Cleanup
    rows[r].Remove(candidate);
    cols[c].Remove(candidate);
    if (r - c == 0)
    {
     diag1.Remove(candidate);
    }
    if (r + c == 2)
    {
     diag2.Remove(candidate);
    }
   }

   return false;
  }
 }

 class PrimeLine
 {
  public long[] numbers = new long[3];
  public long sum = 0;
  public int count = 0;

  public void Add(long value)
  {
   if (count < 3)
   {
    numbers[count] = value;
    count++;
    sum += value;
   }
  }

  public void Remove(long value)
  {
   sum -= value;
   count--;
  }

  public bool IsAvgPrime()
  {
   if (sum % 3 == 0 && Program.primesCacheHT.ContainsKey((int)(sum / 3)))
   {
    return true;
   }
   return false;
  }
 }
}

Comments

  1. This comment has been removed by the author.

    ReplyDelete
  2. very nice, congrats Boris!

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. There exist an n*n solution for all odd n. This is due to the famous proof Green/Tao theorem from 2005 that says there exist arithmetric progression of primes of any length.
    https://www.wikiwand.com/en/Green%E2%80%93Tao_theorem
    These solutions will be magic squares as well. The limitation to odd n's is because the magic square template only works for odd n.
    However the Green/Tao proof is not constructive...

    But the highest know AP of primes has length 26 and this is just above the 5*5 square limit.
    Using this AP gives a 5*5 solution.

    Magic square template:
    17 24 1 8 15
    23 5 7 14 16
    4 6 13 20 22
    10 12 19 21 3
    11 18 25 2 9

    Subsitute primes from the AP into the template:
    1:43142746595714191
    2:48425980631694091
    3:53709214667673991
    4:58992448703653891
    5:64275682739633791
    6:69558916775613691
    7:74842150811593591
    8:80125384847573491
    9:85408618883553391
    10:90691852919533291
    11:95975086955513191
    12:101258320991493091
    13:106541555027472991
    14:111824789063452891
    15:117108023099432791
    16:122391257135412691
    17:127674491171392591
    18:132957725207372491
    19:138240959243352391
    20:143524193279332291
    21:148807427315312191
    22:154090661351292091
    23:159373895387271991
    24:164657129423251891
    25:169940363459231791
    (26:175223597495211691 not used)

    The average of each row will be the middle number #13: 106541555027472991 which is a prime. (part of the AP of primes)

    /Thomas Egense

    ReplyDelete
  6. Hi
    I think it's the sieve of Eratosthenes and not the sieve of Aristophanes.
    regards miracle173

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. Hi and congrats,

    I wrote my own solution at https://www.ibm.com/developerworks/community/forums/html/topic?id=c9c80380-8c90-4dd7-a0d4-a569db8fa829&ps=25

    best regards

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons