Partitionen einer Zahl

02.02.2021, 22:02

Dopap

Partitionen einer Zahl

zu einer beliebigen natürlichen Zahl z soll die Anzahl der Partitionen unter der Verwendung von Elementen der Menge
$\begin{eqnarray*} \mathbb P =\{1,5,10,25,50, 100\} \end{eqnarray*}$ bestimmt werden. $\begin{eqnarray*} |\mathbb P|= \end{eqnarray*}$ 6
Die algebraische CAS Lösung mit Produkten von Polynomen als Koeffizient von $\begin{eqnarray*} x^z \end{eqnarray*}$ wird rasch unhandlich.
Als Programm in C++ geht es erstaunlich weit wie schon HAL9000 zeigen konnte ---> Münzwechsler.

Diese Identität gilt es mMn auf einem möglichen Weg zu einer Formel zu bearbeiten:

(*) $\begin{eqnarray*} \quad{\color{blue}(1+x +x^2 +x^3 +x^4 +\cdots)}\cdot(1+x^{5} +x^{10} + x^{15}+x^{20}+\cdots)\cdot (1+x^{10 } +x^{20} + x^{30}+x^{40}+\cdots)\cdot<br /> \end{eqnarray*}$
$\begin{eqnarray*} \cdot (1+x^{25} +x^{50} + x^{75}+x^{100}+\cdots)\cdot (1+x^{50 } +x^{100} + x^{150}+x^{200}+\cdots)\cdot (1+x^{100 } +x^{200} + x^{300}+x^{400}+\cdots) = \end{eqnarray*}$

$\begin{eqnarray*} \frac{{\color{blue}1}}{{\color{blue}\bigg( 1-x\bigg)}\left(1-x^5\right)\left(1-x^{10}\right)\left(1-x^{25}\right)\left(1-x^{50}\right)\left(1-x^{100}\right)} \end{eqnarray*}$

Für die Partitionen-Anzahl von z.B. z=4711 müsste man beim algebraischen Weg die linke Seite "ausmultiplizieren",
ordnen und nach dem Koeffizienten von $\begin{eqnarray*} x^{4711} \end{eqnarray*}$ suchen.
Viel Spass dabei. Das here Ziel ist, die beide Seite so zu bearbeiten bis eine Formel dasteht. Viel Feind viel Ehr'
Ob das geht ist offen, wichtig ist, dass das Geschriebene zumindest nicht falsch ist. :-)

die blaue Identität könnte man doch 6-1=5 mal differenzieren:

$\begin{eqnarray*} \Rightarrow \quad 1+6x+21x^2+56x^3+126x^4+\cdots=\frac{1}{(1-x)^6} \end{eqnarray*}$ oder vermutlich nützlicher, die 6 ins Spiel bringt:

$\begin{eqnarray*} \binom{5}{6-1}+\binom{6}{6-1}x+\binom{7}{6-1}x^2+\binom{8}{6-1}x^3+\binom{9}{6-1}x^4+\cdots=\frac{1}{\bigg(1-x\bigg)^6} \end{eqnarray*}$

oder allgemein $\begin{eqnarray*} \binom{N-1}{N-1}+\binom{N}{N-1}x+\binom{N+1}{N-1}x^2+\binom{N+2}{N-1}x^3+\binom{N+3}{N-1}x^4+\cdots=\left(1-x\right)^{-N} \end{eqnarray*}$

03.02.2021, 21:18

Dopap

Auf diesen Beitrag antworten »

nur mit Latex Laptop und einer Hand zieht sich das...

--------------------

$\begin{eqnarray*} \color{blue}\frac {1}{1-x} \end{eqnarray*}$ kann man mit $\begin{eqnarray*} (1+x+x^2+x^3+x^4) \end{eqnarray*}$ erweitern zu $\begin{eqnarray*} \frac {1\cdot( 1+x+x^2+x^3+x^4) }{(1-x)\cdot (1+x+x^2+x^3+x^4)} \end{eqnarray*}$ =

$\begin{eqnarray*} \frac{1+x+x^2+x^3+x^4}{(1+x+x^2+x^3+x^4)-(x+x^2+x^3+x^4-x^5)}=\color{blue}\frac{1+x+x^2+x^3+x^4}{1-x^5} \end{eqnarray*}$

in (*) eingesetzt und etwas umgeformt erhält man als rechte Seite von (*)

$\begin{eqnarray*} [\cdots] ={\color{blue}\frac{1+x+x^2+x^3+x^4} {(1-x^5)}} \cdot\frac {1}{1-x^5} \cdot\frac {1}{1-(x^5)^2}\cdot\frac {1}{1-(x^5)^5}\cdot\frac {1}{1-(x^5)^{10}}\cdot\frac {1}{1-(x^5)^{10}} \end{eqnarray*}$

oder mittels $\begin{eqnarray*} q:=x^5 \end{eqnarray*}$

$\begin{eqnarray*} [\cdots] =(1+x+x^2+x^3+x^4)\cdot \frac {1} {(1-q)} \cdot \frac {1} {(1-q)}\cdot\frac {1} {(1-q^2)} \cdot \frac {1} {(1-q^5)}\cdot {\color{red}\frac {1} {(1-q^{10})}}\cdot \frac {1} {(1-q^{20})} \end{eqnarray*}$

und den roten Faktor umgeschrieben:

$\begin{eqnarray*} {\color{red} \frac {1} {1-q^{10}}}= \frac{1+q^{10}} {1-(q^{10})^2}=\frac{1+q^{10}} {1-q^{20}}<br /> \end{eqnarray*}$

03.02.2021, 22:16

HAL 9000

Auf diesen Beitrag antworten »

Eigentlich nicht so schwer - weiß gar nicht, warum ich im anderen Thread nicht dran gedacht habe: Bilde die komplexe Partialbruchzerlegung der rechten Seite von

$\begin{eqnarray*} \sum_{k=0}^{\infty} a_kx^k = \frac{1}{\left(1-x\right)\left(1-x^5\right)\left(1-x^{10}\right)\left(1-x^{25}\right)\left(1-x^{50}\right)\left(1-x^{100}\right)} \end{eqnarray*}$ .

Jeden einzelnen Summand dieser PBZ hat die Struktur $\begin{eqnarray*} \frac{A}{\left(1-zx\right)^m} \end{eqnarray*}$ mit irgendeiner Einheitswurzel $\begin{eqnarray*} z \end{eqnarray*}$ von 1. Nun ist

$\begin{eqnarray*} \frac{A}{\left(1-zx\right)^m} = \sum_{k=0}^{\infty} A\cdot\binom{k+m-1}{m-1}z^k x^k \end{eqnarray*}$

die zugehörige Potenzreihe. Diese Summanden $\begin{eqnarray*} A\cdot\binom{k+m-1}{m-1}z^k \end{eqnarray*}$ nun über alle in der PBZ auftretenden Tripel $\begin{eqnarray*} (z,m,A) \end{eqnarray*}$ aufaddieren bekommt man Koeffizient $\begin{eqnarray*} a_k \end{eqnarray*}$ , d.h. dessen explizite (!) Darstellung. Na dann, fröhliche Bastelei!

04.02.2021, 10:10

Dopap

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
... Na dann, fröhliche Bastelei!

Du machst mir damit an Deinem 10. Jahrestag nicht gerade Mut :-(

Komplexe PBZ ist schon ein Weilchen her ( genauer > 40 Jahre ) und möchte jetzt erst ein mal versuchen,
ob es auf dem eingeschlagenen Weg irgendwie weiter geht.
Beim großen Fermat hat es bekanntlicher weise auch eine beträchtliche Zeit gedauert ... Lol

04.02.2021, 10:28

HAL 9000

Auf diesen Beitrag antworten »

Ich will es mal am einfachen Beispiel $\begin{eqnarray*} \sum_{k=0}^{\infty} a_kx^k = \frac{1}{\left(1-x\right)\left(1-x^3\right)} \end{eqnarray*}$ demonstrieren (also Summe aus 1ct- und 3ct-Stücken):

$\begin{eqnarray*} \frac{1}{\left(1-x\right)\left(1-x^3\right)} = \frac{1}{3(1-x)} + \frac{1}{3(1-x)^2} + \frac{3+\sqrt{3}i}{18\left(1-\frac{-1-\sqrt{3}i}{2}x\right)} + \frac{3-\sqrt{3}i}{18\left(1-\frac{-1+\sqrt{3}i}{2}x\right)} \end{eqnarray*}$

Damit ist dann

$\begin{eqnarray*} a_k = \frac{1}{3} + \frac{k+1}{3} + \frac{3+\sqrt{3}i}{18} \left(\frac{-1-\sqrt{3}i}{2}\right)^k + \frac{3-\sqrt{3}i}{18}\left(1-\frac{-1+\sqrt{3}i}{2}\right)^k \end{eqnarray*}$

Könnte man jetzt noch "reell" machen, d.h. mit Sinus/Kosinus schreiben:

$\begin{eqnarray*} a_k = \frac{k+2}{3} + \frac{1}{3} \cos\left(\frac{2\pi}{3}k\right) + \frac{\sqrt{3}}{9} \sin\left(\frac{2\pi}{3}k\right) \end{eqnarray*}$ .

Musst du jetzt "nur" noch analog auf $\begin{eqnarray*} \frac{1}{\left(1-x\right)\left(1-x^5\right)\left(1-x^{10}\right)\left(1-x^{25}\right)\left(1-x^{50}\right)\left(1-x^{100}\right)} \end{eqnarray*}$ anwenden. smile

Es lässt sich immerhin schon einiges sagen zu diesem $\begin{eqnarray*} a_k \end{eqnarray*}$ aufgrund dieser Linearkombinationen solcher Werte $\begin{eqnarray*} A\cdot\binom{k+m-1}{m-1}z^k \end{eqnarray*}$ :

1) Aufgrund des für Einheitswurzeln geltenden $\begin{eqnarray*} |z|=1 \end{eqnarray*}$ liegt bei $\begin{eqnarray*} a_k \end{eqnarray*}$ kein exponentielles, sondern nur polynomiales Wachstum vor, und zwar bei deinem Problem vom Grad 5, der nur erreicht wird für den Summanden für $\begin{eqnarray*} m=6,z=1 \end{eqnarray*}$ .

2) All die anderen Summanden sind Polynome vom Grad <5 und verknüpft mit irgendwelchen Sinus/Kosinusfaktoren, die lokale Schwankungen um die Haupttrendfunktion vom Grad 5 (aus 1) ) repräsentieren. Für $\begin{eqnarray*} k\to\infty \end{eqnarray*}$ verblasst deren (relativer) Anteil natürlich immer mehr.

04.02.2021, 19:39

Dopap

Auf diesen Beitrag antworten »

sieht gepflegt aus, muss das im Blick behalten ...

---------------------------------------

$\begin{eqnarray*} [\cdots] =(1+x+x^2+x^3+x^4)\cdot \frac {1} {(1-q)} \cdot \frac {1} {(1-q)}\cdot\frac {1} {(1-q^2)} \cdot \frac {1} {(1-q^5)}\cdot {\color{red}\frac {1} {(1-q^{10})}}\cdot \frac {1} {(1-q^{20})} \end{eqnarray*}$

und den roten Faktor umgeschrieben:

$\begin{eqnarray*} {\color{red} \frac {1} {1-q^{10}}}= \frac{1+q^{10}} {1-(q^{10})^2}=\frac{1+q^{10}} {1-q^{20}}<br /> \end{eqnarray*}$ eingesetzt und mit $\begin{eqnarray*} (1+q^5+q^{10}+q^{15}) \end{eqnarray*}$ erweitert folgt:

$\begin{eqnarray*} [\cdots] =(1+x+x^2+x^3+x^4)\cdot \frac {1} {(1-q)} \cdot \frac {1} {(1-q)}\cdot\frac {1} {(1-q^2)}\, \cdot \, \bigg(\frac {1} {(1-q^5)}\cdot \frac {(1+q^{10})(1+q+q^5+q^{10}+q^{15})} {(1-q^{20})(1+q^5+q^{10}+q^{15})}\bigg)\,\cdot \frac{1+q^{10}} {1-q^{20}}\cdot\, \frac {1}{1-q^{20}} \end{eqnarray*}$

und die große Klammer ergibt:

$\begin{eqnarray*} \bigg(\bigg)=\frac {1+q^5+q^{10}+q^{15}}{1-q^{20}} \end{eqnarray*}$

und insgesamt damit

$\begin{eqnarray*} [\cdots] =(1+x+x^2+x^3+x^4)\cdot \frac {1} {(1-q)} \cdot \frac {1} {(1-q)}\cdot\frac {1} {(1-q^2)}\, \cdot \, \bigg(\frac {1+q^5+q^{10}+q^{15}) } { 1-q^ {20} }\bigg)\,\cdot \frac{1+q^{10}} {1-q^{20}}\cdot\, \frac {1}{1-q^{20}} \end{eqnarray*}$
das Latex nervt, reicht jetzt

04.02.2021, 19:54

HAL 9000

Auf diesen Beitrag antworten »

Ich frage mich, ob deine Hin- und Herumformerei der Kreisteilungspolynome irgendeinem Ziel folgt. Falls ja, bin ich wohl zu blind, es zu erkennen. smile

04.02.2021, 20:02

URL

Auf diesen Beitrag antworten »

Immerhin habe ich jetzt den Dunst einer Ahnung, wie in einer Anzahlformel trigonometrische Funktionen auftauchen können smile

05.02.2021, 00:35

Dopap

Auf diesen Beitrag antworten »

Idee; jetzt stehen 2 gleiche Nenner rechts und man könnte noch einen weiteren ( blauen) Bruch

$\begin{eqnarray*} [\cdots] =(1+x+x^2+x^3+x^4)\cdot \frac {1} {(1-q)} \cdot \frac {1} {(1-q)}\cdot{\color {blue}\frac {1} {(1-q^2)}}\, \cdot \, \bigg(\frac {1+q^5+q^{10}+q^{15}) } { 1-q^ {20} }\bigg)\,\cdot \frac{1+q^{10}} {1-q^{20}}\cdot\, \frac {1}{1-q^{20}} \end{eqnarray*}$

auf ähnliche weise

$\begin{eqnarray*} {\color {blue}\frac {1} {(1-q^2)}}= \frac {1+q^2+q^4+q^6+q^8+q^{10}+q^{12}+q^{14}+q^{16}+q^{18}}{1-q^{20}} \end{eqnarray*}$

auf denselben Nenner bringen. $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$

$\begin{eqnarray*} [\cdots] =(1+x+x^2+x^3+x^4)\cdot \left(\frac {1} {(1-q)}\right)^2 \cdot\frac {1+q^2+q^4+ \cdots +q^{18}}{1-q^{20}} \cdot \, \frac {1+q^5+q^{10}+q^{15}) } { 1-q^ {20} }\,\cdot \frac{1+q^{10}} {1-q^{20}}\cdot\, \frac {1}{1-q^{20}} \end{eqnarray*}$

und auch noch die doppelten und zugleich 1. quadratischen Bruch derart verarzten:

$\begin{eqnarray*} [\cdots] =(1+x+x^2+x^3+x^4)\cdot\left(\frac {\sum_{j=0}^{19} q^j} {1-q^{20}}\right)^2 \cdot\frac {1+q^2+q^4+ \cdots +q^{18}}{1-q^{20}} \cdot \, \frac {1+q^5+q^{10}+q^{15}) } { 1-q^ {20} }\,\cdot \frac{1+q^{10}} {1-q^{20}}\cdot\, \frac {1}{1-q^{20}} \end{eqnarray*}$ oder

$\begin{eqnarray*} [\cdots] =(1+x+x^2+x^3+x^4)\cdot\left(\sum_{j=0}^{19} q^j\right)^2 \cdot \sum_{j=0}^9q^{2j} \cdot \sum_{j=0}^3 q^{5j} \cdot (1+q^{10})\cdot \frac {1}{(1-q^{20})^6} \end{eqnarray*}$

der Weg ist das Ziel ...

05.02.2021, 08:53

HAL 9000

Auf diesen Beitrag antworten »

Ok, jetzt verstehe ich langsam, was du vorhast: All die Nennerfaktoren $\begin{eqnarray*} \left(1-x^m\right) \end{eqnarray*}$ sind Teiler von $\begin{eqnarray*} \left(1-x^{100}\right) \end{eqnarray*}$ . Jetzt erweiterst du die alle (bis auf den letzten, wo das gar nicht nötig ist) und bekommst

$\begin{eqnarray*} \frac{1}{\left(1-x\right)\left(1-x^5\right)\left(1-x^{10}\right)\left(1-x^{25}\right)\left(1-x^{50}\right)\left(1-x^{100}\right)} = \frac{p(x)}{\left(1-x^{100}\right)^6} \end{eqnarray*}$

mit einem (mit moderatem Aufwand) berechenbaren Polynom $\begin{eqnarray*} p(x) \end{eqnarray*}$ (vom Grad 409 übrigens), und erhältst insgesamt die Reihe $\begin{eqnarray*} \sum_{k=0}^{\infty} a_kx^k = p(x) \sum_{r=0}^{\infty} \binom{r+5}{5} x^{100r} \end{eqnarray*}$ .

Das ermöglicht dann zwar keine "geschlossene" Formel für die $\begin{eqnarray*} a_k \end{eqnarray*}$ , sondern eine mit 100 Fällen für die Indizes $\begin{eqnarray*} k\bmod 100 \end{eqnarray*}$ , aber dafür ist jeder der Fälle schön reell und in einer übersichtlichen Formel mit maximal 5 Summanden möglich. Das ermöglicht es nun, ein einzelnes $\begin{eqnarray*} a_k \end{eqnarray*}$ für einen sehr großen Index $\begin{eqnarray*} k \end{eqnarray*}$ unmittelbar auszurechnen - Gratulation, deine Beharrlichkeit hat sich ausgezahlt. Freude

Ich geb mal noch ungefiltert per Copy+Paste an, was MuPad für p(x) ermittelt hat:

code:

1:

x^409 + x^408 + x^407 + x^406 + x^405 + 2*x^404 + 2*x^403 + 2*x^402 + 2*x^401 + 2*x^400 + 4*x^399 + 4*x^398 + 4*x^397 + 4*x^396 + 4*x^395 + 6*x^394 + 6*x^393 + 6*x^392 + 6*x^391 + 6*x^390 + 9*x^389 + 9*x^388 + 9*x^387 + 9*x^386 + 9*x^385 + 13*x^384 + 13*x^383 + 13*x^382 + 13*x^381 + 13*x^380 + 18*x^379 + 18*x^378 + 18*x^377 + 18*x^376 + 18*x^375 + 24*x^374 + 24*x^373 + 24*x^372 + 24*x^371 + 24*x^370 + 31*x^369 + 31*x^368 + 31*x^367 + 31*x^366 + 31*x^365 + 39*x^364 + 39*x^363 + 39*x^362 + 39*x^361 + 39*x^360 + 50*x^359 + 50*x^358 + 50*x^357 + 50*x^356 + 50*x^355 + 62*x^354 + 62*x^353 + 62*x^352 + 62*x^351 + 62*x^350 + 77*x^349 + 77*x^348 + 77*x^347 + 77*x^346 + 77*x^345 + 93*x^344 + 93*x^343 + 93*x^342 + 93*x^341 + 93*x^340 + 112*x^339 + 112*x^338 + 112*x^337 + 112*x^336 + 112*x^335 + 134*x^334 + 134*x^333 + 134*x^332 + 134*x^331 + 134*x^330 + 159*x^329 + 159*x^328 + 159*x^327 + 159*x^326 + 159*x^325 + 187*x^324 + 187*x^323 + 187*x^322 + 187*x^321 + 187*x^320 + 218*x^319 + 218*x^318 + 218*x^317 + 218*x^316 + 218*x^315 + 252*x^314 + 252*x^313 + 252*x^312 + 252*x^311 + 252*x^310 + 287*x^309 + 287*x^308 + 287*x^307 + 287*x^306 + 287*x^305 + 325*x^304 + 325*x^303 + 325*x^302 + 325*x^301 + 325*x^300 + 364*x^299 + 364*x^298 + 364*x^297 + 364*x^296 + 364*x^295 + 406*x^294 + 406*x^293 + 406*x^292 + 406*x^291 + 406*x^290 + 449*x^289 + 449*x^288 + 449*x^287 + 449*x^286 + 449*x^285 + 493*x^284 + 493*x^283 + 493*x^282 + 493*x^281 + 493*x^280 + 538*x^279 + 538*x^278 + 538*x^277 + 538*x^276 + 538*x^275 + 584*x^274 + 584*x^273 + 584*x^272 + 584*x^271 + 584*x^270 + 631*x^269 + 631*x^268 + 631*x^267 + 631*x^266 + 631*x^265 + 679*x^264 + 679*x^263 + 679*x^262 + 679*x^261 + 679*x^260 + 722*x^259 + 722*x^258 + 722*x^257 + 722*x^256 + 722*x^255 + 766*x^254 + 766*x^253 + 766*x^252 + 766*x^251 + 766*x^250 + 805*x^249 + 805*x^248 + 805*x^247 + 805*x^246 + 805*x^245 + 845*x^244 + 845*x^243 + 845*x^242 + 845*x^241 + 845*x^240 + 880*x^239 + 880*x^238 + 880*x^237 + 880*x^236 + 880*x^235 + 910*x^234 + 910*x^233 + 910*x^232 + 910*x^231 + 910*x^230 + 935*x^229 + 935*x^228 + 935*x^227 + 935*x^226 + 935*x^225 + 955*x^224 + 955*x^223 + 955*x^222 + 955*x^221 + 955*x^220 + 970*x^219 + 970*x^218 + 970*x^217 + 970*x^216 + 970*x^215 + 980*x^214 + 980*x^213 + 980*x^212 + 980*x^211 + 980*x^210 + 985*x^209 + 985*x^208 + 985*x^207 + 985*x^206 + 985*x^205 + 985*x^204 + 985*x^203 + 985*x^202 + 985*x^201 + 985*x^200 + 980*x^199 + 980*x^198 + 980*x^197 + 980*x^196 + 980*x^195 + 970*x^194 + 970*x^193 + 970*x^192 + 970*x^191 + 970*x^190 + 955*x^189 + 955*x^188 + 955*x^187 + 955*x^186 + 955*x^185 + 935*x^184 + 935*x^183 + 935*x^182 + 935*x^181 + 935*x^180 + 910*x^179 + 910*x^178 + 910*x^177 + 910*x^176 + 910*x^175 + 880*x^174 + 880*x^173 + 880*x^172 + 880*x^171 + 880*x^170 + 845*x^169 + 845*x^168 + 845*x^167 + 845*x^166 + 845*x^165 + 805*x^164 + 805*x^163 + 805*x^162 + 805*x^161 + 805*x^160 + 766*x^159 + 766*x^158 + 766*x^157 + 766*x^156 + 766*x^155 + 722*x^154 + 722*x^153 + 722*x^152 + 722*x^151 + 722*x^150 + 679*x^149 + 679*x^148 + 679*x^147 + 679*x^146 + 679*x^145 + 631*x^144 + 631*x^143 + 631*x^142 + 631*x^141 + 631*x^140 + 584*x^139 + 584*x^138 + 584*x^137 + 584*x^136 + 584*x^135 + 538*x^134 + 538*x^133 + 538*x^132 + 538*x^131 + 538*x^130 + 493*x^129 + 493*x^128 + 493*x^127 + 493*x^126 + 493*x^125 + 449*x^124 + 449*x^123 + 449*x^122 + 449*x^121 + 449*x^120 + 406*x^119 + 406*x^118 + 406*x^117 + 406*x^116 + 406*x^115 + 364*x^114 + 364*x^113 + 364*x^112 + 364*x^111 + 364*x^110 + 325*x^109 + 325*x^108 + 325*x^107 + 325*x^106 + 325*x^105 + 287*x^104 + 287*x^103 + 287*x^102 + 287*x^101 + 287*x^100 + 252*x^99 + 252*x^98 + 252*x^97 + 252*x^96 + 252*x^95 + 218*x^94 + 218*x^93 + 218*x^92 + 218*x^91 + 218*x^90 + 187*x^89 + 187*x^88 + 187*x^87 + 187*x^86 + 187*x^85 + 159*x^84 + 159*x^83 + 159*x^82 + 159*x^81 + 159*x^80 + 134*x^79 + 134*x^78 + 134*x^77 + 134*x^76 + 134*x^75 + 112*x^74 + 112*x^73 + 112*x^72 + 112*x^71 + 112*x^70 + 93*x^69 + 93*x^68 + 93*x^67 + 93*x^66 + 93*x^65 + 77*x^64 + 77*x^63 + 77*x^62 + 77*x^61 + 77*x^60 + 62*x^59 + 62*x^58 + 62*x^57 + 62*x^56 + 62*x^55 + 50*x^54 + 50*x^53 + 50*x^52 + 50*x^51 + 50*x^50 + 39*x^49 + 39*x^48 + 39*x^47 + 39*x^46 + 39*x^45 + 31*x^44 + 31*x^43 + 31*x^42 + 31*x^41 + 31*x^40 + 24*x^39 + 24*x^38 + 24*x^37 + 24*x^36 + 24*x^35 + 18*x^34 + 18*x^33 + 18*x^32 + 18*x^31 + 18*x^30 + 13*x^29 + 13*x^28 + 13*x^27 + 13*x^26 + 13*x^25 + 9*x^24 + 9*x^23 + 9*x^22 + 9*x^21 + 9*x^20 + 6*x^19 + 6*x^18 + 6*x^17 + 6*x^16 + 6*x^15 + 4*x^14 + 4*x^13 + 4*x^12 + 4*x^11 + 4*x^10 + 2*x^9 + 2*x^8 + 2*x^7 + 2*x^6 + 2*x^5 + x^4 + x^3 + x^2 + x + 1

Das bedeutet dann beispielsweise

$\begin{eqnarray*} a_{100r} = \binom{r+5}{5} + 287\binom{r+4}{5} + 985\binom{r+3}{5} + 325\binom{r+2}{5} +2\binom{r+1}{5} = \frac{1}{6}\left(80r^5+390r^4+672r^3+483r^2+127r+6\right) \end{eqnarray*}$

und 99 weitere solche Polynome fünften Grades für die verbleibenden Koeffizientenfälle $\begin{eqnarray*} a_{100r+j} \end{eqnarray*}$ für $\begin{eqnarray*} j=1,\ldots,99 \end{eqnarray*}$ . Der Leitkoeffizient $\begin{eqnarray*} \frac{40}{3} \end{eqnarray*}$ ist übrigens für alle Fälle derselbe, so dass man wg. $\begin{eqnarray*} \frac{40}{3}r^5 = \frac{1}{750\,000\,000}\left(100r\right)^5 \end{eqnarray*}$ auf lange Sicht sagen kann $\begin{eqnarray*} a_k = \frac{k^5}{750\,000\,000} + O\left(k^4\right) \end{eqnarray*}$ .

06.02.2021, 08:07

Dopap

Auf diesen Beitrag antworten »

Danke für den Freude

Den Letzten gab es zur Aufgabe mit den 12 japanischen Sprührobotern.

---------------------------------------------------

Habe in der Zwischenzeit auch umständlich weitergerechnet und auch beim Polynom das CAS vom TR bemüht.
Ich denke das braucht jetzt hier nicht haarklein dargestellt zu werden, da du nicht nur Korrektur gelesen,
sondern das Ergebnis sauber lesbar formuliert hast.

Bei diesen Partitionen mit $\begin{eqnarray*} m\in \{ 1 ,5, 10, 25, 50 ,100 \} \end{eqnarray*}$ stand in Gedanken immer noch die ----> Geldwechselei Pate.
Und von den amerikanische Centmünzen gibt es eine weniger als im Euroland.

Was mit modulo 100 beschrieben wird, kann man auch so sehen, dass eine beliebige Zahl an $
( bei dir mit r bezeichnet ) gewechselt werden könnte.

Und zuletzt kommt noch die ketzerisch aufgeworfene Frage ins Spiel, ob der zeitliche Aufwand für diese Anzahlformel
(ist gültig für mehr als 3$)
nicht eventuell doch den PC mit dem superschnellen C++ zur Schnecke degradieren könnte?

Für einen Googol $ Schein oder $\begin{eqnarray*} 10^{100 }\,\$ \end{eqnarray*}$ erhalte ich
explizit und relativ schnell:

13333333333333333333333333333333333
33333333333333333333333333333333333
33333333333333333333333333333398333
33333333333333333333333333333333333
33333333333333333333333333333333333
33333333333333333333333344533333333
33333333333333333333333333333333333
33333333333333333333333333333333333
33333333333333333334138333333333333
33333333333333333333333333333333333
33333333333333333333333333333333333
33333333333333354500000000000000000
00000000000000000000000000000000000
00000000000000000000000000000000000
000000000001 $\begin{eqnarray*} \quad >10^{511} \end{eqnarray*}$

Am längsten dauert hier das Eintippen!

was sagt ein C++ Programm ohne Formel dazu ?

------------
Das Muster läßt sich bei großem r durch den dominierenden Summand von $\begin{eqnarray*} 40/3 r^5 \end{eqnarray*}$ und den "kleineren" Summanden erklären.

06.02.2021, 09:10

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Und zuletzt kommt noch die ketzerisch aufgeworfene Frage ins Spiel, ob der zeitliche Aufwand für diese Anzahlformel (ist gültig für mehr als 3$) nicht eventuell doch den PC mit dem superschnellen C++ zur Schnecke degradieren könnte?

Na für große $\begin{eqnarray*} k \end{eqnarray*}$ bzw. $\begin{eqnarray*} r \end{eqnarray*}$ auf jeden Fall. Der Rechenaufwand ist ja nur einmalig und hängt nur von der Münz-/Schein-Stückelung ab, aber nicht mehr von dem Geldwert, denn man damit darstellen will. (Im übrigen entbehren deine im hämischen Ton vorgetragenen Versuche, hocheffiziente Berechnungssoftware ins lächerliche zu ziehen, nur um deine lahme Möhre in besserem Licht erscheinen zu lassen, nicht einer gewissen Komik. Augenzwinkern

)

D.h., wenn der Geldwert sehr viel größer als der größte Schein ist, dann ist dieses Verfahren hier klar besser. Bei kleinen Geldwerten (also so wie im anderen Thread, wo der Geldwert gleich dem größten Schein war) sieht es natürlich anders aus.

Genauere Messungen: Allein die Berechnung von $\begin{eqnarray*} p(x) \end{eqnarray*}$ für die 500€-Schein-Stückelung bis zum Cent hinab, d.h. für $\begin{eqnarray*} (m_j)_{j=1,\ldots,15} = \left(1,2,5,10,20,50,100,200,500,1000,2000,5000,10000,20000,50000\right) \end{eqnarray*}$ , hat hochoptimiert mit C++ geschlagene 195 Sekunden in Anspruch genommen. Die Polynomkoeffizientenberechnung mit diesem vorberechneten $\begin{eqnarray*} p(x) \end{eqnarray*}$ sowie auch vorberechneten Binomialkoeffizienten-Polynomen $\begin{eqnarray*} r\mapsto \binom{r+14-j}{14} \end{eqnarray*}$ mit $\begin{eqnarray*} j=0,\ldots,14 \end{eqnarray*}$ (<1ms) dauert für alle 100000 Polynome dann insgesamt nur noch 4.5 Sekunden. Alles wohlgemerkt in exakter Rechnung, also nicht irgendwelchen gerundeten 64Bit-Fließkommazahlen.

--------------------------------------------------------------------------------------------------------------

Nochmal zusammengefasst dargestellt: Wir haben $\begin{eqnarray*} \ell \end{eqnarray*}$ Münz-/Schein-Werte $\begin{eqnarray*} m_1,\ldots,m_{\ell} \end{eqnarray*}$ , deren kgV sei $\begin{eqnarray*} m \end{eqnarray*}$ . Sehr oft ist dieser kgV gleich dem größten der Einzelwerte, aber nicht immer - beispielsweise, wenn die Stückelung bei 20, 50 endet oder in deinem letzten Beispiel bei 10, 25. Übrigens dürfen auch mehrere der $\begin{eqnarray*} m_j \end{eqnarray*}$ einander gleich sein, wie beispielsweise früher bei 5DM-Stück und -Schein, das Verfahren funktioniert auch dafür.

Ziel ist die Koeffizientenbestimmung der Reihe $\begin{eqnarray*} f(x) = \sum_{k=0}^{\infty} a_kx^k = \frac{1}{\prod\limits_{j=1}^{\ell} \left(1-x^{m_j}\right)} \end{eqnarray*}$ .

Dann ist $\begin{eqnarray*} f(x) = \frac{p(x)}{\left(1-x^m\right)^{\ell}} \end{eqnarray*}$ mit Polynom

$\begin{eqnarray*} p(x) = \prod\limits_{j=1}^{\ell} \frac{1-x^m}{1-x^{m_j}} = \prod\limits_{j=1}^{\ell} \left( \sum_{i=0}^{\frac{m}{m_j}-1} x^{im_j} \right) =: \sum_{k=0}^q p_kx^k \end{eqnarray*}$ vom Grad $\begin{eqnarray*} q=\ell m-\sum_{j=1}^{\ell}m_j \end{eqnarray*}$ .

Die Reihenentwicklung des Nenners ergibt schließlich

$\begin{eqnarray*} f(x) = \sum_{k=0}^{\infty} a_kx^k = \left( \sum_{k=0}^q p_kx^k \right) \cdot \left( \sum_{r=0}^{\infty} \binom{r+\ell-1}{\ell-1} x^{mr} \right) \end{eqnarray*}$

und damit per Koeffizientenvergleich

$\begin{eqnarray*} a_{mr+s} = \sum_{j=0}^{\ell-1} p_{jm+s} \binom{r+\ell-1-j}{\ell-1} \end{eqnarray*}$ für $\begin{eqnarray*} r\in\mathbb{N} \end{eqnarray*}$ und $\begin{eqnarray*} s=0,1,\ldots,r-1 \end{eqnarray*}$ .

Beispielsweise auf die letzte Eskalationsstufe in Geldwechsler angewandt ist $\begin{eqnarray*} \ell = 15,m=100\,000,q=1\,411\,112 \end{eqnarray*}$ , es sind also 100000 Polynome vom Grad 14 zu bestimmen...

Neue Frage »

Antworten »

Partitionen einer Zahl

Verwandte Themen