nette Aufgabe II < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm]n\in\IN[/mm].
Ist [mm]4^{545}+545^4[/mm] prim? |
Hallo zusammen,
hier eine weitere nette Übungsaufgabe zum Thema Primzahlen ...
Viel Freude daran 
Gruß
schachuzipus
|
|
| |
|
> Sei [mm]n\in\IN[/mm].
>
> Ist [mm]4^{545}+545^4[/mm] prim?
Gemäß deiner "netten Aufgabe I" natürlich nicht ...
Wer eine leichtere Aufgabe haben möchte, könnte
zeigen, dass [mm] 4^{545}+545^4 [/mm] durch 73 teilbar ist.
LG Al
|
|
|
| |
|
Hallo Al,
> > Sei [mm]n\in\IN[/mm].
> >
> > Ist [mm]4^{545}+545^4[/mm] prim?
>
>
> Gemäß deiner "netten Aufgabe I" natürlich nicht ...
Ganz recht! Du hast also eine Darstellung gem. Auf. I gefunden und die damit verbundene Zerlegung ...
>
> Wer eine leichtere Aufgabe haben möchte, könnte
> zeigen, dass [mm]4^{545}+545^4[/mm] durch 73 teilbar ist.
>
> LG Al
Gruß
schachuzipus
|
|
|
| |
|
Hallo zusammen,
da sich bis auf Al-Chwarizmi bisher niemand an der Aufgabe versucht hat und damit sie nicht untergeht (ist nämlich ganz interssant - auch im Hinblick auf Aufgabe I), schubse ich sie mal nach oben
Viel Spaß damit!
Gruß
schachuzipus
|
|
|
| |
|
Du musstest ja auch unbedingt ein n nehmen, das mit einer 5 endet *g*
Für [mm]n>1, n \ mod \ 10 \not= 5[/mm] könnte ich sogar allgemein zeigen, dass [mm]n^4 + 4^n[/mm] keine Primzahl ist (also deine nette Aufgabe I).
Aber ne, du musstest ja unbedingt eine Zahl nehmen die auf 5 endet. xD
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:02 Fr 24.06.2011 | | Autor: | reverend |
Hallo Maître de l'ombre,
> Du musstest ja auch unbedingt ein n nehmen, das mit einer 5
> endet *g*
>
> Für [mm]n>1, n \ mod \ 10 \not= 5[/mm] könnte ich sogar allgemein
> zeigen, dass [mm]n^4 + 4^n[/mm] keine Primzahl ist (also deine nette
> Aufgabe I).
Na, das ist aber auch nicht wirklich schwer. [mm] 1^4\equiv 3^4\equiv 7^4 \equiv 9^4 \equiv 1\mod{5}
[/mm]
> Aber ne, du musstest ja unbedingt eine Zahl nehmen die auf
> 5 endet. xD
Jo, wat mutt, dat mutt.
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:57 Sa 25.06.2011 | | Autor: | rabilein1 |
> Ist [mm]4^{545}+545^4[/mm] prim?
In welchen Fällen ist denn [mm] a^{b}+b^{a} [/mm] prim?
In welchem Zusammenhang stehen hier 4 und 545 ?
Könnte man da auch irgendwelche x-beliebigen anderen Zahlen nehmen?
Naja, ein 'Supercomputer' wird das sicherlich rauskriegen, indem er einfach das Ergebnis der Addition berechnet, und dann anfängt zu dividieren. Aber wie lange würde er wohl brauchen bis zum Ergebnis?
|
|
|
| |
|
Hallo zusammen,
helfen könnte, dass man [mm]x^4+4y^4[/mm] faktorisieren kann!
Wie? Und warum sollte das helfen?
Gruß
schachuzipus
|
|
|
| |
|
Hier kann man doch 'Identity of Sophie Germain' anwenden. (Wird das einfach in's Deutsche übersetzt?! :D )
Das wäre [mm] a^4+4*b^4=(a^2+2b^2+2ab)(a^2+2*b^2-2ab)
[/mm]
Und in der Aufgabe kann man ja schreiben [mm] 4^545=4*(4^136)^4.
[/mm]
Also kann man [mm] 545^4+4^545 [/mm] faktorisieren. Beide Faktoren sind auch größer 1, wie man leicht zeigen kann.
Lg, David
|
|
|
| |
|
Hallo David,
> Hier kann man doch 'Identity of Sophie Germain' anwenden.
> (Wird das einfach in's Deutsche übersetzt?! :D )
> Das wäre [mm]a^4+4*b^4=(a^2+2b^2+2ab)(a^2+2*b^2-2ab)[/mm]
Hmm, genau! War mein Tipp zu hilfreich?
>
> Und in der Aufgabe kann man ja schreiben
> [mm]4^545=4*(4^136)^4.[/mm]
Ja! Schöner formatiert: [mm]4^{545}=4\cdot{}\left(4^{136}\right)^4[/mm]
> Also kann man [mm]545^4+4^545[/mm] faktorisieren. Beide Faktoren
> sind auch größer 1, wie man leicht zeigen kann.
Ganz recht!
>
> Lg, David
Gruß
schachuzipus
|
|
|
| |
|
Hehe.. Naja ich kenn die Identität. ;D
Schade, dass sich die meisten Wettbewerbsaufgaben nicht so einfach lösen lassen. :D
Lg, David
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:32 Sa 25.06.2011 | | Autor: | felixf |
Moin!
> Naja, ein 'Supercomputer' wird das sicherlich rauskriegen,
> indem er einfach das Ergebnis der Addition berechnet, und
> dann anfängt zu dividieren. Aber wie lange würde er wohl
> brauchen bis zum Ergebnis?
Nein, das macht ein Supercomputer meistens nicht, da es einfach viiiiel zu lange dauert 
Durchprobieren wird nur fuer sehr kleine Zahlen gemacht, wobei man sich das auch meist erspart, indem man zuerst den ggT der Zahl mit dem Produkt von den ersten zig Primzahlen ausrechnet. Ist der ggT ungleich 1, so schaut man genauer nach und hat somit schonmal einen Faktor gefunden. Wenn der ggT 1 ist, dann ist die Zahl mindestens so gross wie das Quadrat der groessten Primzahl in diesem Produkt (andernfalls ist sie prim). Jetzt kann man erstmal ein paar Runden einen nicht-deterministischen Primzahltest anwenden, und schauen ob die Zahl evtl. prim ist. Scheit es so zu sein, wendet man den Algorithmus noch ein paarmal oefter an und dann (wenn an es ganz genau wissen will) nimmt man einen Algorithmus, der ein Zertifikat fuer die Primheit liefert (etwa eine Abwandlung des AKS-Algorithmus).
Wenn man denkt, dass die Zahl nicht prim ist (weil ein Primzahltest das herausgefunden hat), muss man versuchen zu faktorisieren. Eine beliebte Methode, deren Komplexitaet (vermutet) subexponentiell in der Groesse des kleinsten Primfaktors ist, ist die Lenstrasche ![[]](/images/popup.gif) Elliptische-Kurven-Methode. Alternativ (etwa wenn man weiss, dass es keinen kleinen Primfaktor gibt und wenn die Zahl sehr gross ist) kann man auch gleich schwere Geschuetze auffahren wie das Zahlkoerpersieb, die heutzutage schnellste bekannte Faktorisierungsmethode. (Die lohnt sich aber erst ab einer gewissen Eingabegroesse, und evtl. sollte man ihr ein paar Runden der Lenstra-Methode vorschalten, um sicherzugehen dass es keine zu kleinen Primfaktoren gibt.)
Und zu der Frage:
> In welchen Fällen ist denn $ [mm] a^{b}+b^{a} [/mm] $ prim?
Hier war der Trick, dass man das ganze auf die Formel von Sophie Germain zurueckfuehrt. Bei allgemeinen $a, b$ kann es sehr wohl auch mal prim sein. Ich habe mit Maple alle Paare $[a, b]$ mit $2 [mm] \le [/mm] a [mm] \le [/mm] b [mm] \le [/mm] 200$ untersucht, folgende sind herausgekommen, fuer die [mm] $a^b [/mm] + [mm] b^a$ [/mm] prim sind:
[2, 3], [2, 9], [2, 15], [2, 21], [2, 33], [3, 56], [5, 24], [7, 54], [8, 69], [9, 76], [9, 122], [15, 32], [21, 68], [32, 135], [33, 38], [34, 75], [36, 185], [45, 158], [56, 87], [65, 144], [67, 114], [80, 81], [97, 114], [98, 171], [133, 160]
Wenn man die Schranke von 200 auf 300 erhoeht, kommen folgende hinzu:
[51, 206], [76, 215], [87, 248], [157, 214], [200, 237], [214, 235]
(Wenn man $a = 1$ zulaesst, werden es noch einige mehr. Was aber kein Wunder ist, da dann einfach $b p - 1$ sein muss fuer eine Primzahl $p$.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:17 Sa 25.06.2011 | | Autor: | rabilein1 |
Summa summarum schließe ich mal daraus: Je weiter man fortschreitet, desto dünner wird die Luft. Obwohl 545 (und erst recht die 4) ja eigentlich keine sooooo schrecklich große Zahlen ist.
Wir könnten ja mal wetten, ob die Supersupercomputer im Jahre 2254 auch die Zahlenpaare jenseits der 1000 finden werden. Aber davon haben wir wohl genau so wenig eine Vorstellung wie Gauss von den Fähigkeiten heutiger Computer hatte. (Und was ist denn schon 1000 im Vergleich zur Unendlichkeit der natürlichen Zahlen?)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:42 Sa 25.06.2011 | | Autor: | felixf |
Moin,
> Summa summarum schließe ich mal daraus: Je weiter man
> fortschreitet, desto dünner wird die Luft. Obwohl 545 (und
> erst recht die 4) ja eigentlich keine sooooo schrecklich
> große Zahlen ist.
>
> Wir könnten ja mal wetten, ob die Supersupercomputer im
> Jahre 2254 auch die Zahlenpaare jenseits der 1000 finden
> werden. Aber davon haben wir wohl genau so wenig eine
> Vorstellung wie Gauss von den Fähigkeiten heutiger
> Computer hatte. (Und was ist denn schon 1000 im Vergleich
> zur Unendlichkeit der natürlichen Zahlen?)
Da brauchst du nicht bis 2254 zu warten. Die Zahl [mm] $1040^{1401} [/mm] + [mm] 1401^{1040}$ [/mm] ist prim.
Ausgeschrieben ist das:
730648265403504473749683693294339313264468027
662108217196397209013258820925135725774090426
466996507001313162902215383376044110317626986
149183616100967243686587706109501375783795773
198885819320251367085059068917906183421276329
325464020068535758704505766884039323331855767
960254394397772300360686564657956337010325060
547046968400194177127784730806901233696686073
946867466710180215435939374066238452124463471
151979727656785269124744225072931855573149232
740357993481688683548332749852148850467567197
941883747592666848101912149672913956995364072
537890589976447892192753935221214848825752361
030504198625009929122708719736388897887441502
340170015632584910898140864987812011625030271
476785261015696069409668557868583334721388723
464064345247266778122788488777088595461608422
526340935860462164934294014638686794770852745
521720648782228068241598040405856346617632046
637975745456706650421289425073465951631456254
774455425549286618579396588803544531026998068
619619896462577465589630375664560770991564664
560280953694092537935023070293475772975380725
260010953541931179327937751067619143180441845
958767846854559790653545677190277633116442321
783531056177123398891613565667570288933320067
341308454123169519631554975206384621337342691
439617211294964437849418451504874834450804044
226898904567413911797570887480822574109174048
200950009923833759772773846593098109646208155
827846253230814218827287339323907898404456198
985862451572124330454123811002010153729854260
189338217932351512588318008422349683464640409
812485325834910354531570582090833958617200757
181568048048844711046913979804376315795454529
486953235788248702854233557305461444418631629
548716386011880697204016755846630735223603913
951646757474508765560244124568230802846720576
957482091407794293468757009227267741896951708
685125527827476267657409620871364592158634654
009641621130452237361888490367796561371940198
644215690874038219671160774051344888395353167
743734181303394498323382212870532696130269630
277149385166652980806975863540147049261022712
140212006626877474231744255697904168808802153
598635086132083626564793604876276671382627772
646726361830906827130529178840637421286902862
558430265219913886277161562650659534188697412
172733037151718321309640570558741187920113101
536365726298386915410267283622042494444479501
906053088260069365533682582964887064627402252
804187899941736895209828444379269086999572576
088098710556306071310868768530786183497303946
994848389867807029315383780032356551934442324
746376330273953540847263495916803961318761483
683609068811776537905184537217076269628000151
527314229409569503099566143101217854822821359
948645957196979399814591718730879162874851015
048498407964601247376460287552471283418017939
929081411464248672475101999496344315902271288
005654557213282429589499781031255794598415360
141795515062853396702523856223271621702856674
950424043954098963944810680830443597556960696
087980599207868658129738249548508911108420196
805616074987763380723955863311270258874792869
184495049090743868746097766551257495334082507
803111471819079653409889101344590388073414090
493472764060484346421166553525645124977987133
928425899216377600098741163053803451184916937
969090185860137296482101478382747638521307611
326088259537955491393425070936015373526507137
962419740031699392636492318737611670846398388
750229004639519099100296708556363852276884623
746797556570743450023235880770589740246014816
563980705419252090724475321271609144144837624
594800692629757620725866666692116956696826887
172971356555050343368485167514523680116081699
255237648914153620250389882796791843890066653
950669666709504821377247694289152794623931628
432766963518814713277455857802783175290087336
621944900603681961056262552007992270705419676
881323389537495653304961427039247993642143886
391140570339464504325895136572292690482617578
241695752769535053579424592093037429132361579
310124178871240259024763748823912416881582444
414230799594930312587304051810899520541251502
982574202133513210794527738633206666905741884
688967443449642279937846683418345824421852015
546590672203008676660699800967125070227002594
842529495591809750190292760621774492213946815
867423814589594763070145904123494975593491065
097396490203076017152756288437738251607118413
816045408979630779169105798230071719622465760
448327470687219795748190121425201670256001
(die Zahl hat 4227 Dezimalstellen, und 14042 Binaerstellen.)
Edit: Zeilenumbrueche eingefuegt
Und ebenso [mm] $1066^{1325} [/mm] + [mm] 1325^{1066}$. [/mm] Die beiden Paare hat Maple in weniger als einer Stunde gefunden (ich habe den Suchraum auf $1000 [mm] \le [/mm] a [mm] \le [/mm] b [mm] \le [/mm] 1500$ festgesetzt, er ist momentan bei $a = 1071$, und fuer jedes $a$ probiert er alle $b$ mit $a [mm] \le [/mm] b [mm] \le [/mm] 1500$ und $ggT(a, b) = 1$ durch).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:15 So 26.06.2011 | | Autor: | felixf |
Moin,
nach unter 3 Stunden und 40 Minuten Rechnerei hat sich ergeben, dass folgendes alle Paare $[a, b]$ mit $1000 [mm] \le [/mm] a [mm] \le [/mm] b [mm] \le [/mm] 1500$ und [mm] $a^b [/mm] + [mm] b^a$ [/mm] prim sind:
[1040, 1401], [1066, 1325], [1095, 1154], [1106, 1419], [1188, 1405], [1194, 1195], [1232, 1395], [1410, 1451]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:49 So 26.06.2011 | | Autor: | reverend |
Hallo Felix,
> nach unter 3 Stunden und 40 Minuten Rechnerei hat sich
> ergeben, dass folgendes alle Paare [mm][a, b][/mm] mit [mm]1000 \le a \le b \le 1500[/mm]
> und [mm]a^b + b^a[/mm] prim sind:
>
> [1040, 1401], [1066, 1325], [1095, 1154], [1106, 1419],
> [1188, 1405], [1194, 1195], [1232, 1395], [1410, 1451]
Das ist gut zu wissen.
Ich habe mir ein Lesezeichen gesetzt...
Grüße
rev
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:08 So 26.06.2011 | | Autor: | rabilein1 |
So etwas konnte man vor 100 Jahren den Mathe-Studenten noch als Strafarbeit aufgeben.
Zeigen Sie, dass a=1194 und b=1195 die einzigen aufeinanderfolgenden Zahlen zwischen 1000 und 1500 sind, für die gilt:
[mm]a^b + b^a[/mm] sind prim.
Hat das eigentlich schon Gauss gewusst? Den hätte so was doch bestimmt interessiert.
Und falls nein: Wer war der Erste, der das rausgefunden hat?
|
|
|
| |
|
> So etwas konnte man vor 100 Jahren den Mathe-Studenten noch
> als Strafarbeit aufgeben.
> Zeigen Sie, dass a=1194 und b=1195 die einzigen
> aufeinanderfolgenden Zahlen zwischen 1000 und 1500 sind,
> für die gilt:
> [mm]a^b + b^a[/mm] sind prim.
Das wäre eine äußerst fruchtlose, weil unmöglich zu lösende
Strafarbeit gewesen. Und der damit beauftragte Student hätte
den Auftraggeber in arge Bedrängnis bringen können, wenn
er ihn vor vollem Hörsaal nach der Lösung bzw. auch nur nach
dem Nachweis der Primzahleigenschaft von [mm] 1194^{1195}+1195^{1194}
[/mm]
gefragt hätte.
> Hat das eigentlich schon Gauss gewusst?
Hat er bestimmt nicht !
> Den hätte so was doch bestimmt interessiert.
Dessen bin ich nicht sooo sicher. Neben seinen theoretischen
Arbeiten war Gauß nämlich auch ein sehr praktisch orientierter
Geist. Und ihm war zweifellos auch klar, dass es in der Zahlen-
theorie noch massenweise (nämlich unendlich viele) Aussagen
gibt, die zwar richtig, aber deswegen allein noch keineswegs
von besonderem Interesse sind.
> Und falls nein: Wer war der Erste, der das rausgefunden hat?
Ich denke mal, dass sich wohl erst sehr wenige Leute um
gerade diese Frage gekümmert haben. Möglicherweise (ich
denke sogar, mit sehr hoher Wahrscheinlichkeit) bist du
(aufgrund der Vorarbeit von reverend, der in seinem PC
Zilliarden von Elektronen einer stundenlangen möglicherweise
nicht wirklich elektronengerechten Tortur ausgesetzt hat)
sogar der allererste, der das Ergebnis in dieser Form
herausgestellt hat ...
LG und schönen Abend !
Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:38 So 26.06.2011 | | Autor: | reverend |
Hallo Al,
ich bin zu spät dran, da ich gerade schriftstellerisch tätig war...
Wir schätzen die Situation offenbar ganz ähnlich ein.
> Möglicherweise (ich
> denke sogar, mit sehr hoher Wahrscheinlichkeit) bist du
> (aufgrund der Vorarbeit von reverend, der in seinem PC
> Zilliarden von Elektronen einer stundenlangen
> möglicherweise
> nicht wirklich elektronengerechten Tortur ausgesetzt hat)
Aber nein, so etwas würde ich doch niiie tun. Außerdem habe ich gar keine passenden Programme dazu, um solche Rechnungen meinen elektronischen Butler durchführen zu lassen. Das war Felix.
Ehre, wem Ehre gebührt. Wir haben hier in Deutschland ja seit einiger Zeit ein Problem mit der Korrektheit von Fußnoten, da will ich mich lieber nicht in unnötigen Verdacht bringen.
Grüße
reverend
|
|
|
| |
|
Alles klar - hätte ja so auch nicht wirklich gepasst.
Damit alles seine Ordnung hat, habe ich soeben die
Anweisung erteilt:
Replace[https://matheraum.de/read?i=806288,"reverend"->"felixf"]
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:33 So 26.06.2011 | | Autor: | reverend |
Hallo rabilein,
> So etwas konnte man vor 100 Jahren den Mathe-Studenten noch
> als Strafarbeit aufgeben.
Nur, wenn jemand eine lebenslängliche Strafe abzusitzen hatte. Ansonsten hätte es wahrscheinlich eher für eine Promotion genügt, da man neue Methoden hätte finden müssen, um überhaupt für Zahlen mit über 30.000 Stellen eine Aussage über die Zerlegbarkeit zu treffen. Alle heute angewandten Methoden waren da noch nicht gefunden, und der "kleine Fermat" genügt leider nicht: ist [mm] a^{n-1}\not\equiv 1\mod{n}, [/mm] dann ist n sicher zerlegbar. Ist n aber prim, dann ist sicher [mm] a^{n-1}\equiv 1\mod{n}. [/mm] Leider erledigt das nicht alle Fälle, wie z.B. diesen: [mm] 2^{340}\equiv 1\mod{341}. [/mm] Dennoch ist 341=11*31, also nicht prim.
> Zeigen Sie, dass a=1194 und b=1195 die einzigen
> aufeinanderfolgenden Zahlen zwischen 1000 und 1500 sind,
> für die gilt:
> [mm]a^b + b^a[/mm] sind prim.
>
> Hat das eigentlich schon Gauss gewusst? Den hätte so was
> doch bestimmt interessiert.
Vielleicht. Vielleicht nicht. Über die Fermatsche Vermutung hat er jedenfalls offenbar geäußert, dass er daran als Einzelproblem kein Interesse habe, er könne "eine Vielzahl solcher Behauptungen aufstellen, die weder zu beweisen noch zu widerlegen sind".
(Leider kein guter Beleg im Internet, aber immerhin diese).
> Und falls nein: Wer war der Erste, der das rausgefunden
> hat?
Srinivasa Ramanujan Aiyangar natürlich. Bei einer Einladung zum High Tea bei seinem Kollegen und Förderer G.H. Hardy zerbrach dessen Nichte eine schöne viktorianische (also fast noch zeitgenössische) Teekanne. Sie war sich allerdings nach einer ersten Sichtung des Chaos nicht mit ihrem Onkel einig, ob die Kanne nun in 1194 oder 1195 Teile zersprungen war, worauf Ramanujan feststellte, dass die Addition [mm] 1194^n+1195^n [/mm] für n<8000 nur für n=1 und n=2 ein primes Ergebnis liefere.
Die Nichte bemerkte, dass der Faktor 2389 erstaunlich häufig in der Zerlegung der Ergebnisse vorkäme, und wurde von Hardy angeherrscht, sie möge ihre Trivialitäten für sich behalten. Ramanujan meinte darauf versöhnlich, dass die interessantere Aufgabe sei, die erstaunliche Häufigkeit des Faktors 37 zu erklären. (Die Nichte war zu diesem Zeitpunkt 13 Jahre alt, was aber wenig zur Sache tut).
Nachdem Hardy einen Scone mit Butter gegessen hatte, erklärte Ramanujan, dass 1194, 1195 eine ungewöhnliche Lösung für [mm] a^b+b^a=prim [/mm] sei. Weitere Lösungen wolle er erst präsentieren, wenn Hardy noch einen Scone äße.
***
Übrigens könnte ich viele solche Geschichten erzählen, die sich weder beweisen noch widerlegen lassen, vor allem, weil sie mit Hilfe einer heuristischen Suche allein meiner Phantasie entsprungen sind...
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:59 Di 05.07.2011 | | Autor: | reverend |
Hallo allerseits,
ein kleiner Nachtrag zum (nicht nur mathematischen) Wahrheitsgehalt der Geschichte.
> > Und falls nein: Wer war der Erste, der das rausgefunden
> > hat?
>
> Srinivasa Ramanujan Aiyangar
> natürlich. Bei einer Einladung zum High Tea bei seinem
> Kollegen und Förderer
> G.H. Hardy
> zerbrach dessen Nichte eine schöne viktorianische (also
> fast noch zeitgenössische) Teekanne. Sie war sich
> allerdings nach einer ersten Sichtung des Chaos nicht mit
> ihrem Onkel einig, ob die Kanne nun in 1194 oder 1195 Teile
> zersprungen war, worauf Ramanujan feststellte, dass die
> Addition [mm]1194^n+1195^n[/mm] für n<8000 nur für n=1 und n=2 ein
> primes Ergebnis liefere.
Genauer: für n<8192 ist das sicher wahr, und für größere n kann ich es nicht überprüfen, weil meine Software dafür nicht ausreicht. Jedenfalls genügt es, [mm] n=2^k [/mm] zu untersuchen; alle anderen sind sowieso faktorisierbar und daher nicht prim.
> Die Nichte bemerkte, dass der Faktor 2389 erstaunlich
> häufig in der Zerlegung der Ergebnisse vorkäme, und wurde
> von Hardy angeherrscht, sie möge ihre Trivialitäten für
> sich behalten.
2389=1194+1195. Der Faktor wird daher immer in [mm] 1194^n+1195^n [/mm] vorkommen, wenn n ungerade ist.
> Ramanujan meinte darauf versöhnlich, dass
> die interessantere Aufgabe sei, die erstaunliche
> Häufigkeit des Faktors 37 zu erklären. (Die Nichte war zu
> diesem Zeitpunkt 13 Jahre alt, was aber wenig zur Sache
> tut).
37 ist einer der Faktoren von [mm] 1194^3+1195^3 [/mm] und teilt daher [mm] 1194^n+1195^n [/mm] immer dann, wenn n=3*(2k+1) ist. Eine mathematisch begabte 13-Jährige könnte das erkennen, eine normal gebildete 16-Jährige sollte es sogar.
> Nachdem Hardy einen Scone mit Butter gegessen hatte,
> erklärte Ramanujan, dass 1194, 1195 eine ungewöhnliche
> Lösung für [mm]a^b+b^a=prim[/mm] sei. Weitere Lösungen wolle er
> erst präsentieren, wenn Hardy noch einen Scone äße.
Immerhin gibt es zum High Tea (eine aussterbende Tradition) allerlei meist kaltes Essen. Die abgespeckte Variante, der Light Tea, hat dagegen meist nur Scones (gern auch mit Butter), ich weiß aber nicht, ob Hardy sie mochte. (Informativ: britische Teekultur).
Dafür hätte Ramanujan vielleicht Spaß an der folgenden Zerlegung gehabt:
[mm] 1194^51+1195^51=7^2 \times 37 \times 103 \times 787 \times 1327 \times 1429 \times 2389 \times 72931 \times 67 211779 \times 227379 794325 354386 222001 496609 \times 1 355793 544081 733859 365121 895046 009421 527992 839499 \times 17 178641 404622 604721 504130 252026 651808 963709 484351 [/mm]
Die kleineren Faktoren sind durch Probedivisionen gefunden, alle weiteren über elliptische Kurven; der letzte natürlich dann nur noch durch Division: mehr war dann halt nicht mehr zu zerlegen. Für das Programm, mit dem ich diese Zerlegung gefunden habe, ist das immerhin noch einen Platz auf der Liste der "best 20" wert.
Auf einem anderen Rechner läuft das gleiche Programm mit anderer Suchmethode, dem quadratischen Sieb. Weil ichs zwischendurch mal abgeschossen habe, wird das aber noch knapp drei Tage dauern.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:10 Mi 06.07.2011 | | Autor: | felixf |
Moin rev,
> ein kleiner Nachtrag zum (nicht nur mathematischen)
> Wahrheitsgehalt der Geschichte.
vielen Dank uebrigens fuer diese interessante Geschichte
> > > Und falls nein: Wer war der Erste, der das rausgefunden
> > > hat?
> >
> > Srinivasa Ramanujan Aiyangar
> > natürlich. Bei einer Einladung zum High Tea bei seinem
> > Kollegen und Förderer
> > G.H. Hardy
> > zerbrach dessen Nichte eine schöne viktorianische (also
> > fast noch zeitgenössische) Teekanne. Sie war sich
> > allerdings nach einer ersten Sichtung des Chaos nicht mit
> > ihrem Onkel einig, ob die Kanne nun in 1194 oder 1195 Teile
> > zersprungen war, worauf Ramanujan feststellte, dass die
> > Addition [mm]1194^n+1195^n[/mm] für n<8000 nur für n=1 und n=2 ein
> > primes Ergebnis liefere.
>
> Genauer: für n<8192 ist das sicher wahr, und für
> größere n kann ich es nicht überprüfen, weil meine
> Software dafür nicht ausreicht. Jedenfalls genügt es,
> [mm]n=2^k[/mm] zu untersuchen; alle anderen sind sowieso
> faktorisierbar und daher nicht prim.
Fuer $n = [mm] 2^{13} [/mm] = 8192$ ist es nicht prim, das hat Magma ziemlich schnell herausgefunden (definitiv < 30 min, und die Maschine ist nicht gerade die schnellste...). Die naechsten beiden Zweierpotenzen rechnen noch.
> > Ramanujan meinte darauf versöhnlich, dass
> > die interessantere Aufgabe sei, die erstaunliche
> > Häufigkeit des Faktors 37 zu erklären. (Die Nichte war zu
> > diesem Zeitpunkt 13 Jahre alt, was aber wenig zur Sache
> > tut).
>
> 37 ist einer der Faktoren von [mm]1194^3+1195^3[/mm] und teilt daher
> [mm]1194^n+1195^n[/mm] immer dann, wenn n=3*(2k+1) ist. Eine
> mathematisch begabte 13-Jährige könnte das erkennen, eine
> normal gebildete 16-Jährige sollte es sogar.
Wieviel Zeit steht zur Verfuegung? :)
> Dafür hätte Ramanujan vielleicht Spaß an der folgenden
> Zerlegung gehabt:
>
> [mm]1194^51+1195^51=7^2 \times 37 \times 103 \times 787 \times 1327 \times 1429 \times 2389 \times 72931 \times 67 211779 \times 227379 794325 354386 222001 496609 \times 1 355793 544081 733859 365121 895046 009421 527992 839499 \times 17 178641 404622 604721 504130 252026 651808 963709 484351[/mm]
>
> Die kleineren Faktoren sind durch Probedivisionen gefunden,
> alle weiteren über elliptische Kurven; der letzte
> natürlich dann nur noch durch Division: mehr war dann halt
> nicht mehr zu zerlegen. Für das Programm, mit dem ich
> diese Zerlegung gefunden habe, ist das immerhin noch einen
> Platz auf der Liste der "best 20" wert.
Welches Programm war es denn? GMP-ECM?
> Auf einem anderen Rechner läuft das gleiche Programm mit
> anderer Suchmethode, dem quadratischen Sieb. Weil ichs
> zwischendurch mal abgeschossen habe, wird das aber noch
> knapp drei Tage dauern.
Wenn du etwas fuer laengere Zeit laufen lassen willst, melde dich. Zumindest solange es unter Linux laeuft :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:34 Mi 06.07.2011 | | Autor: | reverend |
Hallo Felix,
> > Jedenfalls genügt es,
> > [mm]n=2^k[/mm] zu untersuchen; alle anderen sind sowieso
> > faktorisierbar und daher nicht prim.
>
> Fuer [mm]n = 2^{13} = 8192[/mm] ist es nicht prim, das hat Magma
> ziemlich schnell herausgefunden (definitiv < 30 min, und
> die Maschine ist nicht gerade die schnellste...). Die
> naechsten beiden Zweierpotenzen rechnen noch.
Magma?
> > 37 ist einer der Faktoren von [mm]1194^3+1195^3[/mm] und teilt daher
> > [mm]1194^n+1195^n[/mm] immer dann, wenn n=3*(2k+1) ist. Eine
> > mathematisch begabte 13-Jährige könnte das erkennen, eine
> > normal gebildete 16-Jährige sollte es sogar.
>
> Wieviel Zeit steht zur Verfuegung? :)
Sagen wir: genügend. In der Geschichte dürfte man sicher mehrere Minuten nach dem Ausbruch Hardys annehmen.
> > Für das Programm, mit dem ich
> > diese Zerlegung gefunden habe, ist das immerhin noch einen
> > Platz auf der Liste der "best 20" wert.
>
> Welches Programm war es denn?
> GMP-ECM?
Oh, hübsch. Nein, das kannte ich noch gar nicht. Wir sollten vielleicht mal irgendwo eine Softwareempfehlungsseite im Forum einrichten..
Ich habe das Programm von Dario Alpern benutzt. Es hat eine ganz passable Geschwindigkeit selbst auf meinen alten Rechnern.
> > Auf einem anderen Rechner läuft das gleiche Programm mit
> > anderer Suchmethode, dem quadratischen Sieb. Weil ichs
> > zwischendurch mal abgeschossen habe, wird das aber noch
> > knapp drei Tage dauern.
>
> Wenn du etwas fuer laengere Zeit laufen lassen willst,
> melde dich. Zumindest solange es unter Linux laeuft :)
Es ist unwahrscheinlich, dass ich das in Anspruch nehme, aber danke für das Angebot!
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:26 Mi 06.07.2011 | | Autor: | felixf |
Moin rev,
> > > Jedenfalls genügt es,
> > > [mm]n=2^k[/mm] zu untersuchen; alle anderen sind sowieso
> > > faktorisierbar und daher nicht prim.
> >
> > Fuer [mm]n = 2^{13} = 8192[/mm] ist es nicht prim, das hat Magma
> > ziemlich schnell herausgefunden (definitiv < 30 min, und
> > die Maschine ist nicht gerade die schnellste...). Die
> > naechsten beiden Zweierpotenzen rechnen noch.
>
> Magma?
ja, das Magma :) mit $n = [mm] 2^{14} [/mm] = 16384$ ist es auch nicht prim. (Laufzeit: 1:40 h auf einer 1-GHz-UltrasparcIII-Maschine, also recht lahm im Vergleich zu heutigen schnellen Rechnern.)
> > > 37 ist einer der Faktoren von [mm]1194^3+1195^3[/mm] und teilt daher
> > > [mm]1194^n+1195^n[/mm] immer dann, wenn n=3*(2k+1) ist. Eine
> > > mathematisch begabte 13-Jährige könnte das erkennen, eine
> > > normal gebildete 16-Jährige sollte es sogar.
> >
> > Wieviel Zeit steht zur Verfuegung? :)
>
> Sagen wir: genügend. In der Geschichte dürfte man sicher
> mehrere Minuten nach dem Ausbruch Hardys annehmen.
>
> > > Für das Programm, mit dem ich
> > > diese Zerlegung gefunden habe, ist das immerhin noch einen
> > > Platz auf der Liste der "best 20" wert.
> >
> > Welches Programm war es denn?
> > GMP-ECM?
>
> Oh, hübsch. Nein, das kannte ich noch gar nicht. Wir
Die GMP-ECM-Implementierung duerfte zusammen mit EECM-MPFQ zu den besten ECM-Implementierungen gehoeren. Die EECM-MPFQ-Varianta ist glaub ich sogar noch einen Tacken schneller als die GMP-ECM-Variante.
> sollten vielleicht mal irgendwo eine
> Softwareempfehlungsseite im Forum einrichten..
> Ich habe das Programm von Dario
> Alpern benutzt. Es hat
> eine ganz passable Geschwindigkeit selbst auf meinen alten
> Rechnern.
Ah, die Seite kannte ich noch nicht.
Ich hab noch eine eigene kleine Implementation, die ich in ein paar Programmen "auf der Arbeit" nutze. Allerdings hab ich bisher keine Standalone-Version davon gemacht. Und es ist auch nicht die beste Implementation, es war eher ein kleiner Hack um halbwegs effizient nicht mehr ganz so kleine Zahlen faktorisieren zu koennen die ein Algorithmus ausgespuckt hat...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:11 Do 07.07.2011 | | Autor: | felixf |
Moin,
> > > > Jedenfalls genügt es,
> > > > [mm]n=2^k[/mm] zu untersuchen; alle anderen sind sowieso
> > > > faktorisierbar und daher nicht prim.
> > >
> > > Fuer [mm]n = 2^{13} = 8192[/mm] ist es nicht prim, das hat Magma
> > > ziemlich schnell herausgefunden (definitiv < 30 min, und
> > > die Maschine ist nicht gerade die schnellste...). Die
> > > naechsten beiden Zweierpotenzen rechnen noch.
> >
> > Magma?
>
> ja, das Magma :) mit [mm]n = 2^{14} = 16384[/mm] ist es auch nicht
> prim. (Laufzeit: 1:40 h auf einer
> 1-GHz-UltrasparcIII-Maschine, also recht lahm im Vergleich
> zu heutigen schnellen Rechnern.)
so, und mit $n = [mm] 2^{15} [/mm] = 32768$ ist es auch nicht prim. (Laufzeit: 8:51 h)
Damit ist es fuer alle $n < 65536$ nicht prim, ausser fuer $n = 1, 2$.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:41 Do 07.07.2011 | | Autor: | reverend |
Hallo Felix,
es ist schon toll, was man heute mit ganz handelsüblichen und privat zugänglichen Rechnern so überprüfen kann. Was hätte Ramanujan wohl alles zeigen können, wenn er solche Möglichkeiten der Verifikation gehabt hätte?
Bisher sind wir ja dennoch eigentlich im Bereich recht kleiner k. Schade nur, dass [mm] 1194^n+1195^n [/mm] mit [mm] n=2^k [/mm] so schnell so groß wird.
Ich meine mich erinnern zu können, dass man die Suche sogar auf [mm] n=2^{2^k} [/mm] beschränken kann, finde dafür aber keinen Beleg oder gar Beweis. Bringe ich also nur etwas durcheinander?
Trotzdem frage ich mich, für welches k der Ausdruck wohl wieder prim wird, und ob die recht große Lücke wohl mit der Beziehung [mm] a^b+b^a=\text{prim} [/mm] zusammenhängt, wie auch immer?
Ansonsten suche ich gerade nach kürzeren Seitenwegen in der Faktorisierungsmethode von Shanks. Ich habe ein paar Ideen, aber keine wird griffig. Wenn das, was ich hoffe, auch nur annähernd funktionieren würde, wäre RSA tot. Mit anderen Worten: wahrscheinlich klappt da überhaupt nichts, nur die übliche Chimäre einer Anfangsvision spukt vor sich hin. Da ist die Zahlentheorie manchmal in geradezu faszinierender Weise frustrierend...
Demnächst werde ich wohl meine Schlafstatt mal einer Lauschattacke unterziehen müssen. In letzter Zeit waren zuviele Nächte pseudoprim.
Liebe Grüße
reverend
|
|
|
| |
|
> Da ist die Zahlentheorie manchmal in geradezu
> faszinierender Weise frustrierend...
das gibt ein tolles neues Wort:
[mm] $\mbox{\Huge{Fruszination !}}$
[/mm]
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:18 Do 07.07.2011 | | Autor: | felixf |
Moin!
> > Da ist die Zahlentheorie manchmal in geradezu
> > faszinierender Weise frustrierend...
>
> das gibt ein tolles neues Wort:
>
> [mm]\mbox{\Huge{Fruszination !}}[/mm]
Das Wort gefaellt mir sehr! Es beschreibt etwas, was gerade in der Mathematik sehr haeufig auftritt
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:26 Do 07.07.2011 | | Autor: | reverend |
Hallo Al,
> > > Da ist die Zahlentheorie manchmal in geradezu
> > > faszinierender Weise frustrierend...
> >
> > das gibt ein tolles neues Wort:
> >
> > [mm]\mbox{\Huge{Fruszination !}}[/mm]
>
> Das Wort gefaellt mir sehr! Es beschreibt etwas, was gerade
> in der Mathematik sehr haeufig auftritt
Glücklicherweise nicht nur in der Mathematik, so dass man noch Ausweichmöglichkeiten, will sagen: Auweimöglichkeiten hat.
Dein Wortentwurf ist überzeugend, ich bin sicher, das Wort wird sich durchsetzen. In wenigen Jahren wird die Duden-Reaktion fragen, ob jemand die Entstehung des Wortes datieren und belegen kann. Wir können.
Herzliche Grüße
reverend
|
|
|
| |
|
> Moin!
>
> > > Da ist die Zahlentheorie manchmal in geradezu
> > > faszinierender Weise frustrierend...
> >
> > das gibt ein tolles neues Wort:
> >
> > [mm]\mbox{\Huge{Fruszination !}}[/mm]
>
> Das Wort gefaellt mir sehr! Es beschreibt etwas, was gerade
> in der Mathematik sehr haeufig auftritt
>
> LG Felix
Bekomm ich jetzt dafür den Preis für das Wort des Jahres ?
Google kennt es bis jetzt jedenfalls noch nicht ...
Oh je ... englisch leider schon: "fruscination" scheint es auch im Sport zu geben:
Last season's breakout star wasn't a pitcher or a hitter, it was Mike (Awesome) Wilner of The FAN 590, a true mensch and oasis of intellect in an acrid desert of asinineness about all things baseball. Wilner shepherded the weak through a valley of "fruscination" last season with the way he used wit, logic and charm to knock off the endless parade of puckheads who call in to the post-game show to spew their hockey hullabuloo about grit and heart and ask why the Jays don't bunt or steal bases or go for other low-percentage offensive gambles.
(http://neatesager.blogspot.com/2008/03/batter-up-toronto-blue-jays.html)
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:28 Do 07.07.2011 | | Autor: | rabilein1 |
> Oh je ... englisch leider schon: "fruscination"
Hat dich diese Entdeckung fasziniert oder frustriert ?
Oder war sie fruszinierend ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:42 Do 07.07.2011 | | Autor: | reverend |
> Hat dich diese Entdeckung fasziniert oder frustriert ?
> Oder war sie fruszinierend ?
Oh, fruszinierend trifft es ziemlich präzakt, denke ich.
|
|
|
| |
|
en fait: absolument [mm] $\mbox{\Large{déprillusionnant}}$ [/mm] ! ![[heul]](/images/smileys/heul.gif "[heul]")
(aber das hat nun Google wirklich noch nicht !)
|
|
|
| |
|
melde gehorsamst:
mittlerweile hat es der Terminus "Fruszination" auch in
die Welt des Internets geschafft und kann ergoogelt oder
z.B. auch via Altavista gefunden werden ...
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:13 Mo 27.06.2011 | | Autor: | felixf |
Moin!
> Zeigen Sie, dass a=1194 und b=1195 die einzigen
> aufeinanderfolgenden Zahlen zwischen 1000 und 1500 sind,
> für die gilt:
> [mm]a^b + b^a[/mm] sind prim.
Das gilt uebrigens fuer
* $a = 2$, $b = 3$;
* $a = 80$, $b = 81$;
* $a = 342$, $b = 343$;
* $a = 848$, $b = 849$;
* $a = 1194$, $b = 1195$;
* $a = 2658$, $b = 2659$;
* $a = 4790$, $b = 4791$.
Fuer $a [mm] \le [/mm] 4790$ gibt es sonst keine solchen Paare. Ich lasse noch weitersuchen bis alles [mm] $\le [/mm] 10000$ abgegrast ist, aber ich weiss nicht wie lange das noch dauern wird...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:42 Mo 27.06.2011 | | Autor: | M.Rex |
Hallo.
Die aufkommende Diskussion, was von mathematischem Interesse sein sollte, habe ich mal in einer neuen Diskussionsrunde abgespalten.
Marius
|
|
|
|
