On an iterated arithmetic function problem of Erdos and Graham

2025/04/10 by Stefan Steinerberger, Steinerberger, Stefan · 1 citation
Mathematics · #Mathematics and Applications #Advanced Mathematical Identities #Analytic Number Theory Research

paper · pdf · doi:10.48550/arxiv.2504.08023

Abstract

Erdős and Graham define g(n) = n + ϕ(n) and the iterated application g_k(n) = g(g_k-1(n)). They ask for solutions of g_k+r(n) = 2 g_k(n) and observe g_k+2(10) = 2 g_k(10) and g_k+2(94) = 2 g_k(94). We show that understanding the case r = 2 is equivalent to understanding all solutions of the equation ϕ(n) + ϕ(n + ϕ(n)) = n and find the explicit solutions n = 2^ℓ ⋅ \1,3,5,7,35,47\. This list of solutions is possibly complete: any other solution derives from a number n=2^ℓ p where p ≥ 10¹⁰ is a prime satisfying ϕ((3p-1)/4) = (p+1)/2. Primes with this property seem to be very rare and maybe no such prime exists.

Cited by

• On Positive Integers n with ϕ(n)=(2)/(3) ⋅ (n+1)

Related

• On Positive Integers n with ϕ(n)=(2)/(3) ⋅ (n+1)
• A conjecture of Erdos, supersingular primes and short character sums
• Primes of the form ax+by in certain intervals with small solutions
• Solutions of the problem of Erdös-Sierpiński: σ(n)=σ(n+1)
• Well-defined Erdös-Straus equations and L.C.M