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,7

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.

Links

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

Example

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.

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}]

Crossrefs

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

Sequence in context: A242667 A059581 A344319 * A297116 A163542 A061895

Adjacent sequences: A236995 A236996 A236997 * A236999 A237000 A237001

Keyword

nonn

Author

Zhi-Wei Sun, Feb 02 2014

Status

approved