Bearbeiten von: Abschnitt [Änderungshistorie]
Zeilenumbrüche automatisch mache ich selbst mit HTML

 Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.  Nachricht zur Änderung: Input assistance tools (JavaScript): [Link extern intern] [MathML?] [?] [fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?][Link zurück zum Artikelabschnitt]

 Vorschau: Neuer Abschnitt in Calculating sequence element f(16) of 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.

All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 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]