login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A306330 Squarefree n with >= 3 factors that admit idempotent factorizations n = p*q. 5
30, 42, 66, 78, 102, 105, 114, 130, 138, 165, 170, 174, 182, 186, 195, 210, 222, 246, 255, 258, 266, 273, 282, 285, 290, 318, 330, 345, 354, 366, 370, 390, 399, 402, 410, 426, 434, 435, 438, 455, 462, 465, 474, 498, 510, 518, 530, 534, 546, 555, 570, 582, 602 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

An idempotent factorization of n is a way of writing n = p*q such that b^(k(p-1)(q-1)+1) is congruent to b mod n for any integer k >= 0 and any b in Z_n. For example, p = 19, q = 15 is an idempotent factorization of n = 285.  All factorizations of semiprimes are idempotent, so this sequence is restricted to n with >= 3 factors.  Idempotent factorizations have the property that p and q generate correctly functioning RSA keys, even if one or both are composite.

We show in the reference below that a bipartite factorization of a squarefree integer n = pq is idempotent if and only if lambda(pq) divides (p-1)(q-1).

(p and q are not required to be primes. - N. J. A. Sloane, Feb 08 2019)

LINKS

Barry Fagin, Table of n, a(n) for n = 1..5920 (all terms <= 2^16)

Barry Fagin, Idempotent factorizations for all n < 2^26

Barry Fagin, Idempotent Factorizations of Square-Free Integers, Information 2019, 10(7), 232.

EXAMPLE

30 = 5 * 6, 42 = 7 * 6, 66 = 11 * 6, 78 = 13 * 6, 102 = 17 * 6, 105 = 7 * 15, 114 = 19 * 6, 130 = 13 * 10 are the idempotent factorizations for the first 8 terms in the sequence. 210 = 10 * 21 is the smallest n with a fully composite idempotent factorization, one in which both p and q are composite. The number n = p * 6 is idempotent for any prime p >= 5.

PROG

(Python)

    factor_list = numbthy.factor(n)

    numFactors = len(factor_list)

    if numFactors <= 2: # skip primes and semiprimes

        continue

    if not is_composite_and_square_free_with_list(n, factor_list):

        continue

    factorCount[numFactors] += 1

    iPartitions = idempotentPartitions(n, factor_list)

    numIPs = len(iPartitions)

    if numIPs > 0:

        idempotents += 1

        print(idempotents, n)

(PARI) isok3(p, q, n) = 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 ((d[k] != 1) && isok3(d[k], n/d[k], n), return (1); ); ); ); } \\ Michel Marcus, Feb 22 2019

CROSSREFS

Cf. A115957, A138636, A002322.

Subsequence of A120944 (composite squarefree numbers).

Sequence in context: A046401 A302570 A300156 * A160352 A291446 A226104

Adjacent sequences:  A306327 A306328 A306329 * A306331 A306332 A306333

KEYWORD

nonn

AUTHOR

Barry Fagin, Feb 07 2019

EXTENSIONS

Edited by N. J. A. Sloane, Feb 08 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 16 21:46 EST 2020. Contains 331975 sequences. (Running on oeis4.)