cp's OEIS Frontend

A178313 Absolute difference between prime factors of n-th semiprime mod n.

%I A178313 #26 Apr 22 2025 04:00:03
%S A178313 0,1,0,3,0,2,4,1,0,1,8,3,2,3,10,5,0,14,6,16,6,7,8,20,10,4,12,12,12,26,
%T A178313 6,28,12,14,16,34,18,19,10,0,18,38,40,12,20,44,22,2,24,21,26,25,50,16,
%U A178313 26,0,56,29,58,32,6,33,1,35,22,36,34,8,68,35,38,24,34,70,4,35,42,76,6,0
%N A178313 Absolute difference between prime factors of n-th semiprime mod n.
%H A178313 Alois P. Heinz, <a href="/A178313/b178313.txt">Table of n, a(n) for n = 1..20000</a>
%e A178313 a(2)=1 because semiprime(2) = 6 = 3*2 and (3-2) mod 2 = 1.
%t A178313 semiPrimeQ[n_] := Plus @@ Last /@ FactorInteger@ n == 2; f[n_] := Subtract @@ Reverse@ Flatten[ Table[ #[[1]], {#[[2]]}] & /@ FactorInteger@ n]; t = Select[ Range@ 215, semiPrimeQ]; Table[ Mod[ f[ t[[n]]], n], {n, 80}]
%t A178313 f[{a_,b_}]:=Module[{c=FactorInteger[b][[;;,1]]},If[Length[c]==1,0,Mod[Differences[c][[1]],a]]]; Module[{nn=300,spr},spr=Select[Range[nn],PrimeOmega[#]==2&];f/@Thread[{Range[ Length[ spr]],spr}]] (* _Harvey P. Dale_, May 29 2024 *)
%o A178313 (Python)
%o A178313 from math import isqrt
%o A178313 from sympy import primepi, primerange, primefactors
%o A178313 from sympy.ntheory.primetest import is_square
%o A178313 def A178313(n):
%o A178313     def bisection(f,kmin=0,kmax=1):
%o A178313         while f(kmax) > kmax: kmax <<= 1
%o A178313         kmin = kmax >> 1
%o A178313         while kmax-kmin > 1:
%o A178313             kmid = kmax+kmin>>1
%o A178313             if f(kmid) <= kmid:
%o A178313                 kmax = kmid
%o A178313             else:
%o A178313                 kmin = kmid
%o A178313         return kmax
%o A178313     def f(x): return int(n+x+((t:=primepi(s:=isqrt(x)))*(t-1)>>1)-sum(primepi(x//p) for p in primerange(s+1)))
%o A178313     return 0 if is_square(m:=bisection(f,n,n)) else ((p:=primefactors(m))[1]-p[0])%n # _Chai Wah Wu_, Apr 03 2025
%Y A178313 Cf. A001358, A178102, A109313.
%K A178313 nonn
%O A178313 1,4
%A A178313 _Juri-Stepan Gerasimov_, Dec 20 2010