Skip to content

Eine endliche Menge verschiedener positiver Zahlen ist speziell, wenn jede ganze Zahl in der Menge die Summe aller ganzen Zahlen innerhalb der Menge teilt.

Lösung:

Hier ist eine Teilantwort. Es genügt natürlich zu zeigen, dass $[n]=lbrace 1,2,3,ldots,n rbrace$ ist in einem speziellen Set für jeden enthalten $n$, da jede endliche Menge von positiven ganzen Zahlen in einigen enthalten ist $[n]$. Ich beschreibe unten einen Algorithmus, den ich überprüft habe, um an jedem zu funktionieren $[n]$ zum $8 leq n leq 20$.

Hier ist der Algorithmus. Es beginnt mit einer endlichen Anfangsmenge $A$ von positiven ganzen Zahlen, die wir um ein Element nach dem anderen erhöhen, bis wir eine spezielle Menge treffen.

Schritt 1. Berechne die Summe $s=sum_{ain A} a$.

Schritt 2. Berechnen $X_1=lbrace ain A | anotmid s rbrace$. Wenn $X_1$ ist leer, dann $A$ ist besonders und wir sind fertig. Ansonsten lass $x_1$ sei das kleinste Element in $X_1$.

Schritt 3. Berechnen $X_2=lbrace ain A | amid s rbrace$ (so $X_2$ ist die Ergänzung von $X_1$ in $A$). Bezeichne mit $l$ die lcm der Elemente von $A$ (bestimmtes, $l=1$ wenn $X_2$ ist leer).

Schritt 4. Lass $M$ sei die kleinste ganze Zahl, die die folgenden drei Bedingungen erfüllt: (1) sie ist größer als das größte Element von $A$, (2) es ist teilbar durch $l$, (3) die Summe $s+M$ ist teilbar durch $x_1$ (beachten Sie, dass die Kongruenzbedingungen konstruktiv kompatibel sind).

Schritt 5. Ersetzen $A$ mit $A'=Acup lbrace M rbrace$ und kehren Sie zu Schritt 1 zurück.

Wann $n=50$ zum Beispiel erzeugt der Algorithmus schließlich die 99-Elemente-Spezialmenge

$$
[50] Cup lbrace 1275, 2550, 30600, 35700, 142800, 2.142.000, 28.274.400, 30.630.600, 1102701600, 25607181600, 53542288800, 2248776129600, 69872686884000, 72201776446800, 5198527904169600, 213717258282528000, 9200527969062830400, 433301055304911393600, 2656323860782282891200, 12396178016983986825600, 30990445042459967064000, 464856675636899505960000, 511342343200589456556000, 5113423432005894565560000, 6136108118407073478672000, 269988757209911233061568000, 1129043893786901520075648000, 29637402211906164901985760000, 31048707079139791802080320000, 1241948283165591672083212800000, 24776868249153553858060095360000, 469456451036593652047454438400000, 8424135204712208311740432422400000, 142714761115124470222426149273600000, 2274516505272296244169916754048000000, 33966113145399623912937423527116800000, 473099433096637618787342684841984000000, 6113900366171932304328736234881024000000, 72857312696882193293250773465665536000000, 794807047602351199562735710534533120000000, 78685897712632768756710835342918 77888000000, 69943020189006905561520742527038914560000000, 550801283988429381296975847400431452160000000, 3776923090206372900322120096460101386240000000, 22032051359537175251879033896017258086400000000, 105753846525778441209019362700882838814720000000, 396576924471669154533822610128310645555200000000, 1057538465257784412090193627008828388147200000000, 1586307697886676618135290440513242582220800000000 rbrace $$

Sagen wir, wir bekommen ein Set $S$, mit Summe $s$. Wir nehmen an, dass $S$ besteht nicht nur aus Potenzen von $2$; Wenn dies der Fall ist, können wir einfach die Zahl zum Set hinzufügen $3$. Lassen Sie zuerst $a$ groß genug sein, damit $2^a > 2s$, Bedeutung $2^a - s not in S$, und definieren $S' = S cup {2^a - s}$, so $S'$ hat Summe $2^a$. Lassen $n$ sei das Produkt aller Elemente von $S'$, und lass $b$ groß genug sein, damit $2^b > n$.

Wir konstruieren nun eine Menge $S''$ enthält $S'$ mit Summe 2^{a+b} n$, von denen sich alle Elemente teilen 2^{a+b} n$. Schon seit $n-1$ ist weniger als $2^b$, mit seiner binären Darstellung können wir ausdrücken $n-1$ als Summe verschiedener Elemente von ${1, 2, 4, dots, 2^{b-1}}$, und so können wir ausdrücken $2^a(n-1)$ als Summe verschiedener Elemente von ${2^a, 2^{a+1}, dots, 2^{a+b-1}}$. Lassen $T$ die Teilmenge der Elemente sein, die in der letzteren Summe erscheinen. Dann definiere
$$S'' = S'cup Tcup{2^an, 2^{a+1}n, dots, 2^{a+b-1}n}.$$
Wie Sie überprüfen können, sind alle Elemente von $S''$ Teilen 2^{a+b} n$, und die drei Mengen in dieser Vereinigung sind disjunkt (da $n$ ist keine Macht von $2$), und somit $S''$ hat Summe $2^a + 2^a(n-1) + (2^{a+b} n - 2^an) = 2^{a+b} n$, Bedeutung $S''$ ist besonders.

TL;DR: Mit jedem nicht-speziellen Set $A$ von verschiedenen ganzen Zahlen sei die Summe der Elemente $s$. Die $operatorname{lcm}$ aller Elemente von $A$, nennen $q$, kann immer eine praktische Nummer werden, ruf an $m$, durch Multiplizieren mit einer geeigneten ganzen Zahl. Es existiert dann eine Menge $B$ von verschiedenen Vielfachen von $s$, wobei jedes Element geteilt durch $s$ ist ein Faktor von $m$ und die Summe der Elemente ist $(m - 1)s$. Dann $A tasse B$ ist ein besonderes Set.


Wenn die endliche Menge positiver ganzer Zahlen selbst eine spezielle Menge ist, können Sie nur sie verwenden. Insbesondere bildet jede einzelne ganze Zahl selbst eine spezielle Menge, also wenn $n$ ist die Anzahl der Elemente, die jede nicht-spezielle Menge hat $n gt 1$. Auch in diesen Fällen muss die Menge sein $A = {a_i}_{i=1}^{n}$ und lass

$$s = sum_{i=1}^{n}a_i tag{1}label{eq1A}$$

Erwägen Sie, ein Vielfaches von hinzuzufügen $s$ um ein besonderes Set zu bilden. Zum Beispiel, wenn $A = {2,3}$, dann $s = 5$, mit $2(5) = 10$ und $3(5) = 15$ ausreichen, um einen speziellen Satz mit einer neuen Summe von . zu bilden $30 = (2)(3)5$. Im Allgemeinen muss die neue Gesamtsumme mindestens einen Faktor von haben $operatorname{lcm}$, nennen $q$, von allen $a_i$, Plus $s$ muss die Summe ebenfalls teilen, kann aber bei Bedarf mehr Faktoren haben.

Für einige $j ge 1$, Lassen $B = {b_i(s)}_{i=1}^{j}$, wo $b_i$ unterschiedliche positive ganze Zahlen sind, eine Menge von Vielfachen von $s$ die hinzugefügt werden, um zu bekommen

$$S_t = s + sum_{i=1}^{j}b_i(s) = s(1 + sum_{i=1}^{j}b_i) tag{2}label{eq2A}$ $

wo $S_t$ ist die Gesamtsumme der Elemente in $A tasse B$. Als nächstes lassen

$$m = 1 + sum_{i=1}^{j}b_i tag{3}label{eq3A}$$

Du musst haben $b_i mid m ; für alle ; 1 le i le j$, Plus $q mid ms$.

Beachten Sie, dass eine praktische Zahl ist

... eine positive ganze Zahl $n$ so dass alle kleineren positiven ganzen Zahlen als Summen verschiedener Teiler von dargestellt werden können $n$.

Dies bedeutet, wenn $m$ ist eine praktische Zahl, es gibt verschiedene $b_i$, die alle Faktoren von . sind $m$, das gibt $sum_{i=1}^{j}b_i = m - 1$. In Bezug auf die Anforderungen, eine praktische Zahl zu sein, heißt es im Abschnitt Charakterisierung von praktischen Zahlen:

Eine positive ganze Zahl größer als eins mit Primfaktorzerlegung $n=p_1^{alpha_1}ldots p_k^{alpha_k}$ (mit den Primzahlen in sortierter Reihenfolge $p_1 lt p_2 lt dots lt p_k$) ist genau dann praktisch, wenn jeder seiner Primfaktoren $p_{i}$ ist klein genug für $p_{i}-1$ eine Darstellung als Summe kleinerer Teiler zu haben. Damit dies wahr ist, ist die erste Primzahl $p_{1}$ muss gleich sein $2$ und für jeden $i$ von $2$ zu $k$, jede aufeinanderfolgende Primzahl $p_{i}$ muss der Ungleichung gehorchen
$$p_{i} leq 1 + sigma(p_{1}^{alpha_{1}}p_{2}^{alpha_{2}}dots p_{i-1}^{alpha_{ i-1}}) = 1 + prod_{j=1}^{i-1}frac{p_{j}^{alpha_{j} + 1} - 1}{p_{j} - 1} $$
wo $sigma(x)$ bezeichnet die Summe der Teiler von $x$.

Wie bereits erwähnt, können Sie bei Bedarf weitere Faktoren hinzufügen, z. B. nur eine ausreichend große Potenz von $2$ oder alternativ ein oder mehrere einzelne oder mehrere Faktoren von beliebigen Primzahlen bis zur größten erforderlichen Primzahl. So können Sie in jedem Fall ganz einfach ein $m$ was eine praktische Zahl ist und die anderen Bedingungen erfüllt, was zu $A tasse B$ einen speziellen Satz bilden.

Click to rate this post!
[Total: 0 Average: 0]



Anderer Beitrag

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.