Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Wann ist eine Zahl "groß"?

47 views
Skip to first unread message

neu...@tuhh.de

unread,
Jul 18, 2022, 3:17:30 AM7/18/22
to
Eine einfach zu formulierende kombinatorische Frage, für deren Beantwortung mit einem "unglücklichen" Computerprogramm das Alter des Universums nicht ausreichen würde.

Aufgabe: Man betrachte die Potenzmenge von IN_n= {1, 2, 3, ... n},
und bilde jeweils die Summe der Elemente ihrer Teilmengen.

Sei n= 3 oder 30 oder 300
Frage, wieviel Teilmengen haben eine Summe die durch 3 teilbar ist?
Für 300 ist die Anzahl schon ganz schön groß!
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Ein kleines Python Programm:
n=300
w=1
for i in range(1, n//3+1):
w= 8*w -pow(2,i+1)
print(w)

Siehe auch https://youtu.be/dg_YgkOUb14

neu...@tuhh.de

unread,
Jul 21, 2022, 5:51:02 AM7/21/22
to
Wenn man für n, Vielfaches von 3, die Iteration auflöst, erhält man als Summe:
8^n//3 *(2 +4^n//3)/(3 *4^n//3) oder für n=300: (2**300 + 2**101) / 3

VG Siggi N.

Klaus-R. Loeffler

unread,
Jul 22, 2022, 4:10:22 AM7/22/22
to
... oder allgemeiner erhält man für die Menge {1,2,3,...,k*p} mit Primzahl p (p > 2) als gesuchte Anzahl 1/p * (2^(k*p) + (p-1) *2^k) - wie der schöne von dir angegebene Videoclip zeigt.

Gruß, Klaus-R.

Rainer Rosenthal

unread,
Jul 22, 2022, 5:11:36 AM7/22/22
to
Jupp, wirklich sehr schönes Video, danke für den Tipp!

Gruß,
Rainer R.


neu...@tuhh.de

unread,
Jul 22, 2022, 11:09:14 AM7/22/22
to
Hallo Klaus-R.
Das wäre ja ein sehr schönes Ergebnis, aber wäre dann nicht:
(2^15 +2*2^5)/3= 174784 gleich (2^15 +4*2^3)/5= 104864 ?
VG Siggi N.

Klaus-R. Loeffler

unread,
Jul 22, 2022, 12:11:16 PM7/22/22
to
Hallo Siggi,
mal ganz abgesehen davon, dass (2^15 +2*2^5)/3 nicht gleich 174784, sondern gleich 10944 ist, wie auch (2^15 +4*2^3)/5 nicht gleich 104864, sondern gleich 6560 ist: Warum sollten denn die gleichen Werte herauskommen? Gemeinsam ist nur die Menge {1,2,32,...,15}, aber das erste ist die Formel für die Anzahl der Teilmengen mit durch 3 teilbarer Elementesumme, das zweite für die Anzahl der Teilmengen mit durch 5 teilbarer Elementesumme.
Gruß, Klaus-R.

neu...@tuhh.de

unread,
Jul 22, 2022, 2:10:32 PM7/22/22
to
Ja, natürlich. :-(
Ich habe den Verdacht, da habe ich mich (mal wieder) verdacht! ;-) Pardon! Peinlich - ich eben!
Und außerdem im Kopf verrechnet 2^15= 32*1024. Ich hatte gerechnet 2^15= 512*1024 - auch nicht besser!
Gruß Siggi N.
0 new messages