Problems & Puzzles: Puzzles
Puzzle 76.- z(n)=sigma(n) + phi(n) - 2n
(An example of an email-born-puzzle, by Jud McCranie & Carlos Rivera, November 1999)
It's well known that if n = p^a.q^b. etc., then
Jud's observation (9/11/99):
"When p is prime sigma(p) = p+1 and phi(p) = p-1, so sigma(p)+phi(p) = 2p, …. I was wondering if sigma(n)+phi(n)=2n ever happens when n isn't prime…"
My reply (10/11/99):
"Then it seems interesting define z(n) as z(n)=sigma(n) +phi(n)-2n. Obviously z(p)=0. Less obvious is that z(p^2)=1 and z(p*q)=2. Can you see other properties of z(n)?"
(11/11/99) sigma(Perfect)=2n, then z(Perfect)=phi(Perfect)
(12/11/99): z(p^3)=p+1, z(p^4)=p(p+1)+1, this must generalize z(p^k)=p(p(p….+1)+1)+1 opening and closing (k-3) parentheses
(12/11/99): z(pqr)=2(p+q+r), p,q,r distinct primes
Later I saw that z(p^k)=1+p+p^2+p^3+…+p^(k-2) and then Jud reminded to me that sigma(p^k)= 1+p+p^2+p^3+…+p^k, and also that sigma and phi are multiplicative functions, that is to say: sigma(x.y)=sigma(x).sigma(y) and phi(x.y)=phi(x).phi(y), if gcd(x,y)=1.
With these hints I deduced (the known fact) that phi(p^k)=(p-1)*p^(k-1) and consequently phi(Perfect)=2^(p-2).(2^p-2)
In B37, p. 92, "Unsolved Problems in Number theory", R. K. Guy, I found that "Subbarao also notes that …. p.sigma(p)=2 mod phi(p), and also for n=4, 6 & 22" (*), and Jud found (**) also that "6n^2/pi^2 < phi(n)*sigma(n) < n^2".
This is enough! Now, the questions are:
1. sigma(n)+phi(n)=2n ever happens when n isn't prime…?…(This is the very original Jud's question)
2. Does exists a formula to calculate directly z(n) for the general case n=p^a.p^b. etc
3. Find composite numbers, other than 4, 6 & 22, such that applies the Subbarao relation.
(*)This is also
Chris Nash has solved (20/12/99) the question 1 of this puzzle and consequently and in certain unexpected manner (applying the Möbius function to each divisor of n - see the equation 7 ) the question 2 also... I must confess that I'm completely astonished for the beauty of this reasoning and in particular for the unknown (for me) trick of the so called "Möbius inversion formula"....phew!!!
1 DefinitionsWe define the function z(n) on positive integers n by
2 Solution of Puzzle 76z(n) ³ 0, with equality only holding if n = 1 or n is prime.
In particular, this means n cannot have two or more distinct prime factors. If n had distinct prime factors p and q, choose d = n/pq and we have a contradiction with (8). Hence n must be a power of a prime.
Similarly, if n = pr for some r > 1, choose d = 1 and again we have a contradiction with (8).
Finally it is easy to demonstrate that, if n is prime, f(n) = n-1 and s(n) = n+1.
Hence z(n) = 0 if and only if n = 1, or n is prime
Chris Nash has also solved (21/12/99) the
question 3 ..."Using an elegant function [z(n)] discussed by
Carlos Rivera and Jud McCranie at
Farideh Firoozbakht wrote on Jan-2015: