A373274 - OEIS

%I #23 Jun 22 2024 14:09:30

%S 65,66,91,154,217,369,370,451,481,561,630,703,783,793,1065,1106,1353,

%T 1407,1463,1729,1854,1891,1921,2002,2059,2146,2201,2415,2501,2701,

%U 3451,3550,3870,4033,4081,4097,4225,4625,4642,4681,4699,4921,5215,5457,5626,5830,5833,5929,5985

%N Sigma-phi numbers: composite numbers k such that k-1 is a multiple of Sum_{prime^h|k} phi(prime^h), where h is the maximum integer such that prime^h|k and phi = A000010.

%H Robert C. Vaughan and Kevin L. Weis, <a href="https://doi.org/10.1112/S002557930001442X">On sigma-phi numbers</a>, Mathematika 48 (2001), 169-189.

%e For k = 3550 = 2 * 5^2 * 71, k-1 = 3549 is divisible by phi(2) + phi(5^2) + phi(71) = (2-1) + (5^2-5) + (71-1) = 91.

%p with(numtheory):

%p f := proc(n)

%p     nops(numtheory[factorset](n))

%p end proc:

%p sum_phi := proc(n)

%p     local prime_divisors, sum:

%p       prime_divisors := ifactors(n)[2]:

%p     if f(n) >= 2 then

%p         sum := add(prime_divisors[i][1]^prime_divisors[i][2] - prime_divisors[i][1]^(prime_divisors[i][2]-1), i = 1 .. nops(prime_divisors)):

%p     else

%p         sum := 0:

%p     end if:

%p     sum:

%p end proc:

%p valid_n := proc(n)

%p     local sum_val:

%p     sum_val := sum_phi(n):

%p     if sum_val <> 0 and (n-1) mod sum_val = 0 then

%p         return true:

%p     else

%p         return false:

%p     end if:

%p end proc:

%p result := select(valid_n, [$2 .. 5000]);

%t f[p_, e_] := (p-1) * p^(e-1); Select[Range[6000], CompositeQ[#] && Divisible[# - 1,Plus @@ f @@@ FactorInteger[#]] &] (* _Amiram Eldar_, May 29 2024 *)

%o (PARI) isok(k) = if (k>1 && !isprime(k), my(f=factor(k)); (k-1) % sum(i=1, #f~, eulerphi(f[i,1]^f[i,2])) == 0;) \\ _Michel Marcus_, May 29 2024

%Y Cf. A000010 (Euler totient function phi).

%K nonn

%O 1,1

%A _Rafik Khalfi_, May 29 2024