A306812 Maximally idempotent integers with three or more factors.

273, 455, 1729, 2109, 2255, 2387, 3367, 3515, 4433, 4697, 4921, 5673, 6643, 6935, 7667, 8103, 8723, 8729, 9139, 9455, 10235, 10787, 11543, 13237, 13505, 14497, 16211, 16385, 16523, 17507, 18031, 18907, 20033, 20801, 21437, 22649, 23579, 24583

Offset: 1

Author

Barry Fagin, Mar 11 2019

Keywords

• nonn

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.

Examples

			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.
		

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.

Crossrefs

Cf. A115957, A138636, A002322, A306508.

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).

Programs

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)