|
%I #31 Jul 09 2019 03:11:52
%S 273,455,1729,2109,2255,2387,3367,3515,4433,4697,4921,5673,6643,6935,
%T 7667,8103,8723,8729,9139,9455,10235,10787,11543,13237,13505,14497,
%U 16211,16385,16523,17507,18031,18907,20033,20801,21437,22649,23579,24583
%N Maximally idempotent integers with three or more factors.
%C 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 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 Barry Fagin, <a href="/A306812/b306812.txt">Table of n < 2^30</a>
%H Barry Fagin, <a href="/A306812/a306812.txt">Table of n < 2^30 with factorizations</a>
%H Barry Fagin, <a href="https://doi.org/10.3390/info10070232">Idempotent Factorizations of Square-Free Integers</a>, Information 2019, 10(7), 232.
%e 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 (Python)
%o ## This uses a custom library of number theory functions and the numbthy library.
%o ## Hopefully the names of the functions make the process clear.
%o for n in range(2,max_n):
%o factor_list = numbthy.factor(n)
%o numFactors = len(factor_list)
%o if numFactors <= 2: # skip primes and semiprimes
%o continue
%o if not bsflib.is_composite_and_square_free_with_list(n,factor_list):
%o continue
%o ipList = bsflib.idempotentPartitions(n, factor_list)
%o if len(ipList) == 2**(numFactors-1)-1:
%o print(n)
%Y Cf. A115957, A138636, A002322, A306508.
%Y 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 nonn
%O 1,1
%A _Barry Fagin_, Mar 11 2019
|
