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

Author

Barry Fagin, Sep 09 2019

Keywords

• nonn

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.

Examples

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

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.

Crossrefs

Cf. A306330, A120944.

Programs

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]