login
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.
1
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,7
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.
EXAMPLE
a(7) = 2 since phi(2)*phi(7-2) = 1*4 = 2^2 but phi(1)*phi(7-1) = 2 is not a square.
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}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Zhi-Wei Sun, Feb 05 2014
STATUS
approved