login
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.
2

%I #28 Jun 26 2021 22:20:17

%S 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 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 47,7,6,67,12,34,21,71,10,36,20,40,75,14,14,29,15,20,42

%N 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 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 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 If n mod p = i and n mod q = j, (n-j) mod p = i-j and (n-j) mod q = 0.

%C 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 Property: k(p1, p2) < p2.

%C Definition: a(n) = k(p1, p2), where p1*p2 = A046388(n), and p1, p2 are primes.

%C 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 Lei Zhou, <a href="/A220291/b220291.txt">Table of n, a(n) for n = 1..10000</a>

%e n=1, A046388(1)=15=3*5, 3*3+1 = 10, 10 is divisible by 5, so a(1)=3;

%e n=2, A046388(1)=21=3*7, 3*2+1 = 7, 7 is divisible by 7, so a(1)=3;

%e ...

%e n=990, A046388(990)=5063=61*83, 61*34+1 = 2075, 2075 = 83*25 is divisible by 7, so a(990)=34.

%t 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 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 Cf. A046388.

%K nonn,easy

%O 1,1

%A _Lei Zhou_, Dec 11 2012