A306508 -id:A306508 - cp's OEIS frontend

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

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)

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

cp's OEIS Frontend

A306812 Maximally idempotent integers with three or more factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python