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

Author

Lei Zhou, Dec 11 2012

Keywords

• nonn
• easy

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.

Examples

			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.
		

Links

• Lei Zhou, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A046388.

Programs

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 *)