OFFSET
1,1
COMMENTS
It is conjectured that if n>2 then all solutions of the equation sigma(x)-phi(x)=n (*) are less than or equal to (n-1)^2/4 and 2 is the only number n such that the equation (*) has infinitely many solutions. In fact in the case n=2 prime numbers are all solutions of (*). All numbers of the form 2p+1 where p is prime are in the sequence because p^2 is a solution for the equation sigma(x)-phi(x)=2p+1. All numbers of the form 3*2^n-1 are in the sequence because 2^(n+1) is a solution for the equation sigma(x)-phi(x)=3*2^n-1 and etc.
The conjecture in the previous comment was established by Luke Pebody, see the Rivera link.
Theorem (Luke Pebody): If integers n>2 and m satisfy sigma(m)-phi(m)=n then m<=(n-1)^2/4.
Proof: Case I: m=1. Then n=sigma(m)-phi(m)=0 is not more than 2.
Case II: m is prime. Then n=sigma(m)-phi(m)=(m+1)-(m-1)=2 is not more than 2.
Case III: m has at least one nontrivial divisor. Let m=pq where 1<p<m. Then sigma(m) is the sum of all of the distinct factors of m. Thus sigma(m)>=m+p+1. Phi(m) is certainly no greater than the number of integers smaller than or equal to m that are not divisible by p. Thus phi(m)<=m-q. Thus n=sigma(m)-phi(m)>=p+q+1. Finally, the arithmetic mean of two numbers is always greater than their geometric mean, so sqrt(m)=sqrt(pq)<=(p+q)/2<=(n-1)/2. Squaring both sides, m<=(n-1)^2/4.
LINKS
Robert Israel, Table of n, a(n) for n = 1..4490 (terms <= 10000)
Carlos Rivera, Puzzle 343. One more Faride's question, The Prime Puzzles and Problems Connection.
EXAMPLE
5 is in the sequence because 4 is a solution to the equation sigma(x)-phi(x)=5.
MAPLE
N:= 120: # for terms <= N
S:= {}:
for k from 1 to (N-1)^2/4 do
v:= numtheory:-sigma(k) - numtheory:-phi(k);
if v > 0 and v <= N then S:= S union {v} fi;
od:
sort(convert(S, list)); # Robert Israel, Jul 21 2025
CROSSREFS
KEYWORD
nonn
AUTHOR
Farideh Firoozbakht, Dec 12 2005
STATUS
approved