cp's OEIS Frontend

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

%I A112730 #27 Jul 22 2025 18:19:40
%S A112730 2,5,7,10,11,14,15,16,18,20,22,23,24,26,27,28,30,32,33,34,35,36,38,39,
%T A112730 40,42,44,47,48,50,52,54,56,59,60,62,63,64,66,67,68,72,73,74,75,76,78,
%U A112730 79,80,83,84,86,87,88,90,92,94,95,96,98,100,102,104,106,107,108,110,112
%N A112730 Numbers k such that the equation sigma(x)-phi(x)=k has at least one solution.
%C A112730 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.
%C A112730 The conjecture in the previous comment was established by Luke Pebody, see the Rivera link.
%C A112730 Theorem (Luke Pebody): If integers n>2 and m satisfy sigma(m)-phi(m)=n then m<=(n-1)^2/4.
%C A112730 Proof: Case I: m=1. Then n=sigma(m)-phi(m)=0 is not more than 2.
%C A112730 Case II: m is prime. Then n=sigma(m)-phi(m)=(m+1)-(m-1)=2 is not more than 2.
%C A112730 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.
%H A112730 Robert Israel, <a href="/A112730/b112730.txt">Table of n, a(n) for n = 1..4490</a> (terms <= 10000)
%H A112730 Carlos Rivera, <a href="https://www.primepuzzles.net/puzzles/puzz_343.htm">Puzzle 343. One more Faride's question</a>, The Prime Puzzles and Problems Connection.
%e A112730 5 is in the sequence because 4 is a solution to the equation sigma(x)-phi(x)=5.
%p A112730 N:= 120: # for terms <= N
%p A112730 S:= {}:
%p A112730 for k from 1 to (N-1)^2/4 do
%p A112730   v:= numtheory:-sigma(k) - numtheory:-phi(k);
%p A112730   if v > 0 and v <= N then S:= S union {v} fi;
%p A112730 od:
%p A112730 sort(convert(S,list)); # _Robert Israel_, Jul 21 2025
%Y A112730 Complement of A036446.
%Y A112730 Cf. A051612.
%K A112730 nonn
%O A112730 1,1
%A A112730 _Farideh Firoozbakht_, Dec 12 2005