login
Numbers k such that gcd(k, phi(k)) = gcd(k, psi(k)).
1

%I #37 Mar 21 2019 04:38:16

%S 1,2,3,4,5,7,8,9,10,11,13,14,16,17,19,20,22,23,25,26,27,28,29,31,32,

%T 34,35,37,38,40,41,42,43,44,46,47,49,50,52,53,56,58,59,61,62,64,65,67,

%U 68,70,71,73,74,76,77,78,79,80,81,82,83,84,85,86,88,89,92,94,97,98,100

%N Numbers k such that gcd(k, phi(k)) = gcd(k, psi(k)).

%C Here phi(n) is Euler's totient function A000010 and psi(n) is Dedekind's psi function A001615.

%C This sequence contains all prime powers p^k where phi(p^k) and psi(p^k) are equidistant from p^k, and gcd(p^k, phi(p^k)) = gcd(p^k, psi(p^k)) = p^(k - 1). For the prime numbers themselves this is trivial since phi(p) and psi(p) differ from p by 1 and 1^0 = 1.

%C If prime p|k, then p*k is in the sequence if and only if k is in the sequence. - _Robert Israel_, Mar 05 2019

%e 1 is a term because gcd(1, 1) = gcd(1, 1) = 1.

%e 2 is a term because gcd(2, 1) = gcd(2, 3) = 1.

%e 3 is a term because gcd(3, 2) = gcd(3, 4) = 1.

%e 4 is a term because gcd(4, 2) = gcd(4, 6) = 2.

%e 5 is a term because gcd(5, 4) = gcd(5, 6) = 1.

%e 6 is not a term because gcd(6, 2) <> gcd(6, 12).

%e 7 is a term because gcd(7, 6) = gcd(7, 8) = 1.

%p filter:= proc(n) local p,F;

%p F:= numtheory:-factorset(n);

%p igcd(n, n*mul(1-1/p, p=F)) = igcd(n, n*mul(1+1/p,p=F))

%p end proc:

%p select(filter, [$1..200]); # _Robert Israel_, Mar 05 2019

%o (PARI) dpsi(n) = n * sumdivmult(n, d, issquarefree(d)/d); \\ A001615

%o isok(k) = gcd(k, eulerphi(k)) == gcd(k, dpsi(k)); \\ _Michel Marcus_, Feb 27 2019

%Y Cf. A000010, A001615, A009195, A306695.

%K nonn

%O 1,2

%A _Torlach Rush_, Feb 21 2019