A262750 Least positive integer z such that n - phi(z^2) = x^2 + y^2 for some integers x and y with x*y*z even and phi(k^2) < n for all 0 < k < z, or 0 if no such z exists, where phi(.) is Euler's totient function given by A000010.

1, 1, 2, 2, 1, 1, 2, 4, 1, 1, 2, 2, 4, 1, 2, 4, 1, 1, 2, 2, 1, 2, 3, 4, 4, 1, 2, 2, 5, 1, 2, 6, 1, 2, 3, 2, 1, 1, 2, 4, 1, 1, 2, 4, 4, 1, 2, 4, 4, 1, 2, 2, 1, 1, 2, 5, 4, 3, 3, 2, 4, 1, 2, 6, 1, 1, 2, 8, 1, 2, 3, 4, 1, 1, 2, 2, 6, 3, 3, 4, 1, 1, 2, 2, 5, 1, 2, 4, 4, 1, 2, 2, 4, 6, 3, 8, 4, 1, 2, 2

Offset: 1

Author

Zhi-Wei Sun, Sep 30 2015

Keywords

• nonn

Comments

Conjecture: a(n) <= sqrt(n) except for n = 3, 8, 13, 32.

The conjecture in A262747 implies that a(n) > 0 for all n > 0.

Examples

			a(68) = 8 since 68 - phi(8^2) = 68 - 32 = 36 = 0^2 + 6^2 with 0*6*8 even and all those phi(k^2) (k = 1,...,7) smaller than 68.
a(5403) = 67 since 5403 - phi(67^2) = 5403 - 4422 = 981 = 9^2 + 30^2 with 9*30*67 even and all those phi(k^2) (k = 1,...,5403) smaller than 5403.
		

Links

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

Crossrefs

Cf. A000010, A001481, A002618, A233867, A262747.

Programs

Mathematica

f[n_]:=EulerPhi[n^2]
SQ[n_]:=IntegerQ[Sqrt[n]]
Do[Do[If[f[x]>n,Goto[aa]]; Do[If[SQ[n-f[x]-y^2]&&(Mod[x*y, 2]==0||Mod[n-f[x]-y^2, 2]==0),Print[n," ",x];Goto[bb]], {y, 0, Sqrt[(n-f[x])/2]}]; Continue, {x, 1, n}]; Label[aa];Print[n," ",0];Label[bb]; Continue, {n,1,100}]