Eulers Totient Funktion

22/08/2009 - 16:14 von Peter | Report spam
Eulers Totient Funktion

.. oder auch phi-Funktion genannt, ist eine ziemlich
wilde, obwohl sie nichts anderes macht als die Anzahl
der zu n teilerfremden Zahlen t angibt (0<t<=n).

Zum Beispiel:

phi(5459) = 5304;
phi(5460) = 1152;
phi(5461) = 5292;

Aber ihrem Lauf sind Schranken gesetzt. Betrachten
wir im Weiteren nur *zusammengesetztes n*.

Sierpinski hat dafür eine /obere/ Schranke angegeben:

phi(n) < n - sqrt(n)

Was ich nicht kenne ist eine vergleichbar einfache
und genaue /untere/ Schranke.

[1] Kennt jemand so eine Schranke?

Also habe ich mir selber eine gebastelt.

(1/2 - gamma/2)(n - sqrt(n)) < phi(n)

D. h. die obere Schranke mit

0,2113921...

multipliziert. Noch habe ich keinen Beweis dafür
dass sie stets gültig ist.

[2] Sollte jemand ein Gegenbeispiel finden bitte
melden. (Oder mir mit der Meldung Mut machen:
"Bis x-tausend kein Gegenbeispiel gefunden.")

[3] Sollte jemand einen Beweis kennen und ihn uns
verraten, dann wird ihm Unsterblichkeit gewiss sein.

Gruss Peter
 

Lesen sie die antworten

#1 Helmut Richter
22/08/2009 - 18:43 | Warnen spam
On Sat, 22 Aug 2009, Peter wrote:

(1/2 - gamma/2)(n - sqrt(n)) < phi(n)

D. h. die obere Schranke mit

0,2113921...



Also soll sein: C (n - sqrt(n)) < phi(n)

für eine Konstante C.

Es ist

(n - sqrt(n)) / n = 1 - 1/sqrt(n) >= 1/2

für n >= 4 (n war zusammengesetzt). Also ist

n - sqrt(n) > n/2, mithin

Cn/2 < C (n - sqrt(n)) < phi(n)

mithin

phi(n)/n > C/2

phi(n)/n ist aber das Produkt der (1 - 1/p) über die in n enthaltenen
Primfaktoren, und man sieht, dass man das durch Hinzunahme weiterer
primfaktoren beliebig klein kriegt. Eine solche Konstante C kann es daher
nicht geben.

Für das gegebene C sollte als n das Produkt der Primzahlen bis 191
ausreichen, wenn man die Abschàtzung am Anfang zugrundelegt. Tut man das
nicht, reicht das Produkt der Primzahlen bis 13 aus, eine durchaus
handliche Zahl:

n = 30030
C(n-sqrt(n) = 6311.4742915503904956427
phi(n) = 5760

Wie macht man denn Schranken, wenn man keine Idee hat, wie man sie
beweisen kann?

Helmut Richter

Ähnliche fragen