Barry Fagin - cp's OEIS frontend

A325945 Let p(n) be the n-th composite squarefree number. a(n) is the smallest integer q that forms a pure idempotent product.

217, 21, 265, 91, 10, 217, 217, 4537, 91, 65, 703, 9685, 703, 7885, 133, 217, 21, 10, 645, 49561, 34, 217, 1387, 141, 19045, 1891, 145, 481, 21, 3193, 1891, 15, 91, 231, 91, 182449, 106, 105, 101401, 55, 103285, 133, 2553, 9217, 3781, 2701, 85, 21, 10, 9637, 420553, 70

Offset: 1

Barry Fagin, Sep 09 2019

nonn

Idempotent products are defined in A306330 and the references below.  A pure idempotent product is formed from p and q that are coprime, squarefree, non-Carmichael numbers.
If we allow p to be prime while keeping q composite, values of q that form pure idempotent products are easily determined.  For p=2, there is no solution. For p=3, the smallest qualifying q is 91.  For all primes >= 5, the smallest q is 6.
We conjecture that for all positive composite squarefree integers p, there exists a q such that pq is a pure idempotent product.  Conjecture verified for all squarefree composite p < 2^15.  The largest q correspond to the cases where p-1 is prime.

			6 is the first composite squarefree number, a(1) = 217, 217 is the smallest q such that 6q is a pure idempotent product (1302).
10 is the second composite squarefree number, a(2) = 21, 21 is the smallest q such that 10q is a pure idempotent product (210).
14 is the second composite squarefree number, a(3) = 265, 265 is the smallest q such that 14q is a pure idempotent product (3710).

Barry Fagin, Table of n, a(n) for n = 1..16361
Barry Fagin, Idempotent Factorizations of Square-Free Integers, Information 2019, 10(7), 232.
Barry Fagin, Idempotent Factorizations: A New Addition to the Cryptography Classroom. In Proceedings of the 2019 ACM Conference on Innovation and Technology in Computer Science Education (ITiCSE '19). Aberdeen, Scotland UK — July 15-17, 2019 page 303.

Cf. A306330, A120944.

# returns [q,k,D,cFlag]
# q is smallest non-Carmichael composite q that forms an idempotent
# factorization with p_bar
# q=k*DP+1
# # D is DP unless DP is 1 in which case D is DQ
# cFlag is False, indicates number is not Carmichael
# assumes p_bar is squarefree
# max_k limits # values checked, -1 means no limit.
# Returns [-1,-1,-1,False] if no q found before limit reached
# D_(p_bar) is lambda(p_bar)/gcd(lambda(p_bar),p_bar-1)
# uses numbthy python library
# some functions defined elsewhere, hopefully names indicate what they do
def findSmallestNonCarmichaelQbar(p_bar,min_k,max_k):
    DP = D_(p_bar)
    k = min_k
    if min_k != 0:
        k = min_k-1     # ensures min_k is tried
    Found = False
    while not Found:
        if k > max_k and max_k != -1:
            return [-1,-1,-1,False]
        k += 1
        if k % 10000000 == 0:
            print("   ",k)
        q = k*DP+1
        if not numbthy.gcd(p_bar,q) == 1:
            continue
        try:
            q_factors = numbthy.factor(q)
        except:
            print("problem factoring",q)
            prompt()
        if not is_square_free_with_list(q,q_factors):
            continue
        DQ = D_with_list(q,q_factors)
        if DQ == 1: # q is prime or Carmichael, skip it
            continue
        else:
            if p_bar % DQ == 1:
                if DP != 1:
                    return [q,k,DP,False]
                else:
                    return [q,k,DQ,False]

A307537 a(n) is the smallest maximally idempotent integer with n factors, n >= 3.

Original entry on oeis.org

273, 63973, 72719023, 13006678091, 7817013532691

Offset: 3

Barry Fagin, Apr 13 2019

Maximally idempotent integers are those squarefree integers such that all their bipartite factorizations are idempotent (see A306812). All squarefree integers with n <= 2 factors have this property, and are therefore excluded from the definition.
Entries verified computationally.
The lambda values and factorizations of the integers in this sequence are:
  M(3) = 3*7*13, lambda = 12;
  M(4) = 7*13*19*37, lambda = 36;
  M(5) = 13*19*37*73*109, lambda = 216;
  M(6) = 11*31*41*61*101*151, lambda = 600;
  M(7) = 11*31*41*61*101*151*601, lambda = 600.

			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.

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

Cf. A005117, A120944, A306330, A306508, A306812.

(* This program is not suitable to compute large terms. *)
okQ[n_] := Module[{partitions, p, q, lambda}, partitions = {p, q} /. {ToRules[Reduce[1= 3 && !IntegerQ[a[nu]], If[okQ[n], Print["a(", nu, ") = ", n]; a[nu] = n]]]]; (* Jean-François Alcover, Jun 20 2019 *)

# Partial Python code is shown below.  It uses other routines:
# numbthy.factor(n) -- from the Python number theory library, returns a list of
# (p,e) pairs corresponding to the prime factors and their exponents in the factorizations of n
# partitions(n,factor_list) -- takes an integer n and the factor list from above,
# returns a list of all bipartite factorizations of n
# lambda_n -- calculates the carmichael lambda function
# returns True if all partitions of n are idempotent
def isMaximallyIdempotent(n):
    factor_list = numbthy.factor(n)
    partitions_of_n = partitions(n,factor_list)
    lambda_n = carmichael_lambda_with_list(n,factor_list)
    for (p,q) in partitions_of_n:
        pseudo = (p-1)*(q-1)
        if pseudo % lambda_n != 0:
            return False
    return True

M(7), now confirmed as being a(7), added by Barry Fagin, Dec 04 2019

A306812 Maximally idempotent integers with three or more factors.

Original entry on oeis.org

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

Barry Fagin, Mar 11 2019

nonn

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.

			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.

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.

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

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

A306508 Squarefree numbers that have fully composite idempotent factorizations.

Original entry on oeis.org

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

Barry Fagin, Feb 20 2019

nonn

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.

			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.

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.

Cf. A115957, A138636, A002322.
Subsequence of A120944 (composite squarefree numbers).
Subsequence of A306330 (composite squarefree numbers with idempotent factorizations).

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

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)

A306330 Squarefree n with >= 3 factors that admit idempotent factorizations n = p*q.

Original entry on oeis.org

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

Offset: 1

Barry Fagin, Feb 07 2019

nonn

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)

			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.

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.

Cf. A115957, A138636, A002322.

Subsequence of A120944 (composite squarefree numbers).

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

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

A318555 "Strong impostors" not divisible by 4: Those numbers s !== 0 (mod 4) such that lambda(s) | 2(s-1), where lambda is the Carmichael function (A002322).

Original entry on oeis.org

6, 15, 66, 91, 435, 561, 703, 946, 1105, 1729, 1891, 2465, 2701, 2821, 2926, 3367, 5551, 6601, 8646, 8695, 8911, 10585, 11305, 12403, 13981, 15051, 15841, 16471, 18721, 23001, 26335, 29341, 30889, 38503, 39865, 41041, 46657, 49141, 52633, 53131, 62745, 63973, 68101, 75361, 76627, 76798, 79003, 88561, 88831, 91001

Offset: 1

Barry Fagin, Aug 28 2018

nonn

Strong impostors not == 0 (mod 4) have the property that, even though they are composite, when paired with any odd prime r such that (s,r) = 1, they produce valid RSA key pairs. More specifically, if n=sr, all a in Z_n will be correctly encrypted and decrypted for any (e,d) key pair such that ed == 1 mod (s-1)(r-1). They include the Carmichael numbers and are squarefree. The set of their odd prime factors is always normal: If p_i and p_j are odd prime factors, no p_i == 1 mod p_j.

Amiram Eldar, Table of n, a(n) for n = 1..8000 (terms 1..2773 from Barry Fagin)
D. Borwein, J. M. Borwein, P. B. Borwein and R. Girgensohn, Giuga's Conjecture on Primality, Amer. Math. Monthly 103, No. 1, 40-50 (1996).
B. S. Fagin, Composite Numbers That Give Valid RSA Key Pairs For Any Coprime p, Information, 9, 216; doi:10.3390/info9090216.
J. M. Grau and Antonio Oller-Marcén, Generalizing Giuga's conjecture, arXiv:1103.3483 [math.NT], 2011.

Cf. A002997 (Carmichael numbers), A005117 (squarefree numbers).

Subsequence of A231569.

Reap[For[s = 1, s < 10^5, s++, If[!Divisible[s, 4] && CompositeQ[s], If[ Divisible[2(s-1), CarmichaelLambda[s]], Print[s]; Sow[s]]]]][[2, 1]] (* Jean-François Alcover, Feb 18 2019 *)

isok(s) = s>1 && s%4>0 && !isprime(s) && (2*s-2)%lcm(znstar(s)[2])==0; \\ Jinyuan Wang, Mar 01 2020

cp's OEIS Frontend

User: Barry Fagin

A325945 Let p(n) be the n-th composite squarefree number. a(n) is the smallest integer q that forms a pure idempotent product.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A307537 a(n) is the smallest maximally idempotent integer with n factors, n >= 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A306812 Maximally idempotent integers with three or more factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A306508 Squarefree numbers that have fully composite idempotent factorizations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

A306330 Squarefree n with >= 3 factors that admit idempotent factorizations n = p*q.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A318555 "Strong impostors" not divisible by 4: Those numbers s !== 0 (mod 4) such that lambda(s) | 2(s-1), where lambda is the Carmichael function (A002322).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI