OFFSET
1,1
COMMENTS
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?
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.
If n mod p = i and n mod q = j, (n-j) mod p = i-j and (n-j) mod q = 0.
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).
Property: k(p1, p2) < p2.
Definition: a(n) = k(p1, p2), where p1*p2 = A046388(n), and p1, p2 are primes.
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.
LINKS
Lei Zhou, Table of n, a(n) for n = 1..10000
EXAMPLE
MATHEMATICA
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*)
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 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Lei Zhou, Dec 11 2012
STATUS
approved