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.

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, 13, 39, 20, 22, 3, 22, 4, 8, 12, 47, 17, 22, 24, 13, 28, 26, 16, 55, 2, 21, 21, 59, 35, 32, 47, 7, 6, 67, 12, 34, 21, 71, 10, 36, 20, 40, 75, 14, 14, 29, 15, 20, 42

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

n=1, A046388(1)=15=3*5, 3*3+1 = 10, 10 is divisible by 5, so a(1)=3;
n=2, A046388(1)=21=3*7, 3*2+1 = 7, 7 is divisible by 7, so a(1)=3;
...
n=990, A046388(990)=5063=61*83, 61*34+1 = 2075, 2075 = 83*25 is divisible by 7, so a(990)=34.

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

Cf. A046388.

Sequence in context: A344969 A011772 A060451 * A129187 A166532 A135542

Adjacent sequences: A220288 A220289 A220290 * A220292 A220293 A220294

Keyword

nonn,easy

Author

Lei Zhou, Dec 11 2012

Status

approved