cp's OEIS Frontend

A220291 a(n) is the smallest positive integer that makes p1*a(n)+1 divisible by p2, where p1*p2 (p1 < p2) is the n-th odd squarefree semiprime.

%I A220291 #28 Jun 26 2021 22:20:17
%S A220291 3,2,7,4,4,11,2,6,5,15,3,10,19,11,10,15,12,9,12,27,14,8,31,7,23,6,35,
%T A220291 13,39,20,22,3,22,4,8,12,47,17,22,24,13,28,26,16,55,2,21,21,59,35,32,
%U A220291 47,7,6,67,12,34,21,71,10,36,20,40,75,14,14,29,15,20,42
%N A220291 a(n) is the smallest positive integer that makes p1*a(n)+1 divisible by p2, where p1*p2 (p1 < p2) is the n-th odd squarefree semiprime.
%C A220291 The Mathematica program of this sequence provides a way towards analytically resolving the question which is a common flavor in math tournaments: Number n satisfies n mod p = j and n mod q = k. What is the minimum value of positive integer n?
%C A220291 The function k(p1,p2) is to find the minimum positive integer a such that p1*k+1 is divisible by p2 in less than log_2(p1) loops.  This function is always resolvable when p1 and p2 are coprimes.
%C A220291 If n mod p = i and n mod q = j, (n-j) mod p = i-j and (n-j) mod q = 0.
%C A220291 From the function k(p1,p2), we figure that k*p+1 mod q = 0, and k*p+1 mod p = 1. So we have, (k*p+1)*(i-j) mod p = i-j and (k*p+1)*(i-j) mod q = 0. Then, the minimum n is ((k*p+1)*(i-j)+j) mod (pq).
%C A220291 Property: k(p1, p2) < p2.
%C A220291 Definition: a(n) = k(p1, p2), where p1*p2 = A046388(n), and p1, p2 are primes.
%C A220291 Feature: k(p1,p2) will fail when used for a pair of numbers that has common factor greater than 1, and may fail when one of p1 and p2 is not prime number.  The function k(p1, p2) is always defined for prime pair p1 and p2.
%H A220291 Lei Zhou, <a href="/A220291/b220291.txt">Table of n, a(n) for n = 1..10000</a>
%e A220291 n=1, A046388(1)=15=3*5, 3*3+1 = 10, 10 is divisible by 5, so a(1)=3;
%e A220291 n=2, A046388(1)=21=3*7, 3*2+1 = 7, 7 is divisible by 7, so a(1)=3;
%e A220291 ...
%e A220291 n=990, A046388(990)=5063=61*83, 61*34+1 = 2075, 2075 = 83*25 is divisible by 7, so a(990)=34.
%t A220291 NextA046388[n_]:=Block[{p1 = Prime[Range[2, PrimePi[Max[3, NextPrime[Ceiling@Sqrt[n + 1] - 1]]]]], p2}, p2 = Table[Max[NextPrime[p1[[i]]], NextPrime[Ceiling[(n + 1)/p1[[i]]] - 1]], {i, Length[p1]}]; Min[p1*p2]]; k[p1_, p2_] := Block[{r, pb = p1, s0, s = 1, ans}, While[r = Ceiling[p2/pb]*pb - p2; If[Abs[r] > (Abs[pb]/2), If[r > 0, r = r - Abs[pb], r = r + Abs[pb]]]; s0 = (p2 + r)/pb; s = Mod[s*s0, p2]; Abs[r] != 1, pb = r]; If[r == 1, ans = Mod[s*(p2 - 1), p2], ans = Mod[s, p2]]; ans]; n = 1; Table[n = NextA046388[n]; fct = FactorInteger[n]; k[fct[[1, 1]], fct[[2, 1]]], {i, 70}] (* _Lei Zhou_, Dec 11 2012*)
%t A220291 SemiPrime2Q[n_Integer] := OddQ[n] && Transpose[FactorInteger[Abs[n]]][[2]] == {1, 1}; nn = 500; sp = Select[Range[2, nn], SemiPrime2Q]; Table[{p1, p2} = Transpose[FactorInteger[i]][[1]]; j = 1; While[Mod[p1*j + 1, p2] > 0, j++]; j, {i, sp}] (* _T. D. Noe_, Dec 11 2012 *)
%Y A220291 Cf. A046388.
%K A220291 nonn,easy
%O A220291 1,1
%A A220291 _Lei Zhou_, Dec 11 2012