A373274 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.

65, 66, 91, 154, 217, 369, 370, 451, 481, 561, 630, 703, 783, 793, 1065, 1106, 1353, 1407, 1463, 1729, 1854, 1891, 1921, 2002, 2059, 2146, 2201, 2415, 2501, 2701, 3451, 3550, 3870, 4033, 4081, 4097, 4225, 4625, 4642, 4681, 4699, 4921, 5215, 5457, 5626, 5830, 5833, 5929, 5985

Offset

1,1

Links

Table of n, a(n) for n=1..49.

Robert C. Vaughan and Kevin L. Weis, On sigma-phi numbers, Mathematika 48 (2001), 169-189.

Example

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.

Maple

with(numtheory):
f := proc(n)
    nops(numtheory[factorset](n))
end proc:
sum_phi := proc(n)
    local prime_divisors, sum:
      prime_divisors := ifactors(n)[2]:
    if f(n) >= 2 then
        sum := add(prime_divisors[i][1]^prime_divisors[i][2] - prime_divisors[i][1]^(prime_divisors[i][2]-1), i = 1 .. nops(prime_divisors)):
    else
        sum := 0:
    end if:
    sum:
end proc:
valid_n := proc(n)
    local sum_val:
    sum_val := sum_phi(n):
    if sum_val <> 0 and (n-1) mod sum_val = 0 then
        return true:
    else
        return false:
    end if:
end proc:
result := select(valid_n, [$2 .. 5000]);

Mathematica

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

Prog

(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

Crossrefs

Cf. A000010 (Euler totient function phi).

Sequence in context: A043625 A296877 A044875 * A174928 A355313 A354474

Adjacent sequences: A373271 A373272 A373273 * A373275 A373276 A373277

Keyword

nonn

Author

Rafik Khalfi, May 29 2024

Status

approved