OFFSET
1,1
COMMENTS
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.
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.
LINKS
Barry Fagin, Table of n < 2^30
Barry Fagin, Table of n < 2^30 with factorizations
Barry Fagin, Idempotent Factorizations of Square-Free Integers, Information 2019, 10(7), 232.
EXAMPLE
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.
PROG
(Python)
## This uses a custom library of number theory functions and the numbthy library.
## Hopefully the names of the functions make the process clear.
for n in range(2, max_n):
factor_list = numbthy.factor(n)
numFactors = len(factor_list)
if numFactors <= 2: # skip primes and semiprimes
continue
if not bsflib.is_composite_and_square_free_with_list(n, factor_list):
continue
ipList = bsflib.idempotentPartitions(n, factor_list)
if len(ipList) == 2**(numFactors-1)-1:
print(n)
CROSSREFS
KEYWORD
nonn
AUTHOR
Barry Fagin, Mar 11 2019
STATUS
approved