A236998 a(n) = |{0 < k < n/2: phi(k)*phi(n-k) is a square}|, where phi(.) is Euler's totient function.

0, 0, 1, 0, 0, 1, 2, 0, 2, 2, 1, 1, 2, 1, 1, 1, 1, 3, 3, 2, 2, 4, 3, 1, 3, 1, 3, 1, 1, 2, 2, 1, 4, 4, 3, 3, 1, 1, 5, 2, 3, 7, 2, 5, 3, 4, 3, 2, 7, 3, 2, 3, 4, 6, 2, 1, 7, 5, 3, 2, 2, 4, 4, 2, 6, 4, 3, 5, 5, 7, 4, 3, 2, 6, 4, 2, 7, 5, 5, 4, 4, 2, 4, 8, 2, 7, 5, 7, 3, 3, 8, 6, 7, 5, 7, 3, 9, 3, 7, 5

Offset: 1

Author

Zhi-Wei Sun, Feb 02 2014

Keywords

• nonn

Comments

Conjecture: (i) a(n) > 0 for all n > 8.

(ii) If n > 20, then phi(k)*phi(n-k) + 1 is a square for some 0 < k < n/2.

(iii) If n > 1 is not among 4, 7, 60, 199, 267, then k*phi(n-k) is a square for some 0 < k < n.

We have verified part (i) of the conjecture for n up to 2*10^6.

Examples

			a(17) = 1 since phi(5)*phi(12) = 4*4 = 4^2.
a(24) = 1 since phi(4)*phi(20) = 2*8 = 4^2.
a(56) = 1 since phi(8)*phi(48) = 4*16 = 8^2.
		

Links

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

Crossrefs

Cf. A000010, A000290, A234246, A236567, A237016.

Programs

Mathematica

SQ[n_]:=IntegerQ[Sqrt[n]]
p[n_,k_]:=SQ[EulerPhi[k]*EulerPhi[n-k]]
a[n_]:=Sum[If[p[n,k],1,0],{k,1,(n-1)/2}]
Table[a[n],{n,1,100}]