OFFSET
1,1
COMMENTS
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.
LINKS
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.
EXAMPLE
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).
PROG
(Python)
# 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]
CROSSREFS
KEYWORD
nonn
AUTHOR
Barry Fagin, Sep 09 2019
STATUS
approved