Mathematik: Calculating sequence element a(16) of OEIS A108235 Released by matroid on Sa. 18. April 2020 18:31:10 [Statistics]Written by StrgAltEntf - 1099 x read [Outline] Printer-friendly version -  Choose language 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) \sourceon 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 \sourceoff For example, $a(4)=8$, and there are the following eight partitions of set $\{1,2,...,12\}$. \sourceon 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) \sourceoff 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. \showon 246 lines of code \sourceon C \numberson #include #include #include #define Nmax 20 // maximum list length is 3*Nmax int N; // the current list length is 3*N long long int solutioncounter = 0; int solution[Nmax][3]; // collects triplets of a partition // only for the output int boundary[Nmax+1] = {1, 1, 1, 1, 1, 1, 1, 1, 100, 1000, 1000, 1000, 100000, 100000, 1000000, 1000000, 1000000, 100000, 100000, 100000, 100000}; //--------------------------------------------------------------------------- /* delete list[0], list[j] and list[k] from list[0]...list[3n-1] and check the reduced list Return value: 0, if (sum of the first two thirds entries of the new list) <= (sum of the last third entries of the new list) 1, else -> abort */ int reduce(int list[3*Nmax], int newlist[3*Nmax], int j, int k, int n){ int i, m = 0, sum1 = 0, sum2 = 0; for(i=1; i sum2) return 1; // -> abort else return 0; } //--------------------------------------------------------------------------- // Print a solution for your entertainment void printsolution(void){ int j; if(solutioncounter % boundary[N]) return; printf("No. %Ld ", solutioncounter); for(j=N-1; j>=0; j--) printf("(%d %d %d) ", solution[j][0], solution[j][1], solution[j][2]); printf("\n"); } //--------------------------------------------------------------------------- // Built-in-test // tests that no error has occurred // Return value: 0, if anything ok // 1, if error int builtintest(void){ int j, k, sum, test[3*Nmax+1]; for(j=1; j<=3*N; j++) test[j] = 0; for(j=0; j Nmax || N < 1){ printf("Invalid N = %d\n", N); return 1; } for(hlp=i=0; i<3*N; i++) hlp += i+1; if(hlp % 2){ printf("There is no valid partition of 1...3*N for N = %d\n", N); return 1; } if(ac == 5){ x = atoi(av[2]); y = atoi(av[3]); z = atoi(av[4]); printf("x = %d y = %d z = %d\n", x, y, z); if(x < 1 || x > 3*N){ printf("Invalid value x = %d\n", x); error = 1; } if(y < 1 || y > 3*N){ printf("Invalid value y = %d\n", y); error = 1; } if(z < 1 || z > 3*N){ printf("Invalid value z = %d\n", z); error = 1; } if((x == y) || (x + y != z)){ printf("x and y must be different and must add up to z"); error = 1; } if(error) return 1; if(y < x){ hlp = y; y = x; x = hlp; } printf("Find %d disjoint triplets from 1...%d that contain the triple (%d %d %d)\n", N, 3*N, x, y, z); // create initial list in which the triple (x y z) is missing for(j=0, i=1; iLemma 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. \showon Complete list of results \sourceon 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 \sourceoff \showoff 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}$. \sourceon 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 \sourceoff \sourceon 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 \sourceoff 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$. \showon Source code for the recursive search \sourceon 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 } } } \sourceoff \showoff 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. \showon Complete list of results for a(17) \sourceon 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 \sourceoff \showoff 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.  [Show outline only] Get link to this article   Printer-friendly version -  Choose language      Comments  Für diesen Artikel gibt es keine pdf-Datei

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

 Aufrufzähler 1099 Aufrufstatistik des ArtikelsInsgesamt 25 externe Seitenaufrufe zwischen 2020.05 und 2021.09 [Anzeigen]Häufige Aufrufer in früheren MonatenInsgesamt 16 häufige Aufrufer [Anzeigen][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 A108235von: AnnaKath am: So. 19. April 2020 09:32:35 Ein toller Erfolg! Glückwunsch an euch alle, AK.

 Re: Calculating sequence element a(16) of OEIS A108235von: Slash am: So. 19. April 2020 13:06:59 Jetzt fehlt nur noch der Eintrag in die OEIS. 😉 EDIT: Jo, jetzt isser drin! ...und Glückwunsch natürlich!

 Re: Calculating sequence element a(16) of OEIS A108235von: Kitaktus am: Di. 21. April 2020 20:31:39 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.

 Re: Calculating sequence element a(16) of OEIS A108235von: StrgAltEntf am: Di. 21. April 2020 21:40:43 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.

 Re: Calculating sequence element a(16) of OEIS A108235von: matroid am: Sa. 02. Mai 2020 21:00:50 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

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

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

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]