A283715 a(n) is the number of Carmichael numbers whose largest prime factor is prime(n).

0, 0, 0, 0, 0, 0, 2, 1, 0, 1, 2, 2, 2, 0, 0, 0, 0, 6, 3, 1, 9, 2, 0, 3, 9, 7, 3, 1, 16, 20, 42, 19, 12, 15, 3, 60, 54, 57, 2, 8, 2, 277, 20, 170, 75, 259, 775, 57, 11, 110

Offset: 1

Author

Giovanni Resta, Mar 15 2017

Keywords

• nonn
• more

Comments

Since Carmichael numbers are squarefree, there is only a finite number of them whose largest prime factor is any given prime.

Examples

			a(28) = 1 because prime(28) = 107 and there is only one Carmichael number whose largest prime factor is 107, namely 413631505 = 5 * 7 * 17 * 73 * 89 * 107.
		

Links

• Giovanni Resta, Carmichael numbers with largest prime factor <= 179, sorted by their largest prime factor

Crossrefs

Cf. A002997, A081702, A280617.

Programs

Mathematica

a[n_] := a[n] = If[n < 6, 0, Block[{t, p = Prime@ n}, Length@ Select[ Subsets[ Prime@ Range[2, n-1], {2, n-2}], (t = Times @@ #; Mod[t-1, p-1] == 0 && And @@ IntegerQ /@ ((p t - 1)/ (#-1))) &]]]; Array[a, 22]

Python

from math import prod
from itertools import combinations
from sympy import prime, primerange
def A283715(n):
    plist, c = list(primerange(3,p:=prime(n))), 0
    for l in range(2,len(plist)+1):
        for q in combinations(plist,l):
            k = prod(q)*p-1
            if not (k%(p-1) or any(k%(r-1) for r in q)):
                c+=1
    return c # Chai Wah Wu, Sep 25 2024

Extensions

a(42)-a(50) from Ondrej Kutal, Sep 29 2024