GOLDG - Goldbach graphs

no tags 

Christian Goldbach sent a letter to Leonhard Euler in 1742 in which he made the following conjecture:

"Every even number greater than 4 can be written as the sum of two odd prime numbers"

To find the solutions of Goldbach's conjecture for a given even number n (n > 0), let us define the directed graph GG(n) (the Goldbach Graph of n) as follows:

Nodes are prime numbers p such that 1 < p < n.
For each node p there are zero or more outgoing edges, determined by the following rules:
If p + q = n and q = 1, then no outgoing edges are related to p.
If p + q = n and q = p1 p2 p3 .... pk is the prime factorization of q (asuming q > 1), then for each i = 1..k an edge p->pi is added to graph GG(n). Notice that each pi must be a prime number. Besides, if k = 1 then q is prime and we have a solution to Goldbach's conjecture.

For example:

  • GG(2) is empty (it has zero nodes)
  • GG(4) has two nodes and one edge.
          nodes = {2, 3}
          edges = {2->2}
  • GG(6) has three nodes and three edges
          nodes = {2, 3, 5}
          edges = {2->2, 2->2, 3->3}
    Notice that edge 2->2 appears twice in GG(6) because when p = 2 then q = 4 = 2*2

Solutions to Goldbach's conjecture are cycles in graph GG(n) of the following types:

  • Single-node cycles (Type I): a node p with only one outgoing edge p->p.
  • Double-node cycles (Type II): two nodes p1 and p2, such that each one has a unique outgoing edge (p1->p2, p2->p1).

Your task is to inspect the directed graph GG(n) starting from a given node x and searching every node reachable from x for a solution to Goldbach's conjecture.  The procedure is successfull if a node belonging to a Type I or Type II cycle is found. In such a case the minimum distance from x to the first node of the cycle found must be reported. Otherwise it should be stated that a solution can not be found.

Your algorithm should take into account that GG(n) can contain other types of cycles besides the ones described here. Otherwise, it can run forever.


The input contains several lines each one with a different test case. Each line includes a pair of numbers representing the values n and x. You should assume that n is even and also that 2 <= n <= 1000. Although 0 < x < n is true, do not assume that x is a valid node of GG(n). The last line of the input contains the number 0 (it is not a test case).


For each test case output a single line with one of the following:

  • Solution found at distance D.
  • Solution not reachable.
  • x is not a node!

Where D is the minimum distance from x to the solution found, as described before.



2 1
4 2
6 2
6 3
12 3
12 11
14 7
20 5
38 11
50 17
540 340
540 31
540 33


1 is not a node!
Solution found at distance 0.
Solution not reachable.
Solution found at distance 0.
Solution not reachable.
Solution not reachable.
Solution found at distance 0.
Solution found at distance 1.
Solution found at distance 2.
Solution found at distance 1.
340 is not a node!
Solution found at distance 0.
33 is not a node!


Added by:Coach UTN FRSF
Time limit:1s-1.094s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Author: Pablo A. Marchetti (FRSF-UTN)