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.

%I A325945 #26 Dec 01 2019 15:50:39
%S A325945 217,21,265,91,10,217,217,4537,91,65,703,9685,703,7885,133,217,21,10,
%T A325945 645,49561,34,217,1387,141,19045,1891,145,481,21,3193,1891,15,91,231,
%U A325945 91,182449,106,105,101401,55,103285,133,2553,9217,3781,2701,85,21,10,9637,420553,70
%N A325945 Let p(n) be the n-th composite squarefree number.  a(n) is the smallest integer q that forms a pure idempotent product.
%C A325945 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.
%C A325945 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.
%C A325945 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.
%H A325945 Barry Fagin, <a href="/A325945/b325945.txt">Table of n, a(n) for n = 1..16361</a>
%H A325945 Barry Fagin, <a href="https://doi.org/10.3390/info10070232">Idempotent Factorizations of Square-Free Integers</a>, Information 2019, 10(7), 232.
%H A325945 Barry Fagin, <a href="https://doi.org/10.1145/3304221.3325557">Idempotent Factorizations:  A New Addition to the Cryptography Classroom</a>. 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.
%e A325945 6 is the first composite squarefree number, a(1) = 217, 217 is the smallest q such that 6q is a pure idempotent product (1302).
%e A325945 10 is the second composite squarefree number, a(2) = 21, 21 is the smallest q such that 10q is a pure idempotent product (210).
%e A325945 14 is the second composite squarefree number, a(3) = 265, 265 is the smallest q such that 14q is a pure idempotent product (3710).
%o A325945 (Python)
%o A325945 # returns [q,k,D,cFlag]
%o A325945 # q is smallest non-Carmichael composite q that forms an idempotent
%o A325945 # factorization with p_bar
%o A325945 # q=k*DP+1
%o A325945 # # D is DP unless DP is 1 in which case D is DQ
%o A325945 # cFlag is False, indicates number is not Carmichael
%o A325945 # assumes p_bar is squarefree
%o A325945 # max_k limits # values checked, -1 means no limit.
%o A325945 # Returns [-1,-1,-1,False] if no q found before limit reached
%o A325945 # D_(p_bar) is lambda(p_bar)/gcd(lambda(p_bar),p_bar-1)
%o A325945 # uses numbthy python library
%o A325945 # some functions defined elsewhere, hopefully names indicate what they do
%o A325945 def findSmallestNonCarmichaelQbar(p_bar,min_k,max_k):
%o A325945     DP = D_(p_bar)
%o A325945     k = min_k
%o A325945     if min_k != 0:
%o A325945         k = min_k-1     # ensures min_k is tried
%o A325945     Found = False
%o A325945     while not Found:
%o A325945         if k > max_k and max_k != -1:
%o A325945             return [-1,-1,-1,False]
%o A325945         k += 1
%o A325945         if k % 10000000 == 0:
%o A325945             print("   ",k)
%o A325945         q = k*DP+1
%o A325945         if not numbthy.gcd(p_bar,q) == 1:
%o A325945             continue
%o A325945         try:
%o A325945             q_factors = numbthy.factor(q)
%o A325945         except:
%o A325945             print("problem factoring",q)
%o A325945             prompt()
%o A325945         if not is_square_free_with_list(q,q_factors):
%o A325945             continue
%o A325945         DQ = D_with_list(q,q_factors)
%o A325945         if DQ == 1: # q is prime or Carmichael, skip it
%o A325945             continue
%o A325945         else:
%o A325945             if p_bar % DQ == 1:
%o A325945                 if DP != 1:
%o A325945                     return [q,k,DP,False]
%o A325945                 else:
%o A325945                     return [q,k,DQ,False]
%Y A325945 Cf. A306330, A120944.
%K A325945 nonn
%O A325945 1,1
%A A325945 _Barry Fagin_, Sep 09 2019