cp's OEIS Frontend

A306812 Maximally idempotent integers with three or more factors.

%I A306812 #31 Jul 09 2019 03:11:52
%S A306812 273,455,1729,2109,2255,2387,3367,3515,4433,4697,4921,5673,6643,6935,
%T A306812 7667,8103,8723,8729,9139,9455,10235,10787,11543,13237,13505,14497,
%U A306812 16211,16385,16523,17507,18031,18907,20033,20801,21437,22649,23579,24583
%N A306812 Maximally idempotent integers with three or more factors.
%C A306812 An integer n has an idempotent factorization n=pq if b^(k(p-1)(q-1)+1) is congruent to b mod n for any integer k >= 0 and any b in Z_n (see A306330).  An integer is maximally idempotent if all its bipartite factorizations n=pq are idempotent.
%C A306812 There are 15506 maximally idempotent integers less than 2^30.  15189 have three factors, 315 have four, two have five.  The smallest maximally idempotent integer with four factors is 63973=7*13*19*37, a Carmichael number.  The two with five factors are 13*19*37*73*109 and 11*31*41*101*151.  The smallest maximally idempotent integer with six factors is 11*31*41*61*101*151.
%H A306812 Barry Fagin, <a href="/A306812/b306812.txt">Table of n < 2^30</a>
%H A306812 Barry Fagin, <a href="/A306812/a306812.txt">Table of n < 2^30 with factorizations</a>
%H A306812 Barry Fagin, <a href="https://doi.org/10.3390/info10070232">Idempotent Factorizations of Square-Free Integers</a>, Information 2019, 10(7), 232.
%e A306812 273 is the smallest maximally idempotent integer.  Factorization is (3,7,13).  Bipartite factorizations are (3,91), (7,39), (13,21).  Lambda(273) = 12, (2*90),(6*38) and (12*20) are all divisible by 12, thus 273 is maximally idempotent.  The same is true for 455 = 5*7*13.  The next entry in the sequence, 1729=7*13*19, is a Carmichael number, but most Carmichael numbers are not maximally idempotent.
%o A306812 (Python)
%o A306812 ## This uses a custom library of number theory functions and the numbthy library.
%o A306812 ## Hopefully the names of the functions make the process clear.
%o A306812 for n in range(2,max_n):
%o A306812     factor_list = numbthy.factor(n)
%o A306812     numFactors = len(factor_list)
%o A306812     if numFactors <= 2: # skip primes and semiprimes
%o A306812         continue
%o A306812     if not bsflib.is_composite_and_square_free_with_list(n,factor_list):
%o A306812         continue
%o A306812     ipList = bsflib.idempotentPartitions(n, factor_list)
%o A306812     if len(ipList) == 2**(numFactors-1)-1:
%o A306812         print(n)
%Y A306812 Cf. A115957, A138636, A002322, A306508.
%Y A306812 Subsequence of A120944 (composite squarefree numbers).  Subsequence of A306330 (squarefree numbers that admit idempotent factorizations).  Members of the sequence with >= 4 factors for a subsequence of A306508 (squarefree integers with fully composite idempotent factorizations).
%K A306812 nonn
%O A306812 1,1
%A A306812 _Barry Fagin_, Mar 11 2019