Project Euler 27 - Quadratic Primes Thoughts and Soluions

    I have decided to start doing a few of the Project Euler (**PE) problems to help get my mind kicking again after a few days of being distracted by real life issues and picked one I haven't completed before: 27.

Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.
The incredible formula  n² - 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.
Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n

e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

    Now with every PE I come across I stop to think if there is any way of solving this problem without writing a single line of code. If you finish many of these problems and lurk through their forums you find posts from people on how to solve every one with assembly and where possible how to solve them with pen and paper.

    Since we only need to check a maximum of four million possible equations we could probably do it by hand. To make it easier though you want to find any possible limitations where we know doesn't meet what we need.
In this case we want to find the maximum number of primes of consecutive n starting from n=0. So the earliest an equation will fail is if when n=0 the equation isn't a prime.

(0)² + a(0) + b

b

    So no matter what we need b to be a prime. This greatly reduces the number of possible bs that we can use. A quick check gives me a count of 168 primes less than 1000; nearly a order of magnitude less combinations. Since primes can't be negative by definition ( this appears to be in debate on portions of the Internet so I'm going to go with the smaller set since both given quadratics always result in positive primes ) b is from this set of primes.

    By the previous statement about the nature of primes a must always be at least as large as one less than -b. This I get from when n = 1 (the first n where a matters):

 (1)² + a(1) + b

 a + b + 1

    Now the fact that they gave us an equation that is itself outside of the bounds of the coefficients stands out to me. This gives me the impression that there isn't an equation within the range that will ever result in a larger range than 80.

 

 

    Now given this I am going to make an assumptions to help limit the runtime of my code that isn't necessarily true and I wouldn't use in a production that would require me to get the correct answer the first time 100%. The highest prime that we will reach will be less than 6400 (n**2 for the already assumed largest n).

 

From here it is a simple triple nested for loop to find the resulting coefficients and answer.

Sample python code for the solution with the hardcoded primes removed for viewability (or view at github):

large_primes = [ 2, ... 6421]
primes = [ 2, ... 997 ]

highest_count = 40
highest_blarg = 41 # 41*1

for x in primes:
    for y in xrange(-1*x-1,1000):
        for z in xrange( 80 ):
            if( z*z+y*z+x not in large_primes ):
                if( z > highest_count ):
                    highest_count = z
                    highest_blarg = x*y
                break
       
print highest_blarg,":",highest_count

 

The solution if you don't want to plug it in yourself: -59231

Binary Tree Cycle Detection

    Upon graduation a about a month ago, I began (not really, but began to me more intense about it) to search for a job in software development. Just today, during an interview at a local company, I received a technical question that stumped for a significantly more amount of time than I expected:

Are there any cycles in this tree?

     Now I looked up this question by chance before the interview and the Internet in general and and Stackoverflow in specific wasn't very helpful; either being obstinate in stating that a tree by definition cannot have a cycle or some destructive or overly complicated solution.

   Now when my interviewers referring to a binary-tree with a cycle, they were talking about something similar to figure 1 below. This tree have the normal 2 branch binary-tree structure, with 3 (possibly incorrect; I don't really care) branches that extend to previous nodes in the tree. 

Figure 1

    There are two one main problems that I had when thinking through how to solve this problem:

1. We only have access to the root node of the tree and thus can't find the strongly connected components or some other algorithm that would find cycles in a graph.

    The simplest tree that would have a cycle of it is just the root with a self-pointing branch (figure 2), so that is where I began.

Figure2

   If we mark each node as we go along, when we reach that node again we believe there is a loop. This works for the very simple case above as well as any of the cycles shown below in figure 3.

Figure3

    The problem with this approach is the connections that aren't necessary cylces, but are possible with edges that point to non-descendant nodes (A simple example shown in Figure 4). At the current working state the method halts as show in Figure 5.

Figure 4

Figure 5

   In order to account for this type of branch, we need to unmark a node when we finish exploring all of its children, which at that point we know there isn't a cycle within that portion of the subtree we traversed, returning false only when we have explored every child (Figure 6 showing the updated method).

Figure 6

    The other way of completing this algorithm that doesn't require changing the actual tree structure itself is to keep a stack of visiting nodes. A node is popped off the stack when all it's children are visited (as above) and we know there is a cycle if there is ever a node that is already in the stack.

    Finally is a method of solving this function in a tortoise and hare style solution that I was getting stuck on trying to create during the interview.
To modify it to work with a tree/graph structure, the two runners will be a list of positions in the tree rather than a single position like what would occur in a linked-list. When there exists a single position that is in both the slow and fast list, there is a cycle. I have found that this solution doesn't work for several cases that the others do.

    For the below example how it should work. I will mark the tortoise as green and the hare as blue.

    An example of a tree where this method won't work. When the first iteration is complete node 2 will be in both the fast and slow set, but the tree has no cycle.

Below is the code for both algorithms that I wrote in C++:

Stack Based:

typedef struct Node {
 Node* left;
 Node* right;
 Node() {
  left = 0;
  right = 0;
 }
 ~Node() {
  left->~Node();
  right->~Node();
 }
} Node;

vector<Node*> v;

static bool has_cycle(Node* root) {
 if( !root ) {
  return false;
 }
 if( find(v.begin(),v.end(),root) != v.end() ) {
  return true;
 }
 v.push_back(root);
 if( root->left == 0 && root->right == 0 ) {
  v.pop_back();
 }
 if( v.empty() ) {
  return false;
 }
 return has_cycle(root->left) || has_cycle(root->right);
}

Marking based:

typedef struct Node {
 Node* left;
 Node* right;
 bool visited;
 Node() {
  left = 0;
  right = 0;
  visited = false;
 }
 ~Node() {
  left->~Node();
  right->~Node();
 }
} Node;

static bool has_cycle(Node* root) {
 if( root == 0 ) {
  return false;
 }
 if( root->visited ) {
  return true;
 }
 root->visited = true;
 if( !has_cycle(root->left) && !has_cycle(root->right) ) {
  root->visited = false;
  return false;
 }
 return true;
}

HTML5 Dart Centipede Demo

Dart centipede

Simple Centipede Game

• Eat the Food
• Don't run into the walls
• Don't run into yourself