A237203 Least positive integer k < n/2 with phi(k)*phi(n-k) a square, or 0 if such a number k does not exist.

0, 0, 1, 0, 0, 1, 2, 0, 1, 2, 1, 2, 1, 2, 5, 7, 5, 1, 2, 4, 6, 3, 3, 4, 6, 6, 3, 4, 12, 3, 4, 14, 1, 2, 1, 2, 5, 1, 2, 8, 1, 2, 16, 6, 5, 7, 10, 8, 1, 2, 17, 7, 5, 3, 4, 8, 3, 1, 2, 6, 1, 2, 7, 1, 2, 11, 3, 4, 12, 6

Offset: 1

Author

Zhi-Wei Sun, Feb 05 2014

Keywords

• nonn

Comments

Conjecture: a(n) < sqrt(n)*log(2*n) for all n > 0.

We have verified this for n up to 2*10^5. Note that a(211) = 85 > sqrt(211)*log(211) and a(373) = 117 > sqrt(373)*log(373).

According to the conjecture in A236998, a(n) should be positive for all n > 8.

Examples

			 a(7) = 2 since phi(2)*phi(7-2) = 1*4 = 2^2 but phi(1)*phi(7-1) = 2 is not a square.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A000290, A236998.

Programs

Mathematica

SQ[k_,m_]:=IntegerQ[Sqrt[EulerPhi[k]*EulerPhi[m]]]
Do[Do[If[SQ[k,n-k],Print[n," ",k];Goto[aa]],{k,1,(n-1)/2}];
Print[n," ",0];Label[aa];Continue,{n,1,70}]