SP6726 GOLDG - Goldbach graphs

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_ = _p_ $ _{1} $ _p_ $ _{2} $ _p_ $ _{3} $ .... _p_ $ _{k} $ is the prime factorization of _q_ (asuming _q_ > 1), then for each _i_ = 1.._k_ an edge _p_->_p $ _{i} $_ is added to graph GG(_n_). Notice that each _p $ _{i} $_ 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 _p_ $ _{1} $ and _p_ $ _{2} $ , such that each one has a unique outgoing edge (_p_ $ _{1} $ ->_p_ $ _{2} $ , $ _{} $ _p_ $ _{2} $ ->_p_ $ _{1} $ ). 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

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.