First build a set of possible "neighbors" for each integer 1..n. For this problem, two numbers can be neighbors only if the sum of their squares is prime. For example, for n=10. the n sets are

s(1) = {2,4,6,10}
s(2) = {1,3,5,7}
s(3) = {2,8,10}
s(4) = {1,5,9}
s(5) = {2,4,6,8}
s(6) = {1,5}
s(7) = {2,8,10}
s(8) = {3,5,7}
s(9) = {4,10}
s(10)= {1,3,7,9}

Note that some of these sets (e.g., s(6) and s(9)) are much smaller  than others. Because 6 and 9 have fewer possible neighbors, they will be more difficult to use in building a solution. Hence, use the following heuristic when building a solution: at each step, take the largest number that has the fewest possible neighbors. After each step, we need to update the neighbor sets. Note that if n is odd, then we must begin the solution with an odd number because there are more odd numbers in 1..n than even numbers.

For n=10, the first number in the solution is 9 because it is the largest number that has the fewest neighbors. So we remove 9 from all the neighbor sets and look at the possible neighbors of 9: 4 and 10. The number 4 now has 2 possible neighbors; the number 10 has 3 possible neighbors. We choose 4 because it has the fewest.

Continuing with this algorithm, we find the solution

{9,4,5,6,1,10,7,8,3,2}

This method works in many sequential decision problems in which the solution is found without backtracking. In the language of graph theory, a solution to this problem is a Hamiltonian path. The sets s(i) are the adjacency lists for the graph.

***

For the Task 2 T. D. Noe has an answer for all the 4 questions:

I have some results on task 2:

a,b. I think that there is a solution for all n > 97. However, it is possible that the true n0 is less than 97. My non-exhaustive algorithm, given below, found solutions for n=98,99,...,200. It also found solutions for 2,3,4,6,10,11,59-66,71,73-79,81,84,87-96. It missed solutions for n=12 and 31.

This problem can be viewed as a graph-theory problem. Two numbers

(vertices) are connected by an edge if their sum is prime and the sum of their squares is prime. The problem is to determine whether there is a Hamiltonian path (not cycle) that visits each vertex just once. For each n, much can be learned by examining degree of each vertex -- the number of edges at each vertex. By looking at the vertices that have degree 0 or 1, it can be shown that there can be no solution for n=3,5,7,8,9,13-25,29,35,37-43,48,50,55,57. I have used exhaustive search to show that there are no solutions for n=26,27,28,30,32,33,34,36. That still leaves the following numbers with unknown status: n=44-47,49,51-54,56,58,67-70,72,80,82,83,85,86.

c. In Mathematica, my greedy-type algorithm is:

n=100;
s=Table[{},{n}];
For[i=1,i<=n,i++, (* 1 *)
For[j=1,j<=n,j++,
If[i+j>2&&PrimeQ[i^2+j^2]&&PrimeQ[i+j], AppendTo[s[[i]],j]]]];
lst={}; solnSet=If[OddQ[n], Range[1,n,2], Range[n]]; While[Length[solnSet]>0,
For[minVal=n; minPos=0; i=1,i<=Length[solnSet],i++, (* 2 *)
j=solnSet[[i]]; len=Length[s[[j]]];
If[len>0, If[len<=minVal, minVal=len; minPos=j]]];
If[minPos==0&&Length[lst]<n-1, Print["No greedy solution for ",n]; Break[],
If[minPos==0,
AppendTo[lst,solnSet[[1]]]; solnSet={},
AppendTo[lst,minPos];
solnSet=s[[minPos]];
For[i=1,i<=Length[solnSet],i++, (* 3 *)
j=s[[minPos]][[i]];
s[[j]]=DeleteCases[s[[j]],minPos]];
s[[minPos]]={}]]];
If[Length[lst]==n, Print[lst]];

What it does, basically, is (1) compute the adjacency lists s[i] for each vertex i, (2) build the solution in "lst" sequentially by choosing the number that is connected to the previous vertex and has the fewest connections to other numbers not in the solution yet, and (3) remove the new vertex from the adjacency lists. Note that when n is odd, the solution must begin and end with an odd number. Also note that this algorithm works for task 1 also; just change the definition of the adjacency lists s[i].

d. There is no solution for n=50 because there are two numbers (vertices), 37 and 47, that have only one edge. So any solution must begin and end with those two numbers. But when n is an even number, the solution must begin and end with numbers of opposite parity; one must be even and the other odd.

A solution for n=100 is

{89,74,29,44,39,34,49,40,63,38,93,98,83,18,23,48,53,78,35,68,95,54,59,24,19,
84,79,94,99,50,87,92,17,62,47,80,69,70,37,72,7,12,77,30,73,58,55,96,31,76,61
,90,91,66,71,36,65,86,11,6,1,16,51,56,41,60,97,42,5,32,57,82,67,22,25,88,85,
64,9,4,75,52,45,14,15,46,21,26,81,100,13,28,43,10,27,2,3,20,33,8}

***