login
Least k such that phi(n) = phi(k) + phi(n-k) for 0<k<n, or 0 if there is no such k, where phi is Euler's totient function.
5

%I #10 Feb 20 2023 12:26:20

%S 0,0,1,2,0,0,0,4,4,4,0,6,0,4,5,8,0,6,0,6,5,6,0,6,6,4,11,6,0,0,0,16,6,

%T 8,10,12,0,4,13,12,0,12,0,6,7,8,0,12,0,10,16,6,0,6,26,12,19,26,0,30,0,

%U 4,12,32,24,24,0,6,23,28,0,18,0,10,12,8,24,12,0,24,0,8,0,24,8,4,6,12,0,30

%N Least k such that phi(n) = phi(k) + phi(n-k) for 0<k<n, or 0 if there is no such k, where phi is Euler's totient function.

%C Sequence A110174 gives the number of solutions 0<k<n. Note that a(n)=0 for all primes except 3. It is also zero for the composite numbers in A110175.

%H Antti Karttunen, <a href="/A110173/b110173.txt">Table of n, a(n) for n = 1..16384</a>

%H Antti Karttunen, <a href="/A110173/a110173.txt">Data supplement: n, a(n) computed for n = 1..65537</a>

%t a[n_] := Select[Range[n-1], EulerPhi[n]==EulerPhi[n-# ]+EulerPhi[ # ]&]; Table[s=a[n]; If[Length[s]==0, 0, First[s]], {n, 150}]

%o (PARI) A110173(n) = { my(ph=eulerphi(n)); for(k=1,n-1,if(ph == (eulerphi(k)+eulerphi(n-k)), return(k))); (0); }; \\ _Antti Karttunen_, Feb 20 2023

%Y Cf. A066426 (least k such that phi(n)+phi(k)=phi(n+k)), A110174.

%Y Cf. also A110176.

%K nonn

%O 1,4

%A _T. D. Noe_, Jul 15 2005