A112730 Numbers k such that the equation sigma(x)-phi(x)=k has at least one solution.

2, 5, 7, 10, 11, 14, 15, 16, 18, 20, 22, 23, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 47, 48, 50, 52, 54, 56, 59, 60, 62, 63, 64, 66, 67, 68, 72, 73, 74, 75, 76, 78, 79, 80, 83, 84, 86, 87, 88, 90, 92, 94, 95, 96, 98, 100, 102, 104, 106, 107, 108, 110, 112

Offset: 1

Author

Farideh Firoozbakht, Dec 12 2005

Keywords

• nonn

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

Examples

			5 is in the sequence because 4 is a solution to the equation sigma(x)-phi(x)=5.
		

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.

Crossrefs

Complement of A036446.

Cf. A051612.

Programs

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