A248006 Least positive integer m such that m + n divides phi(m*n), where phi(.) is Euler's totient function.

3, 4, 3, 6, 5, 8, 9, 6, 9, 4, 11, 7, 5, 16, 7, 9, 5, 12, 7, 18, 21, 8, 15, 13, 27, 14, 11, 10, 14, 32, 7, 14, 5, 12, 35, 10, 13, 24, 7, 14, 13, 11, 9, 42, 45, 16, 11, 30, 13, 12, 19, 27, 33, 8, 15, 22, 28, 4, 35, 28, 18, 64, 7, 14, 21, 28, 19, 10

Offset: 3

Author

Zhi-Wei Sun, Sep 29 2014

Keywords

• nonn

Comments

Conjecture: For any n > 2, a(n) exists and a(n) <= n.

See also A248007 and A248008 for similar conjectures. - Zhi-Wei Sun, Sep 29 2014

The conjecture is true: One can show that 2*n divides phi(n^2) for all n > 2. So, a(n) is at most n. - Derek Orr, Sep 29 2014

a(n) >= 3 for all n. - Robert Israel, Sep 29 2014

Examples

			a(5) = 3 since 3 + 5 divides phi(3*5) = 8.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 3..10000
• Zhi-Wei Sun, A new theorem on the prime-counting function, arXiv:1409.5685, 2014.

Crossrefs

Cf. A000010, A248004, A248007, A248008.

Programs

Maple

f:= proc(n)
local m;
for m from 3 do
  if numtheory:-phi(m*n) mod (m+n) = 0 then return m fi
od
end proc;
seq(f(n),n=3..100); # Robert Israel, Sep 29 2014

Mathematica

Do[m=1;Label[aa];If[Mod[EulerPhi[m*n],m+n]==0,Print[n," ",m];Goto[bb]];m=m+1;Goto[aa];Label[bb];Continue,{n,3,70}]

PARI

a(n)=m=1;while(eulerphi(m*n)%(m+n),m++);m
vector(100,n,a(n+2)) \\ Derek Orr, Sep 29 2014