A283715 - OEIS

%I #20 Sep 29 2024 21:10:04

%S 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,

%T 12,15,3,60,54,57,2,8,2,277,20,170,75,259,775,57,11,110

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

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

%H Giovanni Resta, <a href="/A283715/a283715.txt">Carmichael numbers with largest prime factor <= 179, sorted by their largest prime factor</a>

%e 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.

%t 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]

%o (Python)

%o from math import prod

%o from itertools import combinations

%o from sympy import prime, primerange

%o def A283715(n):

%o     plist, c = list(primerange(3,p:=prime(n))), 0

%o     for l in range(2,len(plist)+1):

%o         for q in combinations(plist,l):

%o             k = prod(q)*p-1

%o             if not (k%(p-1) or any(k%(r-1) for r in q)):

%o                 c+=1

%o     return c # _Chai Wah Wu_, Sep 25 2024

%Y Cf. A002997, A081702, A280617.

%K nonn,more

%O 1,7

%A _Giovanni Resta_, Mar 15 2017

%E a(42)-a(50) from _Ondrej Kutal_, Sep 29 2024