Trends In Euler's Totient φ Function

While looking at the wiki page for Euler's totient function φ, we notice that Wiki has a graph of φ(n) versus n on the upper right side of the page, so we explore this result with Maple:

>p:=plot(liste,style=point, symbol=cross):

totient graph

One notices that the graph displays some obvious "trends" or lines where many points accumulate, so the author tried to figure out the approximate functions which describe those trends: First, it's obvious that the upper line is the line f(x)=x-1, since φ(p)=p-1, for p prime. Hence the highest line consists of primes.

The author fitted the rest of some lines, based on the rough heuristic that the next major trend looks like f in F1={x/2}, and continuing in the obvious way with f in F2={x/3,2*x/3}, F3={x/5,2*x/5,3*x/5,4*x/5}, F4={x/7,2*x/7,3*x/7,4*x/7,5*x/7,6*x/7}, F5={x/11,2*x/11,3*x/11,4*x/11,5*x/11,6*x/11,7*x/11,8*x/11,9*x/11,10*x/11}, etc.


The resulting graph combined with that of the totient:

totient graph 2
Key: Blue: F1; Cyan: F2; Yellow: F3; Magenta: F4; Green: F5;φ(n).

So the author set forth to ask this question in the newsgroup sci.math. He includes here Gerry Myerson's reply for completeness:

"As you noticed, if p is prime then φ(p) = p - 1, so there will be points just below y = x for each prime. But the primes are few and far between once you get to large values of x, so in a sense those points are not really very dense at all. But you also get close to y = x if n = p q with p and q both large primes. In fact, if n is any number all of whose prime factors are large then phi(n) will be relatively close to n.

If n = 2 p or n = 4 p or n = 8 p or ... where p is an odd prime then phi(n) is just less than n 2, so that gives you points near y = x 2. Numbers of the form 3 p, 9 p, 27 p, etc., give points near y = 2 x 3. Numbers 6 p, 12 p, 18 p, 24 p, 36 p, 48 p, 54 p, 72 p, etc., give points near y = x 3...."

Now let's dissect Gerry's answer: The highest line is indeed the line f(x)=x-1. Then:

For n=2kp, k in N, p odd prime:
(n)=(2kp)=2kp(1-1/2)(1-1/p)=(n/2)(p-1)/p. For large p, (p-1)/p ~ 1, hence also for large n, (n)~n/2, consequently these numbers follow approximately the trend f(x)=x/2.

For n=3kp, k in N, p prime > 3:
(n)=(3kp)=3kp(1-1/3)(1-1/p)=(2n/3)(p-1)/p. For large p, again (p-1)/p ~ 1, hence also for large n, (n) ~ 2 n/3, consequently these numbers follow the trend f(x)=2*x/3.

For n=2k3lp, k,l in N, p prime > 3:
(n)=2k3lp(1-1/2)(1-1/3)(1-1/p)=(n/2)(2/3)(p-1)/p=(n/3)(p-1)/p, hence again for large n, (n) ~ n/3, consequently these numbers follow the trend f(x)=x/3.

Let's do some more:

For n=5kp, k in N, p prime > 5:
(n)=5kp(1-1/5)(1-1/p)=(4n/5)(p-1)/p, hence for large n, (n) ~ 4n/5, consequently these numbers follow the trend f(x)=4*x/5.

For n=2k5lp, k,l in N, p prime > 5:
(n)=n(1-1/2)(1-1/5)(1-1/p)=(2n/5)(p-1)/p, hence the trend f(x)=2*x/5.

For n=3k5lp, k,l in N, p prime > 5:
(n)=n(1-1/3)(1-1/5)(1-1/p)=(8n/15)(p-1)/p, hence the trend f(x)=8*x/15.

For n=2k3l5mp, k,l,m in N, p prime > 5:
(n)=n(1-1/2)(1-1/3)(1-1/5)(1-1/p)=(4n/15)(p-1)/p, hence the trend f(x)=4*x/15.

Here is the graph with all the trends for n=2k3l5m7qp, k,l,m,q in N U {0}, p prime > 7:

totient graph 3
Key: Black: {x-1} (primes}; Blue: {x/2}; Cyan: {x/3,2*x/3}; Yellow: {2*x/5,4*x/5}; Magenta: {4*x/15,8*x/15};
Green: {2*x/7,3*x/7,4*x/7,6*x/7}; Grey: {8*x/35,12*x/35,16*x/35,24*x/35};

Now let's look at some actual counts:

> margin:=2;
> trends:=16;
> c:=array(1..trends);
> for n from 1 to trends do
> c[n]:=0;
> od:
> for n from 1 to lim do
> t:=phi(n);
> if abs(t-n)<=margin then
> c[1]:=c[1]+1;
> elif abs(t-n/2)<=margin then
> c[2]:=c[2]+1;
> elif abs(t-n/3)<=margin then
> c[3]:=c[3]+1;
> elif abs(t-2*n/3)<=margin then
> c[4]:=c[4]+1;
> elif abs(t-2*n/5)<=margin then
> c[5]:=c[5]+1;
> elif abs(t-4*n/5)<=margin then
> c[6]:=c[6]+1;
> elif abs(t-4*n/15)<=margin then
> c[7]:=c[7]+1;
> elif abs(t-8*n/15)<=margin then
> c[8]:=c[8]+1;
> elif abs(t-2*n/7)<=margin then
> c[9]:=c[9]+1;
> elif abs(t-3*n/7)<=margin then
> c[10]:=c[10]+1;
> elif abs(t-4*n/7)<=margin then
> c[11]:=c[11]+1;
> elif abs(t-6*n/7)<=margin then
> c[12]:=c[12]+1;
> elif abs(t-8*n/35)<=margin then
> c[13]:=c[13]+1;
> elif abs(t-12*n/35)<=margin then
> c[14]:=c[14]+1;
> elif abs(t-16*n/35)<=margin then
> c[15]:=c[15]+1;
> elif abs(t-24*n/35)<=margin then
> c[16]:=c[16]+1;
> else ;
> fi;
> od:
> p1:=plot([[1,0],[1,evalf(c[1]/lim)]],color=black):#x-1
> p2:=plot([[2,0],[2,evalf(c[2]/lim)]],color=blue):#x/2
> p3:=plot([[3,0],[3,evalf(c[3]/lim)]],color=cyan):#x/3
> p4:=plot([[4,0],[4,evalf(c[4]/lim)]],color=cyan):#2*x/3
> p5:=plot([[5,0],[5,evalf(c[5]/lim)]],color=yellow):#2*x/5
> p6:=plot([[6,0],[6,evalf(c[6]/lim)]],color=yellow):#4*x/5
> p7:=plot([[7,0],[7,evalf(c[7]/lim)]],color=magenta):#4*x/15
> p8:=plot([[8,0],[8,evalf(c[8]/lim)]],color=magenta):#8*x/15
> p9:=plot([[9,0],[9,evalf(c[9]/lim)]],color=green):#2*x/7
> p10:=plot([[10,0],[10,evalf(c[10]/lim)]],color=green):#3*x/7
> p11:=plot([[11,0],[11,evalf(c[11]/lim)]],color=green):#4*x/7
> p12:=plot([[12,0],[12,evalf(c[12]/lim)]],color=green):#6*x/7
> p13:=plot([[13,0],[13,evalf(c[13]/lim)]],color=grey):#8*x/35
> p14:=plot([[14,0],[14,evalf(c[14]/lim)]],color=grey):#12*x/35
> p15:=plot([[15,0],[15,evalf(c[15]/lim)]],color=grey):#16*x/35
> p16:=plot([[16,0],[16,evalf(c[16]/lim)]],color=grey):#24*x/35

> with(plots):
> display({p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,p16});

totient counts
Key: Black: P(n=prime);
Blue: P(n=2kq,q:prime>2);
Cyan: P(n=2k3lq,q:prime>3), P(n=3kq,q:prime>3);
Yellow: P(n=2k5lq,q:prime>5), P(n=5kq,q:prime>5);
Magenta: P(n=2k3l5mq,q:prime>5), P(n=3k5lq:,q:prime>5);
Green: P(n=2k3l7mq,q:prime>7), P(n=2k7lq,q:prime>7), P(n=3k7lq,q:prime>7), P(n=7kq,q:prime>7);
Grey: P(n=2k3l5m7oq,q:prime>7), P(n=2k5l7mq,q:prime>7), P(n=3k5l7mq,q:prime>7), P(n=5k7lq,q:prime>7);

P(n=prime)=c[1]/lim ~ 0.1525
Prime number theorem gives: P(n=prime)=1/log(lim) ~ 0.1315633249

Running the same program for lim=10000, we find thus:

P(n=prime)=c[1]/lim ~ 0.1231

Prime number theorem gives: P(n=prime)=1/log(lim) ~ 0.1085736205

In a sense, the above probabilities represent the "density" of the trend lines in the graph of for the space [1..lim].

For a slightly deeper analysis, consult this answer on math.StackExchange.

Back to Mathematics

Web Analytics Made Easy -

Valid HTML 4.01 Transitional