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,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

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

Sequence in context: A338557 A347882 A347888 * A157374 A043467 A028530

Adjacent sequences: A306809 A306810 A306811 * A306813 A306814 A306815

Keyword

nonn

Author

Barry Fagin, Mar 11 2019

Status

approved