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] 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)
 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 0n 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)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.

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.

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 jfor(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 jfor(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$.

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.

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.

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 1042 Aufrufstatistik des ArtikelsInsgesamt 17 externe Seitenaufrufe zwischen 2020.05 und 2021.05 [Anzeigen]Häufige Aufrufer in früheren MonatenInsgesamt 10 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]