Skip to main content
Mathematica

Return to Answer

added 1371 characters in body
Source Link
Fred Simons
Fred Simons
  • 10.2k
  • 19
  • 50

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 and the value at position 3n+3 is the sum of the values at the positions 3n+1 and 3n+2. Moreover, each value at the positions 1,4,7,... must be less than nn/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 numbersthe first number 1 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 isnumberless than nn/2 and larger than the candidate that was previouslylast placed number at that position (which 0. If that is impossible, we go back to position 2 at the first visit)previous triple.
  • when we are at a position with mod(k,3)=0=2, we placecomplete the sum oftriple with 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 notsmallest available second value. IfIf that happensis impossible, we go back with our construction to the last position with mod(k,3)=1 and choose1 of the next higher available numbersame triple.

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. HereHere is the implementation.

ggg= With[ggg=Compile[{firstavailable=Function[{lstnn,n_Integer, 0}},
  Block[Module[{result=Length[lst]+1}result,
    Do[If[lst[[k]]==kavailable, result=k;Break[]]k, {ka,n+1b, Length[lst]}]; result]]c,n},
  Compile[{{nn, _Integerresult=Table[0,0}{nn}, ];
   result[[1]]=1;
 Module[{k, result, available,n},available=Range[nn];
   available[[1]]=0;
   k=1;k=2;
   While[2<=k<=nn,
   result=Table[0,{nn}];  Which[
      available=Range[nn]; Mod[k,3]==1&&k<nn,
      While[1<=k<=nn  n=0;Do[If[available[[i]]==i,n=i; Break[]],{i,result[[k]]+1,nn}];
        Which[
If[1<=n<nn/2, result[[k]]=n; available[[n]]=0; k=k+1,
       Mod[k, 3]==1 &&k<nn Do[available[[i]]=i, n=firstavailable[available{i, result[[k+1]]];result[[{k-2,k-1}]]}];
          If[n<=nnresult[[k]]=0;result[[k-1]]=0;k=Max[{k-2, result[[k]]=n; available[[n]]=0;k=k+1]0}]],
         Mod[k,3]==2&&k<nn, 
 3]==2 &&k<nn, n=firstavailable[available, result[[k]]];
      a=result[[k-1]];
    If[n<=nn, If[result[[k]]>0,available[[result[[k]]]]=result[[k]]];
     b=0;c=0;
         result[[k]]=n; available[[n]]=0;n=result[[k]]; k=k+1]If[n==0, n=a];
          Mod[kDo[If[available[[i]]==i,3]==0 &&c=a+i; 0<k<=nnWhich[c>nn, n=result[[k-2]]+result[[k-1]];Break[],
           If[n<=nn && available[[n]]==navailable[[c]]==c, result[[k]]=n;b=i;Break[]]], available[[n]]=0;k=k+1{i,n+1,nn}];
            Do[available[[result[[i]]]]=result[[i]];result[[i]]=0If[b>0,
            result[[k]]=b; {i,result[[k+1]]=c; Max[{k-3,1}]k=k+2; available[[b]]=0;available[[c]]=0, 
  k-1}];k=k          result[[k]]=0; available[[a]]=a;k=k-4]]];1] 
       result],  ]];
    result], CompilationTarget->"C"]]>"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]:=
Partition[ggg[27], ggg[42]3] // Timing
Out[3]=(* {1613.5985063693,
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0{1,02,03},0{4,014,018},0{5,016,021},0{6,019,025},0{7,020,027},0
  {8,015,023},0{9,017,026},0{10,012,022},0{11,013,024}}} *)

ThatThe argument of the function ggg must be a multiple of 3. When for nn=33 such a partitionvalue a partion does not exist, a list containing zeros is returned.

Now we can try a lot of arguments, but we can be seen inrestrict the following waydomain. 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 partionpartition does not exist. For nn=33 this sum is 17*34, oddTherefore, and therefore thea necessary condition for a partition does notto exist is that nn(nn+1)/2 is even, that is nn has to a multiple of 4 or nn+1 has to be a multiple of 4.

Another observation:That can be seen in a different way as well. In every triple there are 0 or 2 odd numbers. Therefore, whenin the totalrange of nn there must be an even amount of odd numbers in, which means that nn has to be a multiple of 4 or nn+1 has to be a multiple of 4.

We only have to consider the rangevalues 3, 12, 15, 24, 27, 36, 39, ...

Already for nn=36, the number of situations that have to be considered is oddso large that a partition can hardly be found in a reasonably time. We can reduce the number of situations with another assumption, suchthat seems to be satisfied: there is a triple partition does not existwith the property that the successive triples start with 1, 2, 3, .... That applies for every odd nn!gives the following function:

hhh=Compile[{{nn,_Integer,0}},Module[{result, available, k,a,b,c,n},result=Table[0,{nn}];
  Do[result[[3i-2]]=i,{i,1,nn/3}];
  available=Range[nn];
  Do[available[[i]]=0, {i,1,nn/3}];
  k=2;
  While[1<k<nn,
    a=result[[k-1]];
    b=0;c=0;
    n=result[[k]]; If[n==0, n=a];
    Do[If[available[[i]]==i, c=a+i; Which[c>nn, Break[], available[[c]]==c, b=i;Break[]]],
      {i,n+1,nn}];
     If[b>0,
      result[[k]]=b; result[[k+1]]=c; k=k+3; available[[b]]=0; available[[c]]=0,
      available[[result[[k-3]]]]=result[[k-3]];available[[result[[k-2]]]]=result[[k-2]];
      result[[k-2]]=0; result[[k]]=0; k=k-3] ];
  result],
  CompilationTarget->"C"];

Is there a similar argument forThis is considerably faster:

Partition[hhh[27],3]//Timing

(* {0.,{{1,10,11},{2,12,14},{3,15,18},{4,19,23},{5,22,27},{6,20,26},

{7,17,24},{8,13,21},{9,16,25}}} *)

We now can go even as far as 60:

Partition[hhh[60],3]//Timing

(* {42.2451,{{1,21,22},{2,23,25},{3,24,27},{4,26,30},{5,28,33},{6,29,35},
{7,34,41},{8,40,48},{9,42,51},{10,39,49},{11,45,56},{12,46,58},{13,47,60},
{14,43,57},{15,44,59},{16,37,53},{17,38,55},{18,36,54},{19,31,50},20,32,52}}} *)

These results strongly suggest that the condition that nn? or nn+1 is a multiple of 4 is also sufficient.

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?

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 and the value at position 3n+3 is the sum of the values at the positions 3n+1 and 3n+2. Moreover, each value at the positions 1,4,7,... must be less than nn/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 the first number 1 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 numberless than nn/2 and larger than the last placed number at that position. If that is impossible, we go back to position 2 at the previous triple.
  • when we are at a position with mod(k,3)=2, we complete the triple with the smallest available second value. If that is impossible, we go back to position 1 of the same triple.

Here is the implementation.

ggg=Compile[{{nn,_Integer, 0}},
  Module[{result, available, k, a,b,c,n},
   result=Table[0,{nn}];
   result[[1]]=1;
   available=Range[nn];
   available[[1]]=0;
   k=2;
   While[2<=k<=nn,
     Which[
       Mod[k,3]==1&&k<nn,
        n=0;Do[If[available[[i]]==i,n=i; Break[]],{i,result[[k]]+1,nn}];
        If[1<=n<nn/2, result[[k]]=n; available[[n]]=0; k=k+1,
          Do[available[[i]]=i, {i, result[[{k-2,k-1}]]}];
          result[[k]]=0;result[[k-1]]=0;k=Max[{k-2, 0}]],
        Mod[k,3]==2&&k<nn, 
          a=result[[k-1]];
          b=0;c=0;
          n=result[[k]]; If[n==0, n=a];
          Do[If[available[[i]]==i, c=a+i; Which[c>nn, Break[],
            available[[c]]==c, b=i;Break[]]], {i,n+1,nn}];
          If[b>0,
            result[[k]]=b; result[[k+1]]=c; k=k+2; available[[b]]=0;available[[c]]=0, 
            result[[k]]=0; available[[a]]=a;k=k-1] 
         ]];
    result], CompilationTarget->"C"];

Partition[ggg[27], 3] // Timing
(* {13.3693,{{1,2,3},{4,14,18},{5,16,21},{6,19,25},{7,20,27},
  {8,15,23},{9,17,26},{10,12,22},{11,13,24}}} *)

The argument of the function ggg must be a multiple of 3. When for such a value a partion does not exist, a list containing zeros is returned.

Now we can try a lot of arguments, but we can restrict the domain. 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 partition does not exist. Therefore, a necessary condition for a partition to exist is that nn(nn+1)/2 is even, that is nn has to a multiple of 4 or nn+1 has to be a multiple of 4.

That can be seen in a different way as well. In every triple there are 0 or 2 odd numbers. Therefore, in the range of nn there must be an even amount of odd numbers, which means that nn has to be a multiple of 4 or nn+1 has to be a multiple of 4.

We only have to consider the values 3, 12, 15, 24, 27, 36, 39, ...

Already for nn=36, the number of situations that have to be considered is so large that a partition can hardly be found in a reasonably time. We can reduce the number of situations with another assumption, that seems to be satisfied: there is a partition with the property that the successive triples start with 1, 2, 3, .... That gives the following function:

hhh=Compile[{{nn,_Integer,0}},Module[{result, available, k,a,b,c,n},result=Table[0,{nn}];
  Do[result[[3i-2]]=i,{i,1,nn/3}];
  available=Range[nn];
  Do[available[[i]]=0, {i,1,nn/3}];
  k=2;
  While[1<k<nn,
    a=result[[k-1]];
    b=0;c=0;
    n=result[[k]]; If[n==0, n=a];
    Do[If[available[[i]]==i, c=a+i; Which[c>nn, Break[], available[[c]]==c, b=i;Break[]]],
      {i,n+1,nn}];
     If[b>0,
      result[[k]]=b; result[[k+1]]=c; k=k+3; available[[b]]=0; available[[c]]=0,
      available[[result[[k-3]]]]=result[[k-3]];available[[result[[k-2]]]]=result[[k-2]];
      result[[k-2]]=0; result[[k]]=0; k=k-3] ];
  result],
  CompilationTarget->"C"];

This is considerably faster:

Partition[hhh[27],3]//Timing

(* {0.,{{1,10,11},{2,12,14},{3,15,18},{4,19,23},{5,22,27},{6,20,26},

{7,17,24},{8,13,21},{9,16,25}}} *)

We now can go even as far as 60:

Partition[hhh[60],3]//Timing

(* {42.2451,{{1,21,22},{2,23,25},{3,24,27},{4,26,30},{5,28,33},{6,29,35},
{7,34,41},{8,40,48},{9,42,51},{10,39,49},{11,45,56},{12,46,58},{13,47,60},
{14,43,57},{15,44,59},{16,37,53},{17,38,55},{18,36,54},{19,31,50},20,32,52}}} *)

These results strongly suggest that the condition that nn or nn+1 is a multiple of 4 is also sufficient.

Source Link
Fred Simons
Fred Simons
  • 10.2k
  • 19
  • 50

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?