login
Composite numbers k such that phi(k) * psi(k) + 1 is a perfect square, where phi is the Euler totient function (A000010) and psi is the Dedekind psi function (A001615).
1

%I #23 Aug 14 2019 09:30:57

%S 6,8,20,22,33,69,82,156,171,190,198,295,354,451,581,664,1119,1142,

%T 1175,1184,2812,2893,4043,4163,4262,4581,5090,6964,7018,12977,14927,

%U 15026,15753,19105,22828,22926,25132,25369,28919,29746,38013,39146,47932,74666,80375

%N Composite numbers k such that phi(k) * psi(k) + 1 is a perfect square, where phi is the Euler totient function (A000010) and psi is the Dedekind psi function (A001615).

%C For all primes p, phi(p) * psi(p) + 1 = (p-1) * (p+1) + 1 = p^2 is a perfect square.

%C The squarefree terms of this sequence are common with the squarefree terms of A015709 since sigma(k) = psi(k) for squarefree numbers k.

%C If p is in A096147 then 2*p is in this sequence.

%C If p is in A078699 (prime p such that p^2 - 1 is a triangular number) then 3*p is in this sequence.

%C If p is a prime such that 2*p^2 - 2*p - 1 is also a prime then p*(2*p^2 - 2*p - 1) is in this sequence. These primes are 2, 3, 7, 13, 19, 37, 79, 103, 127, 199, 241, 307, 313, 331, 337, ...

%H Amiram Eldar, <a href="/A309653/b309653.txt">Table of n, a(n) for n = 1..500</a> (terms 1..200 from Robert Israel)

%e 8 is in the sequence since phi(8) * psi(8) + 1 = 4 * 12 + 1 = 49 = 7^2 is a perfect square.

%p filter:= proc(n)

%p local t;

%p if isprime(n) then return false fi;

%p issqr(1 + mul(t[1]^(2*t[2]-2)*(t[1]^2-1),t=ifactors(n)[2]))

%p end proc:

%p select(filter, [$2..10^5]); # _Robert Israel_, Aug 13 2019

%t f[p_, e_] := (p^e - p^(e - 1))*(p^e + p^(e - 1)); psiphi[n_] := Times @@ (f @@@ FactorInteger[n]); aQ[n_] := CompositeQ[n] && IntegerQ@Sqrt[psiphi[n] + 1]; Select[Range[1000], aQ]

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

%o isok(k) = !isprime(k) && issquare(eulerphi(k)*mypsi(k) + 1); \\ _Michel Marcus_, Aug 11 2019

%Y Cf. A000010, A001615, A015709, A078699, A096147.

%K nonn

%O 1,1

%A _Amiram Eldar_, Aug 11 2019