We may assume that the partition we are looking for is ordered, and that every triple is ordered as well. When we flatten this list of partitions, we arrive at a permutation of the first nn integers, such that the first value is 1, the values at the positions 1,4,7, ... are increasing, and for every n the values at the positions 3n+1, 3n+2 and 3n+3 are increasing, such that the value at position 3n+3 is the sum of the values at the positions 3n+1 and 3n+2. Our backtracking process tries to construct this list, in the implementation called result. At any stage we have a number k, the position at which we have to place a number in the list result, and moreover a list called available of the numbers from which we can choose. We start with the list result with no numbers placed, the list available with the complete range and k=1. The construction is then as follows:
- when we are at a position with mod(k,3)=1, we place the smallest available number.
- when we are at a position with mod(k,3)=2, we place the first available number that is larger than the candidate that was previously placed at that position (which 0 at the first visit).
- when we are at a position with mod(k,3)=0, we place the sum of the two predecessors. That is not always possible, for two reasons: it could be that this sum is larger than nn or that it is not available. If that happens, we go back with our construction to the last position with mod(k,3)=1 and choose the next higher available number.
In the implementation I use an auxiliary function firstavailable to find the first number larger than the second argument that can be placed. The implementation is deliberately a little bit primitive, bevause of it will be used in a compiled function. Here is the implementation.
ggg= With[{firstavailable=Function[{lst,n }, Block[{result=Length[lst]+1}, Do[If[lst[[k]]==k, result=k;Break[]], {k,n+1, Length[lst]}]; result]]}, Compile[{{nn, _Integer,0}}, Module[{k, result, available,n}, k=1; result=Table[0,{nn}]; available=Range[nn]; While[1<=k<=nn, Which[ Mod[k, 3]==1 &&k<nn, n=firstavailable[available, result[[k+1]]]; If[n<=nn, result[[k]]=n; available[[n]]=0;k=k+1], Mod[k, 3]==2 &&k<nn, n=firstavailable[available, result[[k]]]; If[n<=nn, If[result[[k]]>0,available[[result[[k]]]]=result[[k]]]; result[[k]]=n; available[[n]]=0; k=k+1], Mod[k,3]==0 && 0<k<=nn, n=result[[k-2]]+result[[k-1]]; If[n<=nn && available[[n]]==n, result[[k]]=n; available[[n]]=0;k=k+1, Do[available[[result[[i]]]]=result[[i]];result[[i]]=0, {i, Max[{k-3,1}], k-1}];k=k-4]]]; result], CompilationTarget->"C"]] The result of this function is either a list giving the desired partition (when k > nn) or a list of zeros when such a partition does not exist (when k < 1).
I only found lists of zeros. Here is an example:
In[3]:= ggg[42] // Timing Out[3]= {16.598506, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}} That for nn=33 such a partition does not exist, can be seen in the following way. Since every third number is the sum of its two predecessors, the sum of all third numbers must be half of the sum of all numbers, so when the sum of all numbers is odd, such a partion does not exist. For nn=33 this sum is 17*34, odd, and therefore the partition does not exist.
Another observation: in every triple there are 0 or 2 odd numbers. Therefore, when the total of odd numbers in the range is odd, such a triple partition does not exist. That applies for every odd nn!
Is there a similar argument for even nn?