Reverse Eulersche Phi-Funktion

Neue Frage »

Brotscheibe Auf diesen Beitrag antworten »
Reverse Eulersche Phi-Funktion
Meine Frage:
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.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Brotscheibe
Phi() ist multiplikativ, also ist phi(mn) = phi(m) * phi(n). Aber hilft mir das weiter?

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.
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.
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.
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".
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.
 
 
HAL 9000 Auf diesen Beitrag antworten »

ist schnell erledigt, da Primfaktor 2 nur einmal drin ist. Augenzwinkern

Aber sieht nach einer hübsch umfangreichen Fallunterscheidung aus - viel Spaß. Big Laugh


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 . Big Laugh
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.
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. Augenzwinkern



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.
Brotscheibe Auf diesen Beitrag antworten »

Vielen Dank bis hierher Freude

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.
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

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
beginproc
    resultset = {}
    for (t | (p/2)) do
        q = 2t+1
        if (q prim) and (q not in A) then
            p1 = p/(q-1)
            resultset = resultset cup InversPhi(p1, A cup {q})*q
            qp = q;
            while (q | p1) do
                p1 = p1/q
                qp = qp*q
                resultset = resultset cup InversPhi(p1, A cup {q})*qp
            endwhile
        endif
    endfor
    return resultset
endproc
(| steht für "teilt", in für "ist enthalten in" und cup für Mengenvereinigung).

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. Augenzwinkern

EDIT: Hinsichtlich Primfaktor 2 ist auch noch eine "Gurke" drin. Big Laugh


EDIT2: Nach dem Pseudo- jetzt mal richtiger MuPad-Code

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
InversPhi := proc(p,A={}) 
  local p1,q,qp,s ;
  option remember ;
  begin
    s := {} :
    if (p = 1) then
      if contains(A,2) then
         s:={1}
      else
         s:={1,2}
      end_if
    elif (p mod 2 = 0) then
      for q in [2].(2*numlib::divisors(p/2)+1) do
        if isprime(q) and not contains(A,q) then
          p1 := p/(q-1) :
          qp := q :
          A := A union {q} :
          while (p1 = floor(p1)) do
            s := s union InversPhi(p1,A)*qp :
            qp := qp*q :
            p1 := p1/q
          end_while
        end_if
      end_for
    end_if ;
    s
  end_proc ;
Soweit ich das nach ein paar Testläufen beurteilen kann, haut das so hin.
Brotscheibe Auf diesen Beitrag antworten »

Ein Wahnsinns Hammer! Big Laugh
HAL 9000 Auf diesen Beitrag antworten »

Anscheinend hast du das noch nicht getestet, denn ich erwarte statt Big Laugh ja doch eher ein Gott - oder auch vielleicht ein Forum Kloppe , wenn du einen Fehler findest.
Brotscheibe Auf diesen Beitrag antworten »

Erstmal alles von MuPad nach irgendwas bekommen. Dann ganz sicher Gott
Brotscheibe Auf diesen Beitrag antworten »

Funktioniert das auch in Matlab?
HAL 9000 Auf diesen Beitrag antworten »

Bei leidlich neuen Matlabs ist Mupad integriert: Einfach mal "mupad" in der Matlab-Kommandozeile eintippen.
Brotscheibe Auf diesen Beitrag antworten »

Wenn mein PC nicht verkackt kann ich Matlab 8 nutzen. Ich hoffe das das neu genug ist verwirrt
HAL 9000 Auf diesen Beitrag antworten »

War das nicht deutlich genug:
Zitat:
Original von HAL 9000
Einfach mal "mupad" in der Matlab-Kommandozeile eintippen.

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.
Brotscheibe Auf diesen Beitrag antworten »

Gott Knorke! Gott

Könntest du mir noch sagen wie ich mir nur ein gewißes Element aus dem Set anzeigen lassen kann?
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
Brotscheibe Auf diesen Beitrag antworten »

Fettesten Dank nochmal! Freude Gott

Ich frag mich immer wieder wie man soviel Ahnung von so was haben kann verwirrt
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 verwirrt 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.
Dirk_F Auf diesen Beitrag antworten »

Sehr gut, danke Freude
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
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. Augenzwinkern
Dirk_F Auf diesen Beitrag antworten »

Jetzt schon ein Dankeschön an alle Helfer. Wenn ich das Krankenhaus überstanden habe, melde ich mich wieder Freude
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »