A262750 - OEIS

%I #12 Oct 01 2015 06:33:12

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

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

%U 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

%N 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.

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

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

%H Zhi-Wei Sun, <a href="/A262750/b262750.txt">Table of n, a(n) for n = 1..10000</a>

%e 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.

%e 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.

%t f[n_]:=EulerPhi[n^2]

%t SQ[n_]:=IntegerQ[Sqrt[n]]

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

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

%K nonn

%O 1,3

%A _Zhi-Wei Sun_, Sep 30 2015