A306508 Squarefree numbers that have fully composite idempotent factorizations.

210, 462, 570, 1155, 1302, 1330, 1365, 1785, 2210, 2310, 2730, 3003, 3410, 3710, 3990, 4305, 4515, 4758, 4810, 5005, 5187, 5474, 5610, 5642, 6006, 6105, 6118, 6270, 6510, 6622, 6630, 7410, 7770, 8265, 8385, 8463, 8645, 9282, 9471, 9870, 10010, 10101, 10230, 10374, 10545, 10582

Offset: 1

Author

Barry Fagin, Feb 20 2019

Keywords

• nonn

Comments

Fully composite idempotent factorizations are bipartite factorizations n=p*q such that p and q are composite numbers with the property that for any b in Z_n, b^(k(p-1)(q-1)+1) is congruent to b mod n for any integer k >= 0. Idempotent factorizations have the property that p and q generate correctly functioning RSA keys, even if one or both are composite.

2730 has more than one fully composite idempotent factorization (10*273, 21*130). It is the smallest positive integer with that property. 7770 and 8463 are similar.

Examples

			210=10*21, 462=22*21, 570=10*57, 1155=21*55, 1302=6*217, 1330=10*133, 1365=15*91 and 1785=21*85 are the fully composite idempotent factorizations for the first eight terms.
		

Links

• Barry Fagin, Table of n, a(n) for n = 1..63737
• Barry Fagin, All n < 2^27 and their fully composite idempotent factorizations
• Barry Fagin, Idempotent Factorizations of Square-Free Integers, Information 2019, 10(7), 232.
• Barry Fagin, Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers, Information (2021) Vol. 12, No. 8, 305.

Crossrefs

Cf. A115957, A138636, A002322.

Subsequence of A120944 (composite squarefree numbers).

Subsequence of A306330 (composite squarefree numbers with idempotent factorizations).

Programs

PARI

isokc(p, q, n) = (p != 1) && !isprime(p) && !isprime(q) && (frac((p-1)*(q-1)/lcm(znstar(n)[2])) == 0);
isok(n) = {if (issquarefree(n) && omega(n) >= 3, my(d = divisors(n)); for (k=1, #d\2, if (isokc(d[k], n/d[k], n), return (1););););} \\ Michel Marcus, Feb 22 2019

Python

for n in range(2,max_n):
    factor_list = numbthy.factor(n)
    numFactors = len(factor_list)
    if numFactors <= 3:
        continue
    if not bsflib.is_composite_and_square_free_with_list(n,factor_list):
        continue
    fciFactorizations = bsflib.fullyCompositeIdempotentFactorizations(n,factor_list)
    numFCIFs = len(fciFactorizations)
    if numFCIPs > 0:
        fcIdempotents += 1
    print(n)