Reverse Eulersche Phi-Funktion |
11.08.2015, 20:32 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Reverse Eulersche Phi-Funktion Gegeben sei phi(n) = p. Kann man aus p nun ableiten welche Zahlen für n in Frage kommen? Meine Ideen: Phi() ist multiplikativ, also ist phi(mn) = phi(m) * phi(n). Aber hilft mir das weiter? Momentan stehe ich so richtig aufm Schlauch. |
||||||||||||
11.08.2015, 21:05 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Doch, schon: Ist die Primfaktorzerlegung von , so ist ja dann , mit . Insbesondere sind letztere Werte immer gerade (außer für ), also begrenzt der Exponent des Primfaktors 2 in deinem gegebenen schon mal die Anzahl der verschiedenen Primfaktoren in ... Der Rest ist sorgfältige Fallunterscheidung. |
||||||||||||
12.08.2015, 21:42 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Das klingt danach, dass ich mein (mn) faktorisieren und dann Zahlen finden muss die jeweils das phi() aufweisen und multiplizieren. |
||||||||||||
13.08.2015, 08:29 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Ja, so ungefähr. Am besten nennst du mal ein konkretes , an dem wir das durchsprechen können. Soweit ich mich erinnere, gab es dazu hier im Board auch schon den einen oder anderen Thread zu diesem Thema, hab jetzt aber noch nicht konkret gesucht. |
||||||||||||
13.08.2015, 10:59 | Leopold | Auf diesen Beitrag antworten » | ||||||||||
Bemerkung am Rande: Mich stört das Wort "reverse". Das scheint mir aus der englischsprachigen mathematischen Literatur zu kommen. Im Deutschen sagt man aber wohl eher "invers". |
||||||||||||
13.08.2015, 11:01 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Ich dachte z.B. an 9! = 362880 bzw 17# = 510510, weil es gerade in diesen Fällen auch ne Menge Teiler gibt. |
||||||||||||
Anzeige | ||||||||||||
|
||||||||||||
13.08.2015, 11:34 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
ist schnell erledigt, da Primfaktor 2 nur einmal drin ist. Aber sieht nach einer hübsch umfangreichen Fallunterscheidung aus - viel Spaß. EDIT: Spaßeshalber habe ich mal per Brute-Force nach Lösungen für suchen lassen - Ergebnis: 1138 Lösungen, von der kleinsten bis zur größten . |
||||||||||||
13.08.2015, 16:22 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Ich habe bislang einen Brute Force Algorithmus der phi über die Primfaktoren ohne gcd berechnet. Damit habe ich nur die Schwierigkeiten dass ich die Laufweite auf das Quadrat von phi gesetzt hab. Bei phi(n) = 6 also auf 36 obwohl ich nur von 7 bis 18 durchsuchen müsste. In Form dauert es für größere Zahlen wie 9! natürlich ewig. |
||||||||||||
13.08.2015, 16:39 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Nun ja, man kann schon grob (aber gut genug) abschätzen, in welchem Bereich man die mit suchen muss: Die Zahl enthalte den Primfaktor 2 genau -mal, dann kann maximal verschiedene ungerade Primfaktoren enthalten (siehe oben), sowie evtl. noch Primfaktor 2. Somit gilt , wenn mit die Folge der Primzahlen gemeint ist. Umgestellt ergibt das . Im obigen Beispiel mit und damit würde dies ergeben, d.h. als gesamter Untersuchungsbereich . Angesichts dessen, dass die letzte passende Zahl war, geht es eigentlich mit der "Grobheit" der Abschätzung. P.S.: Bei mit einer ungeraden Zahl kommt potentiell nur noch sowie mit einer ungeraden Primzahl in Frage. Über ist dann folgendes klar: passt nur, wenn prim ist. Für kann nur der größte Primfaktor von sein. Ob das dann mit irgendeinem m "passt", muss man sehen. Am Beispiel mit demnach : liefert und damit die Lösungen 7 und 14. bedeutet , und in der Folge und damit die Lösungen 9 und 18. |
||||||||||||
14.08.2015, 12:05 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Vielen Dank bis hierher Der Hinweis zur Lauflänge mit dem Produkt(p_k / p_k-1) [k = 1; k <= m+1] war äußerst hilfreich. Jetzt gehts an den Kleinkram weil die Laufzeit mit steigendem phi ja auch immer mehr wird und dann ewig dauert. |
||||||||||||
14.08.2015, 13:29 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Du redest jetzt von jenem Bruteforce-Algorithmus, den auch ich oben angewandt hatte? Wenn du das ganze für noch größere Zahlen durchführen willst, dann lohnt es sich ja vielleicht doch, Zerlegungen gemäß meiner oben skizzierten Vorgehensweise durchzuführen, statt alle Zahlen eines doch recht umfangreichen Intervalls abzuklappern. Ich könnte mir folgendes rekursive Vorgehen vorstellen anhand einer rekursiven Funktion: set InversPhi (int p, set A) soll die Menge aller möglichen mit liefern, wobei keine Primfaktoren aus der Menge enthalten darf. Der Ablauf dieser Funktion wäre dann schematisch so
So in etwas müsste es eigentlich klappen. Wahrscheinlich kann man hier und da einige Ineffizienzen ausbügeln (wenn ich das richtig sehe, kann bei obigen Ablauf ein und dieselbe Lösung mehrfach der Menge beigefügt werden, was zwar nicht schadet, aber vielleicht auch nicht sein muss). Und außerdem fehlt die Abbruchbedingung, kannst du dir ja selbst überlegen falls du diesen Ansatz weiter verfolgen willst - so wie oben ohne Abbruchbedingung geht es nicht. EDIT: Hinsichtlich Primfaktor 2 ist auch noch eine "Gurke" drin. EDIT2: Nach dem Pseudo- jetzt mal richtiger MuPad-Code
|
||||||||||||
14.08.2015, 15:37 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Ein Wahnsinns Hammer! |
||||||||||||
14.08.2015, 15:41 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Anscheinend hast du das noch nicht getestet, denn ich erwarte statt ja doch eher ein - oder auch vielleicht ein , wenn du einen Fehler findest. |
||||||||||||
14.08.2015, 15:50 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Erstmal alles von MuPad nach irgendwas bekommen. Dann ganz sicher |
||||||||||||
14.08.2015, 15:56 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Funktioniert das auch in Matlab? |
||||||||||||
14.08.2015, 16:02 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Bei leidlich neuen Matlabs ist Mupad integriert: Einfach mal "mupad" in der Matlab-Kommandozeile eintippen. |
||||||||||||
14.08.2015, 16:45 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Wenn mein PC nicht verkackt kann ich Matlab 8 nutzen. Ich hoffe das das neu genug ist |
||||||||||||
14.08.2015, 17:11 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
War das nicht deutlich genug:
Entweder geht ein MuPad-Fenster auf (wenn das Matlab neu genug ist, ab 2008 oder 2009) oder eben nicht, da gibt's nix zu rätseln. |
||||||||||||
14.08.2015, 18:19 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Knorke! Könntest du mir noch sagen wie ich mir nur ein gewißes Element aus dem Set anzeigen lassen kann? |
||||||||||||
14.08.2015, 18:30 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Na das sind ja jetzt eher MuPad-technische Fragen - wenn das ausartet, mach besser einen neuen Thread auf. S := InversPhi(9!) ; nops(S); // Kardinalzahl der Menge S[5] ; // das fünftkleinste Elemente der Menge |
||||||||||||
14.08.2015, 18:32 | Brotscheibe | Auf diesen Beitrag antworten » | ||||||||||
Fettesten Dank nochmal! Ich frag mich immer wieder wie man soviel Ahnung von so was haben kann |
||||||||||||
16.12.2015, 14:13 | Dirk_F | Auf diesen Beitrag antworten » | ||||||||||
Inverse Phi-Funktion *neu* Unter matheboard / thread.php?threadid=559134 wurde durch Brotscheibe nach der "reversen Eulerschen Phi-Funktion" gefragt. Interessante Sache. In einem ähnlichen Thread auf Stackexchange bei Google nach finding all natural numbers where 110 totient site:stackexchange.com suchen) geht's um die Zahl 110 und dazu gehörig deren Primfaktorisierung = 2*5*11. Allerdings durchschaue ich weder hier noch dort so richtig die Lösungsfindung Auf Stackexchange sprechen die Kommentatoren vom Dividieren des Phi-Wertes durch (p-1), wobei p ein Primfaktor des Wertes ist. Im Beispiel 110 ist das nur bei 2 und 11 möglich, da 110 mod 4 != 0. Was hat das speziell bei der Suche nach n zu bedeuten, durch (p-1) zu dividieren, wenn ich phi(n) gegeben habe, bspw. 110? Im Thread von Brotscheibe wird eine ähnliche Division von HAL9000 erwähnt, aber offenbar nur um den Ergebnisbereich abzuschätzen. Ich hoffe, es wird mir verziehen, aber es interessiert mich ebenso, wie ich das kleinste n finde bei gegebenem phi(n). Im Beispiel von Brotscheibe mit 9! hatte HAL9000 dann 364.087 = 577 * 631 ermittelt. Und wie kommt es dass u. a. 14 gar nicht als mögliches phi(n) auftaucht? Ich weiß, dass ist viel und sicherlich zum Teil auch doppelt gemoppelt. Ggf. könnte ein Admin die beiden Threads zusammenführen, wenn es nicht gewünscht ist, dass der hier separat besteht. Hab ich jetzt gemacht. Es ist ja dasselbe Thema. Steffen Danke schonmal! PS: Ich hätte gern die Links als solche eingefügt, ließ sich aber als Gast nicht machen. |
||||||||||||
16.12.2015, 14:30 | Dirk_F | Auf diesen Beitrag antworten » | ||||||||||
Sehr gut, danke |
||||||||||||
16.12.2015, 15:51 | ollie3 | Auf diesen Beitrag antworten » | ||||||||||
Hallo, Einige fragen kann ich dir beantworten: Bei der eulerschen phi-funktion gilt immer phi(a*b)=phi(a)*phi(b), wenn a und b teilerfremd sind, Und es gilt phi(p)=p-1 für alle Primzahlen p. Dadurch erklären sich die meisten deiner fragen. Gruss ollie3 |
||||||||||||
16.12.2015, 16:47 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
@DirkF Ganz früh hier im Thread taucht folgende Erkenntnis auf: Ist mit , so kann höchstens eine ungerade Primzahl als Primfaktor enthalten. Genauer gesagt: für so ein ist allenfalls für oder mit einer ungeraden Primzahl möglich (aber auch das ist nicht garantiert). Wegen sind wir genau in diesem Fall. Nun kann man bei durchprobieren: würde bedeuten, das ist aber keine Primzahl. bedeutet , was für erfüllt ist. kommt nicht in Frage, da 110 keinen Primfaktor mit Ordnung >2 enthält. Bleibt demnach nur , also die Zahlen sowie als Lösungen. Dassselbe für , d.h. nunmehr : würde bedeuten, das ist keine Primzahl. würde bedeuten, ohne ganzzahlige Lösung. kommt nicht in Frage, da 14 keinen Primfaktor mit Ordnung >2 enthält. Hier also gar keine Lösung. Wie gesagt, alles noch sehr übersichtlich - die Sache wird erst dann zunehmend ausufernd, je öfter der Primfaktor 2 im gegebenen Funktionswert enthalten ist. Wie bei , wo die 2 doch schon 7-mal enthalten ist. |
||||||||||||
19.12.2015, 15:36 | Dirk_F | Auf diesen Beitrag antworten » | ||||||||||
Jetzt schon ein Dankeschön an alle Helfer. Wenn ich das Krankenhaus überstanden habe, melde ich mich wieder |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |