cp's OEIS Frontend

A280617 Number of n-smooth Carmichael numbers.

%I A280617 #53 Sep 30 2024 16:55:46
%S A280617 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,3,3,3,3,3,3,3,3,3,3,4,4,6,6,6,6,
%T A280617 6,6,8,8,8,8,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
%U A280617 10,16,16,16,16,16,16,19,19,19,19,20,20,29,29,29,29,29,29,31,31,31,31,31,31,31,31
%N A280617 Number of n-smooth Carmichael numbers.
%C A280617 A number is b-smooth whenever its prime factors are all not greater than b.
%C A280617 By Korselt's criterion, every Carmichael number is squarefree, therefore n-smooth numbers are products of subsets of primes below n.
%H A280617 Ondrej Kutal, <a href="/A280617/b280617.txt">Table of n, a(n) for n = 1..180</a>
%H A280617 Wikipedia, <a href="https://en.wikipedia.org/wiki/Carmichael_number">Carmichael number</a>
%H A280617 Wikipedia, <a href="https://en.wikipedia.org/wiki/Carmichael_number#Korselt.27s_criterion">Korselt's criterion</a>
%H A280617 Wikipedia, <a href="https://en.wikipedia.org/wiki/Smooth_number">Smooth number</a>
%F A280617 a(n) = Sum_{k=1..primepi(n)} A283715(k). - _Ondrej Kutal_, Sep 27 2024
%e A280617 For n = 19, the n-smooth Carmichael numbers are
%e A280617   571 = 3*11*17
%e A280617   1105 = 5*13*17
%e A280617   1729 = 7*13*19
%e A280617 There are no other Carmichael numbers that are 19-smooth, therefore a(19)=3.
%p A280617 extend:= proc(c,p)
%p A280617      if andmap(q -> (p-1 mod q <> 0), c) then (c, c union {p}) else c fi
%p A280617 end proc:
%p A280617 carm:= proc(c) local n;
%p A280617   n:= convert(c,`*`);
%p A280617   map(t -> n-1 mod (t-1), c) = {0}
%p A280617 end proc:
%p A280617 A[1]:= 0: A[2]:= 0: Primes:= []:
%p A280617 for k from 3 to 100 do
%p A280617   A[k]:= A[k-1];
%p A280617   if isprime(k) then
%p A280617     Cands:= {{}};
%p A280617     for i from 1 to nops(Primes) do
%p A280617       if (k - 1) mod Primes[i] <> 0 then
%p A280617         Cands:= map(extend,Cands,Primes[i])
%p A280617       fi;
%p A280617     od;
%p A280617     Cands:= map(`union`,select(c -> nops(c) > 1, Cands),{k});
%p A280617     A[k]:= A[k] + nops(select(carm,Cands));
%p A280617     Primes:= [op(Primes),k];
%p A280617   fi
%p A280617 od:
%p A280617 seq(A[i],i=1..100); # _Robert Israel_, Mar 14 2017
%t A280617 a[n_] := a[n] = If[n<17, 0, a[n-1] + If[! PrimeQ[n], 0, Block[{t, k = PrimePi@n, p}, p = Prime@k; Length@ Select[ Subsets[ Prime@ Range[2, k-1], {2, k-2}], (t = Times @@ #; Mod[t-1, p-1] == 0 && And @@ IntegerQ /@ ((p t - 1)/ (#-1))) &]]]]; Array[a, 80] (* _Giovanni Resta_, Mar 14 2017 *)
%o A280617 (Python)
%o A280617 from collections import Counter
%o A280617 from functools import reduce
%o A280617 from itertools import combinations, chain
%o A280617 from operator import mul
%o A280617 # http://www.sympy.org
%o A280617 import sympy as sp
%o A280617 limit = 90
%o A280617 # credit: http://stackoverflow.com/a/16915734
%o A280617 # as proved, there are no Carmichael numbers with
%o A280617 # less than 3 prime factors, and thus modification
%o A280617 def powerset(iterable):
%o A280617     xs = list(iterable)
%o A280617     return chain.from_iterable(combinations(xs, n) for n in range(3, len(xs) + 1))
%o A280617 # all computed numbers will be limit-smooth
%o A280617 def carmichael(limit):
%o A280617     for d in powerset(sp.primerange(3, limit)):
%o A280617         n = reduce(mul, d, 1)
%o A280617         broke = False
%o A280617         for p in d:
%o A280617             if (n - 1) % (p - 1) != 0:
%o A280617                 broke = True
%o A280617                 break
%o A280617         if not broke:
%o A280617             yield (d[-1])
%o A280617 # from list of pairs of (n, number_of_integers_with_n_as_greatest_prime_factor)
%o A280617 # creates the sequence
%o A280617 def prefix(lst):
%o A280617     r = []
%o A280617     s = 0
%o A280617     rpointer = 0
%o A280617     lstpointer = 0
%o A280617     while lstpointer < len(lst):
%o A280617         while lst[lstpointer][0] > rpointer:
%o A280617             r.append(s)
%o A280617             rpointer += 1
%o A280617         s += lst[lstpointer][1]
%o A280617         lstpointer += 1
%o A280617     r.append(s + lst[-1][1])
%o A280617     return r
%o A280617 c = Counter(carmichael(limit))
%o A280617 for i, e in enumerate(prefix(sorted(c.items()))):
%o A280617     if i > 0:
%o A280617         print(e, end=", ")
%o A280617 (Python)
%o A280617 from math import prod
%o A280617 from itertools import combinations
%o A280617 from sympy import primerange
%o A280617 def A280617(n):
%o A280617     plist, c = list(primerange(3,n+1)), 0
%o A280617     for l in range(2,len(plist)+1):
%o A280617         for q in combinations(plist,l):
%o A280617             k = prod(q)-1
%o A280617             if not any(k%(r-1) for r in q):
%o A280617                 c+=1
%o A280617     return c # _Chai Wah Wu_, Sep 25 2024
%Y A280617 Cf. A002997, A081702, A283715.
%K A280617 nonn
%O A280617 1,17
%A A280617 _Michal Radwanski_, Jan 06 2017