Mathematik: Calculating sequence element a(16) of OEIS A108235
Released by matroid on Sa. 18. April 2020 18:31:10 [Statistics]
Written by StrgAltEntf - 1042 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)
Abstract

The On-Line Encyclopedia of Integer Sequences (OEIS) lists under the identifier A108235 the following sequence:

$a(n)=$ Number of partitions of $\{1,2,...,3n\}$ into $n$ triples $(X,Y,Z)$ each satisfying $X+Y=Z$.

The following values can be found there (status on Apr 18 2020)
n       a(n)
1          1
2          0
3          0
4          8
5         21
6          0
7          0
8       3040
9      20505
10         0
11         0
12  10567748
13 103372655
14         0
15         0

For example, $a(4)=8$, and there are the following eight partitions of set $\{1,2,...,12\}$.
No. 1 (1 5 6) (2 8 10) (3 9 12) (4 7 11)
No. 2 (1 5 6) (2 9 11) (3 7 10) (4 8 12)
No. 3 (1 6 7) (2 10 12) (3 8 11) (4 5 9)
No. 4 (1 8 9) (2 10 12) (3 4 7) (5 6 11)
No. 5 (1 9 10) (2 4 6) (3 8 11) (5 7 12)
No. 6 (1 10 11) (2 5 7) (3 6 9) (4 8 12)
No. 7 (1 11 12) (2 6 8) (3 7 10) (4 5 9)
No. 8 (1 11 12) (2 7 9) (3 5 8) (4 6 10)

Now we are happy to announce that we can add two more members to this sequence. The following holds.
\[a(16)=142664107305\]
\[a(17)=1836652173363\]
Furthermore, we were able to calculate the member \(a'(43)\) for the related sequence A002849.
\[a'(43)=16852166906\]





This is how we did it

First, we note that for a partition to exist with the desired properties, it is necessary that the sum $1+2+...+3n=\frac{3n(3n+1)}2$ is even. Thus $4\not\mid n(3n+1)\Rightarrow a(n)=0$ applies. This also explains the many zeros in the above list. For example, there is no partition with the requested properties for $n=11$, since $11\cdot34$ is not divisible by 4. However, since $16\cdot49$ is divisible by 4, partitions can be expected for $n=16$ and similarly for $n = 17$. And there are actually very many, as it turned out.

To accomplish the calculation of $a(16)$, the help of computers was necessary. We have parallelized the calculation by specifying a triple $(1,y,y+1)$ and counting those partitions that contain $(1,y,y+1)$. The calculation for $y =2,3,...,47$ could then be done independently.

The calculation could be achieved with the following C program. Please don't be scared, most of the code only concerns the input and output.
246 lines of code
C
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define Nmax 20 // maximum list length is 3*Nmax
  6. int N; // the current list length is 3*N
  7. long long int solutioncounter = 0;
  8. int solution[Nmax][3]; // collects triplets of a partition
  9.  
  10. // only for the output
  11. int boundary[Nmax+1] = {1, 1, 1, 1, 1, 1, 1, 1, 100, 1000, 1000, 1000,
  12. 100000, 100000, 1000000, 1000000, 1000000, 100000, 100000, 100000, 100000};
  13.  
  14. //---------------------------------------------------------------------------
  15.  
  16. /*
  17.   delete list[0], list[j] and list[k] from list[0]...list[3n-1]
  18.   and check the reduced list
  19.  
  20.   Return value:
  21.   0, if (sum of the first two thirds entries of the new list)
  22.   <= (sum of the last third entries of the new list)
  23.   1, else -> abort
  24. */
  25. int reduce(int list[3*Nmax], int newlist[3*Nmax], int j, int k, int n){
  26. int i, m = 0, sum1 = 0, sum2 = 0;
  27.  
  28. for(i=1; i<j; i++)
  29. newlist[m++] = list[i];
  30. for(i=j+1; i<k; i++)
  31. newlist[m++] = list[i];
  32. for(i=k+1; i<3*n; i++)
  33. newlist[m++] = list[i];
  34.  
  35. for(i=0; i<2*n-2; i++)
  36. sum1 += newlist[i];
  37. for(i=2*n-2; i<3*n-3; i++)
  38. sum2 += newlist[i];
  39.  
  40. if(sum1 > sum2)
  41. return 1; // -> abort
  42. else
  43. return 0;
  44. }
  45.  
  46. //---------------------------------------------------------------------------
  47.  
  48. // Print a solution for your entertainment
  49. void printsolution(void){
  50. int j;
  51.  
  52. if(solutioncounter % boundary[N])
  53. return;
  54.  
  55. printf("No. %Ld ", solutioncounter);
  56. for(j=N-1; j>=0; j--)
  57. printf("(%d %d %d) ", solution[j][0], solution[j][1], solution[j][2]);
  58. printf("\n");
  59. }
  60.  
  61. //---------------------------------------------------------------------------
  62.  
  63. // Built-in-test
  64. // tests that no error has occurred
  65. // Return value: 0, if anything ok
  66. // 1, if error
  67. int builtintest(void){
  68. int j, k, sum, test[3*Nmax+1];
  69.  
  70. for(j=1; j<=3*N; j++)
  71. test[j] = 0;
  72. for(j=0; j<N; j++){
  73. if(solution[j][0] + solution[j][1] != solution[j][2]){ // Fatal error!
  74. boundary[N] = 1;
  75. return 1;
  76. }
  77. for(k=0; k<3; k++)
  78. test[solution[j][k]] = 1;
  79. }
  80. sum = 0;
  81. for(j=1; j<=3*N; j++)
  82. sum += test[j];
  83.  
  84. if(sum == 3*N)
  85. return 0;
  86. else{ // Fatal error!
  87. boundary[N] = 1;
  88. return 1;
  89. }
  90. }
  91.  
  92. //---------------------------------------------------------------------------
  93.  
  94. // Recursive search for valid partitions in a list of length 3*n
  95. void search(int list[3*Nmax], int n){
  96. int newlist[3*Nmax];
  97. int j, k;
  98.  
  99. if(n == 0){
  100. solutioncounter++; // BINGO! Valid partition found
  101.  
  102. if(builtintest()){ // for paranoids ... may be omitted
  103. printsolution();
  104. printf("Fatal error in program!\n");
  105. exit(0);
  106. }
  107.  
  108. printsolution(); // may be omitted
  109.  
  110. return;
  111. }
  112.  
  113. for(j=1; j<3*n; j++){
  114. for(k=j+1; k<3*n; k++){ // searching for triplets (list[0] list[j] list[k])
  115. if(list[0] + list[j] < list[k])
  116. break; // for this k and greater k no solution is possible
  117.  
  118. if(list[0] + list[j] == list[k]){ // new triple found
  119. solution[n-1][0] = list[0]; // add triple to solutions
  120. solution[n-1][1] = list[j]; // ... to print it out later
  121. solution[n-1][2] = list[k]; // ... (may be omitted)
  122.  
  123. if(reduce(list, newlist, j, k, n)) // delete triple from list
  124. continue; // test of reduced list failed
  125. search(newlist, n-1); // search shortened list
  126. break;
  127. }
  128. }
  129. }
  130. }
  131.  
  132. //---------------------------------------------------------------------------
  133.  
  134. int main(int ac, char **av){
  135. int list[3*Nmax];
  136. int i, j, x, y, z, error = 0, hlp;
  137. time_t begin, end, total;
  138.  
  139. time(&begin);
  140.  
  141. printf("===================\n");
  142. printf("| OEIS A108235 |\n");
  143. printf("===================\n");
  144.  
  145. if(ac != 2 && ac !=5){
  146. printf("Usage:\n");
  147. printf(" %s N\n", av[0]);
  148. printf(" or\n");
  149. printf(" %s N x y z\n", av[0]);
  150. printf(" (x + y = z)\n");
  151. return 1;
  152. }
  153.  
  154. N = atoi(av[1]);
  155.  
  156. printf("Compute a(N) for N = %d\n", N);
  157.  
  158. if(boundary[N] == 1)
  159. printf("Output every solution\n");
  160. else
  161. printf("Output every %d-th solution\n", boundary[N]);
  162.  
  163. if(N > Nmax || N < 1){
  164. printf("Invalid N = %d\n", N);
  165. return 1;
  166. }
  167.  
  168. for(hlp=i=0; i<3*N; i++)
  169. hlp += i+1;
  170.  
  171. if(hlp % 2){
  172. printf("There is no valid partition of 1...3*N for N = %d\n", N);
  173. return 1;
  174. }
  175.  
  176. if(ac == 5){
  177. x = atoi(av[2]);
  178. y = atoi(av[3]);
  179. z = atoi(av[4]);
  180. printf("x = %d y = %d z = %d\n", x, y, z);
  181. if(x < 1 || x > 3*N){
  182. printf("Invalid value x = %d\n", x);
  183. error = 1;
  184. }
  185. if(y < 1 || y > 3*N){
  186. printf("Invalid value y = %d\n", y);
  187. error = 1;
  188. }
  189. if(z < 1 || z > 3*N){
  190. printf("Invalid value z = %d\n", z);
  191. error = 1;
  192. }
  193. if((x == y) || (x + y != z)){
  194. printf("x and y must be different and must add up to z");
  195. error = 1;
  196. }
  197. if(error)
  198. return 1;
  199.  
  200. if(y < x){
  201. hlp = y;
  202. y = x;
  203. x = hlp;
  204. }
  205. printf("Find %d disjoint triplets from 1...%d that contain the triple (%d %d %d)\n",
  206. N, 3*N, x, y, z);
  207.  
  208. // create initial list in which the triple (x y z) is missing
  209. for(j=0, i=1; i<x; i++)
  210. list[j++] = i;
  211. for(i=x+1; i<y; i++)
  212. list[j++] = i;
  213. for(i=y+1; i<z; i++)
  214. list[j++] = i;
  215. for(i=z+1; i<=3*N; i++)
  216. list[j++] = i;
  217.  
  218. solution[N-1][0] = x; // add triple (x y z) to the solutions
  219. solution[N-1][1] = y;
  220. solution[N-1][2] = z;
  221.  
  222. search(list, N-1); // call of the recursive function
  223. }
  224. else{
  225. printf("Find %d disjoint triplets from 1...%d\n", N, 3*N);
  226.  
  227. for(i=0; i<3*N; i++) // create initial list
  228. list[i] = i+1;
  229.  
  230. search(list, N); // call of the recursive function
  231. }
  232.  
  233. printf("Number of valid partitions = %Ld\n", solutioncounter);
  234.  
  235. // calculate the time needed
  236. time(&end);
  237. total = end - begin;
  238. if(total < 60)
  239. printf("Time needed: %d sec\n", total);
  240. else if(total < 3600)
  241. printf("Time needed: %.2f min\n", (double)total/60.);
  242. else
  243. printf("Time needed: %.2f h\n", (double)total/3600.);
  244.  
  245. return 0;
  246. }

If the program runs on your computer, the way it works should hopefully be self-explanatory.

A calculation within a reasonable time was only possible by the following small consideration.

Lemma 1: Let \(\{x_i,y_i,z_i\}\), \(i=1,...,k\), be pairwise disjoint sets of three different positive integers each of which satisfies \(x_i+y_i=z_i\). Further let \(b_1\lt b_2\lt...\lt b_{3k}\) such that \(\displaystyle B:= \{b_1,b_2,...,b_{3k}\}=\bigcup_{i=1}^k\{x_i,y_i,z_i\}\). Then it holds
\[S_1:=\sum_{i=1}^{2k}b_i \stackrel!\leq S_2:=\sum_{i=2k+1}^{3k}b_i\]
Proof: Let \(M_1:=\{x_1,...,x_k\}\cup\{y_1,...,y_k\}, M_2:=\{z_1,...,z_k\}\). Then
\[S_1=\min_{M\subseteq B\wedge|M|=2k}\sum_{b\in M}b\leq \sum_{b\in M_1}b = \sum_{b\in M_2}b\leq \max_{M\subseteq B\wedge|M|=k}\sum_{b\in M}b =S_2\] q. e. d.

This made it possible to discard a search tree at an early stage in the recursive search for triplets. In the above code this abort criterion is implemented in lines 35 to 40.

Note 1 (May 1 2020): In an earlier version of this article the sets \(\{x_i,y_i,z_i\}\) in Lemma 1 were part of a partition of \(\{1,2,...,3n\}\). Of course, this condition is not necessary. It was therefore also possible to use the lemma to shorten the calculation of a′(43), see explanations below.

Here are the results of the calculation. The calculation of the individual values took different lengths of time from about three hours to one day.
Complete list of results
x	y	z	Number of partitions that contain the triple (x, y, z)
1	2	3	889,120,886
1	3	4	921,635,465
1	4	5	962,359,593
1	5	6	1,010,562,667
1	6	7	1,066,239,459
1	7	8	1,128,319,611
1	8	9	1,200,430,705
1	9	10	1,281,347,974
1	10	11	1,370,418,483
1	11	12	1,469,595,473
1	12	13	1,568,971,244
1	13	14	1,683,148,960
1	14	15	1,811,796,731
1	15	16	1,943,693,569
1	16	17	2,046,389,287
1	17	18	2,175,228,046
1	18	19	2,318,611,993
1	19	20	2,471,084,712
1	20	21	2,624,515,292
1	21	22	2,789,662,822
1	22	23	2,945,942,651
1	23	24	3,074,298,960
1	24	25	2,913,951,079
1	25	26	2,904,088,956
1	26	27	3,029,283,957
1	27	28	3,160,486,143
1	28	29	3,295,589,992
1	29	30	3,448,134,464
1	30	31	3,599,592,584
1	31	32	3,757,089,678
1	32	33	3,906,652,914
1	33	34	4,047,751,528
1	34	35	4,191,875,829
1	35	36	4,353,084,955
1	36	37	4,502,544,293
1	37	38	4,642,346,446
1	38	39	4,785,252,859
1	39	40	4,920,083,992
1	40	41	5,039,172,458
1	41	42	5,166,149,522
1	42	43	5,270,456,559
1	43	44	5,358,518,135
1	44	45	5,429,211,918
1	45	46	5,466,980,797
1	46	47	5,453,508,240
1	47	48	5,268,925,424
Sum			142,664,107,305

Note 2 (May 1 2020): By improving the C-program, the times for the calculation could be improved immensely, see explanations below. The calculation of the individual values now takes from 10 minutes to 94 minutes.

Acknowledgement

I thank the forists gonz and hyperG, who provided computing time. I also thank viertel who drew my attention to the problem.

May 1 2020: Especially the forists Ixx and Kitaktus contributed with great ideas to improve the runtime of the program so that a calculation of $a(17)$ and $a'(43)$ was possible. The calculation of $a(17)$ was performed by pzktupel and to a large extent by hyperG. Many thanks to all involved!

Finally I thank Matroid for the wonderful Matheplanet.



Supplement

Status on Apr 20 2020: $a(16)$ has been added to sequence A108235 on OEIS.

May 1 2020:

Encouraged by the inclusion of our result in OEIS, we have invested a lot of effort to improve our program for calculating $a(n)$.

First we have optimized the double loop, which searches for triples $(b_1,b_j,b_k)$ with $b_1+b_j=b_k$ in the list $B=(b_1,...,b_{3n})$ with $b_1\lt...\lt b_{3n}$.
Pseudo code, old
for(j = 2; j <= 3*n; j++)
  for(k = j+1; k <= 3*n; k++)
    if(b_1 + b_j == b_k)
      remove b_1, b_j, b_k from list and examine shortened list
      break k-loop -> next j
    if(b_1 + b_j < b_k)
      break k-loop -> next j
Pseudo code, new
for(j = 2, k=3; j <= 3*n-1; j++)
  for( ; k <= 3*n; k++)
    if(b_1 + b_j == b_k)
      remove b_1, b_j, b_k from list and examine shortened list
      k++
      break k-loop -> next j
    if(b_1 + b_j < b_k)
      break k-loop -> next j
Thus $k$ did not have to start at $j+1$ with a new $j$, but could continue where it stopped with the last $j$.

Secondly, the calculation of $S_1$ and $S_2$ (see Lemma 1) within the recursive call was also performed recursively, so that the calculation for a shortened list $(b_1,...,b_{3n})$ does not require a loop of length $3n$ each time.

The following considerations also helped to shorten the duration of the program.

Lemma 2: Let \(\{x_i,y_i,z_i\}\), \(i=1,...,k\), be pairwise disjoint sets of three different positive integers each of which satisfies \(x_i+y_i=z_i\). Further let \(b_1\lt b_2\lt...\lt b_{3k}\) such that \(\displaystyle B:= \{b_1,b_2,...,b_{3k}\}=\bigcup_{i=1}^k\{x_i,y_i,z_i\}\).
Furthermore let $\displaystyle S_1:=\sum_{i=1}^{2k}b_i$, $\displaystyle S_2:=\sum_{i=2k+1}^{3k}b_i$. Then it holds

(1) $S_1=S_2$ iff $\{x_1,...,x_k\}\cup\{y_1,...,y_k\}=\{b_1,...,b_{2k}\}$ and $\{z_1,...,z_k\}=\{b_{2k+1},...,b_{3k}\}$.

(2) $b_1+b_{2k}\leq b_{3k}$

(3) If $b_1+b_{2k}=b_{3k}$, then $\{b_1,b_{2k},b_{3k}\}=\{x_i,y_i,z_i\}$ for some $i$ and $S_1=S_2$.

(4) If $b_1+b_{2k+1}>b_{3k}$, then $S_1=S_2$.

Proof:
(1) From Lemma 1 we know that $S_1\leq S_2$. But from the proof of Lemma 1 it becomes clear that inequality can only be valid if one of the $x_i$ or the $y_i$ is found in the upper third and one of the $z_i$ in the lower two thirds of the $b_r$.

(2) It is clear that there must be at least one $x_i$ or one $y_i$ with $x_i\geq b_{2r}$ or $y_i\geq b_{2k}$. If $y_i\geq b_{2r}$ then $b_1+b_{2k}\leq x_i+y_i=z_i\leq b_{3k}$. Similarly, if $x_i\geq b_{2r}$.

(3) If $b_1+b_{2k}=b_{3k}$, equality holds in the chain of inequalities in the proof of (2). Thus $x_i=b_1,y_i=b_{2k},z_i=b_{3k}$, which proves the first part of the claim. Now let $j\in\{1,...,k\}$. We have $b_{3k}\geq z_j=x_j+y_j\geq b_1+y_j=b_{3k}-b_{2k}+y_j$ and therefore $y_j\leq b_{2k}$, and similarly $x_j\leq b_{2k}$. Thus $\{x_1,...,x_k\}\cup\{y_1,...,y_k\}=\{b_1,...,b_{2k}\}$ and $S_1=S_2$ follows from (1).

(4) Let $j\in\{1,...,k\}$. Then $b_{3k}\geq z_j=x_j+y_j\geq b_1+y_j>b_{3k}-b_{2k+1}+y_j$ and therefore \(y_j\lt b_{2k+1}\). Similarly $x_j\lt b_{2k+1}$. Thus $\{x_1,...,x_k\}\cup\{y_1,...,y_k\}=\{b_1,...,b_{2k}\}$ and $S_1=S_2$ follows from (1).
$\Box$

(2) and (4) provide further criteria to abort the recursive search in the search tree early.

If during the recursive search the case occurs that $S_1=S_2$, the search for triples $(x,y,z)$ can be limited to the cases where the sum $z$ is in the upper third and the two summands $x,y$ are in the lower two thirds of the list $(b_1,...,b_{3n})$ because of (1). This further shortened the runtime considerably. We have programmed a second search routine that handles this case. In this second routine, it is also no longer necessary to calculate and test the values $S_1$ and $S_2$.

Source code for the recursive search
C
// Recursive search for valid partitions in a sorted list of length 3*n
//   sum1 is the sum of the first two thirds of the entries of list[]
//   sum2 is the sum of the last third of the entries of list[]
void search(int list[3*Nmax], int n, int sum1, int sum2){
  int newlist[3*Nmax], newsum1, newsum2;
  int j, k;
 
  if(n == 0){
    solutioncounter++;	                    // Valid partition found
    printsolution();
    return;
  }
 
  if(list[0] + list[2*n-1] > list[3*n-1])
    return;                                 // abort search, cf. Lemma 2 (2)
 
  if(list[0] + list[2*n-1] == list[3*n-1]){
    if(sum1 < sum2)
      return;                               // abort search, cf. Lemma 2 (3)
 
    // triple found
    reduce(list, newlist, 2*n-1, 3*n-1, n); // delete triple from list
 
    solution[n-1][0] = list[0];             // add triple to solution
    solution[n-1][1] = list[2*n-1];
    solution[n-1][2] = list[3*n-1];
 
    search2(newlist, n-1);                  // search shortened list, switch to search2
    return;
  }
 
  if(list[0] + list[2*n] > list[3*n-1]){
    if(sum1 < sum2)
      return;                               // abort search, cf. Lemma 2 (4)
 
    search2(list, n);                       // switch to search2()
    return;
  }
 
  // searching for triplets (list[0] list[j] list[k])
  for(j=1, k=j+1; j<3*n-1; j++){
    for( ; k<3*n; k++){
      if(list[0] + list[j] == list[k]){     // new triple found
	reduce(list, newlist, j, k, n);     // delete triple from list
        // update of sum1 and sum2:
        if(k < 2*n){
          newsum1 = sum1 - list[0] - list[j] - list[k] + list[2*n];
          newsum2 = sum2 - list[2*n];
        }
        else if(j < 2*n){
          newsum1 = sum1 - list[0] - list[j];
          newsum2 = sum2 - list[k];
        }
        else{
          newsum1 = sum1 - list[0] - list[2*n-1];
          newsum2 = sum2 - list[j] - list[k] + list[2*n-1];
        }
        if(newsum1 <= newsum2){             // test abort criterion, cf. Lemma 1
                                            // test of newlist passed
          solution[n-1][0] = list[0];       // add triple to solution
          solution[n-1][1] = list[j];
          solution[n-1][2] = list[k];
          if(newsum1 < newsum2)
            search(newlist, n-1, newsum1, newsum2); // search shortened list
          else
            search2(newlist, n-1);          // search shortened list, switch to search2
        }
        k++;
	break;                              // next j
      }
 
      if(list[0] + list[j] < list[k])       // for this (j, k) and greater k
        break;                              // no solution is possible -> next j
    }
  }
}
 
//----------------------------------------------------------------------------------
 
// Recursive search for valid partitions in a sorted list of length 3*n
// - where the elements of the upper third of the list are known to be the sum
//   of two entries from the lower two thirds of the list
void search2(int list[3*Nmax], int n){
  int newlist[3*Nmax];
  int j, k;
 
  if(n == 0){
    solutioncounter++;	                    // Valid partition found
    printsolution();
    return;
  }
 
  if(list[0] + list[2*n-1] > list[3*n-1])
    return;                                 // abort search, cf. Lemma 2 (2)
 
  if(list[0] + list[2*n-1] == list[3*n-1]){
                                            // triple found, cf. Lemma 2 (3)
    reduce(list, newlist, 2*n-1, 3*n-1, n); // delete triple from list
 
    solution[n-1][0] = list[0];             // add triple to solution
    solution[n-1][1] = list[2*n-1];
    solution[n-1][2] = list[3*n-1];
 
    search2(newlist, n-1);                  // search shortened list
    return;
  }
 
  // searching for triplets (list[0] list[j] list[k])
  for(j=1, k=2*n; j<2*n; j++){
    for( ; k<3*n; k++){
      if(list[0] + list[j] == list[k]){     // new triple found
	reduce(list, newlist, j, k, n);     // delete triple from list
 
        solution[n-1][0] = list[0];         // add triple to solution
        solution[n-1][1] = list[j];
        solution[n-1][2] = list[k];
 
        search2(newlist, n-1);              // search shortened list
        k++;
	break;                              // next j
      }
 
      if(list[0] + list[j] < list[k])       // for this (j, k) and greater k
        break;                              // no solution is possible -> next j
    }
  }
}


Again, we have parallelized the calculation of $a(17)$ by specifying a triple $(1,y,y+1)$ and counting those partitions that contain $(1,y,y+1)$. The calculation for $y=2,3,...,50$ could then be done independently. Here are the results of the calculation. The calculation of the individual values took different lengths of time from about seven to sixty hours.
Complete list of results for a(17)
x	y	z	Number of partitions that contain the triple (x, y, z)
1	2	3	10,873,579,079
1	3	4	11,265,391,089
1	4	5	11,726,044,854
1	5	6	12,257,306,077
1	6	7	12,866,587,574
1	7	8	13,549,711,175
1	8	9	14,311,511,163
1	9	10	15,173,542,983
1	10	11	16,110,572,783
1	11	12	17,153,121,784
1	12	13	18,251,666,239
1	13	14	19,392,436,217
1	14	15	20,703,689,337
1	15	16	22,138,841,380
1	16	17	23,591,276,423
1	17	18	24,772,324,686
1	18	19	26,177,242,793
1	19	20	27,797,557,916
1	20	21	29,484,194,970
1	21	22	31,216,487,343
1	22	23	32,977,254,286
1	23	24	34,817,801,899
1	24	25	36,428,557,022
1	25	26	36,090,309,522
1	26	27	34,455,133,562
1	27	28	35,829,539,300
1	28	29	37,256,636,943
1	29	30	38,823,585,285
1	30	31	40,418,176,371
1	31	32	42,089,818,503
1	32	33	43,827,831,321
1	33	34	45,635,993,229
1	34	35	47,253,269,348
1	35	36	48,902,206,476
1	36	37	50,579,064,214
1	37	38	52,283,058,915
1	38	39	53,996,324,691
1	39	40	55,671,295,146
1	40	41	57,192,254,943
1	41	42	58,763,734,636
1	42	43	60,183,744,398
1	43	44	61,540,079,868
1	44	45	62,807,759,176
1	45	46	63,955,124,900
1	46	47	64,831,433,030
1	47	48	65,650,341,154
1	48	49	65,991,602,320
1	49	50	65,893,060,966
1	50	51	63,694,096,074
Sum			1,836,652,173,363

The total runtime on a single i9 processor would have taken 915 hours.

Calculating sequence element a'(43) of A002849

$a'(n)$ = Maximal number of disjoint subsets $\{X,Y,Z\}$ of $\{1, 2, ..., n\}$, each satisfying $X + Y = Z$.

The calculation of \(a'(43)\) was performed by removing the element \(r\) for \(r= 1,...,43\) from the set \(\{1,...,43\}\) and applying the search algorithm described above to these sets. \(a'(43)\) is then the sum of all 43 results. This gave $a'(43)=16.852.166.906$. The calculation took 13 hours.

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 1042
 
Aufrufstatistik des Artikels
Insgesamt 17 externe Seitenaufrufe zwischen 2020.05 und 2021.05 [Anzeigen]
DomainAnzahlProz
http://oeis.org847.1%47.1 %
https://oeis.org847.1%47.1 %
https://google.com15.9%5.9 %

Häufige Aufrufer in früheren Monaten
Insgesamt 10 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
202005-08 (6x)http://oeis.org/A108235
202101-05 (4x)https://oeis.org/

[Top of page]

"Mathematik: Calculating sequence element a(16) of OEIS A108235" | 7 Comments
The authors of the comments are responsible for the content.

Re: Calculating sequence element a(16) of OEIS A108235
von: AnnaKath am: So. 19. April 2020 09:32:35
\(\begingroup\)
Ein toller Erfolg!

Glückwunsch an euch alle,
AK.\(\endgroup\)
 

Re: Calculating sequence element a(16) of OEIS A108235
von: Slash am: So. 19. April 2020 13:06:59
\(\begingroup\)
Jetzt fehlt nur noch der Eintrag in die OEIS. 😉

EDIT: Jo, jetzt isser drin!

...und Glückwunsch natürlich!\(\endgroup\)
 

Re: Calculating sequence element a(16) of OEIS A108235
von: Kitaktus am: Di. 21. April 2020 20:31:39
\(\begingroup\)
Ich freue mich, dass ihr zu einem so guten Ende gekommen seid. Mein eigener Ansatz und meine Geduld reichten leider nur zur Berechnung von a(12) und a(13).
Es war schön, Euch -- meist als stiller Zuschauer, aber nicht nur -- auf dem Weg begleitet zu haben.\(\endgroup\)
 

Re: Calculating sequence element a(16) of OEIS A108235
von: StrgAltEntf am: Di. 21. April 2020 21:40:43
\(\begingroup\)
Hallo alle,

danke für die freundlichen Kommentare!

@Kitaktus: Mithilfe eines von Ixx verbesserten Codes berechnet mein Programm auf meinem alten Aldi-Rechner nun a(12) in nur noch 44 Sekunden und a(13) in 8,63 Minuten. Ich werde beizeiten den bisherigen Code hier im Artikel durch den neuen Code ersetzen.\(\endgroup\)
 

Re: Calculating sequence element a(16) of OEIS A108235
von: matroid am: Sa. 02. Mai 2020 21:00:50
\(\begingroup\)
Wow, auch noch a(17)!👍🏻👍🏻👍🏻

Ich gratuliere euch zu dieser tollen Gemeinschaftsleistung und bedanke mich bei StrgAltEntf besonders für die Dokumention des ganzen.

Schön, dass es euch gibt!

Es grüßt
euer Matroid\(\endgroup\)
 

Re: Calculating sequence element a(16) of OEIS A108235
von: hyperG am: Sa. 02. Mai 2020 23:03:54
\(\begingroup\)
Da immer mehr Fakten (neue OEIS-Glieder usw.) zur verwandten Folge A002849 zusammenkommen, habe ich einen neuen Beitrag Optimierung der Folge A002849 erstellt.\(\endgroup\)
 

Re: Calculating sequence element a(16) of OEIS A108235
von: hyperG am: Di. 12. Mai 2020 22:19:23
\(\begingroup\)
Neu:
A002849(44)
\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]