1,1

Suppose that (s(i)) is a strictly increasing sequence in the set N of positive integers. For i in N, let r(h) be the residue of s(i+h)-s(i) mod n, for h=1,2,...,n+1. There are at most n distinct residues r(h), so that there must exist numbers h and h' such that r(h)=r(h'), where 0<=h<h'<=n. Then s(i+h) is congruent mod n to s(i+h'), so that there exist j and k in N such that j<k and n divides s(k)-s(j). Let k(n) be the least k for which such j exists, and let j(n)=j. The pair (k,j) will be called the "least pair for which n divides s(k)-s(j)." (However, starting with "least j for which there is a k" yields pairs (k,j) which differ from those already described.)

Corollary: for each n, there are infinitely many pairs (j,k) such that n divides s(k)-s(j), and this result holds if s is assumed unbounded, rather than strictly increasing.

Guide to related sequences:

...

s(n)=prime(n), primes

... k(n), j(n): A204892, A204893

... s(k(n)),s(j(n)): A204894, A204895

... s(k(n))-s(j(n)): A204896, A204897

s(n)=prime(n+1), odd primes

... k(n), j(n): A204900, A204901

... s(k(n)),s(j(n)): A204902, A204903

... s(k(n))-s(j(n)): A109043(?), A000034(?)

s(n)=prime(n+2), primes >=5

... k(n), j(n): A204908, A204909

... s(k(n)),s(j(n)): A204910, A204911

... s(k(n))-s(j(n)): A109043(?), A000034(?)

s(n)=prime(n)*prime(n+1) product of consecutive primes

... k(n), j(n): A205146, A205147

... s(k(n)),s(j(n)): A205148, A205149

... s(k(n))-s(j(n)): A205150, A205151

s(n)=(prime(n+1)+prime(n+2))/2: averages of odd primes

... k(n), j(n): A205153, A205154

... s(k(n)),s(j(n)): A205372, A205373

... s(k(n))-s(j(n)): A205374, A205375

s(n)=2^(n-1), powers of 2

... k(n), j(n): A204979, A001511(?)

... s(k(n)),s(j(n)): A204981, A006519(?)

... s(k(n))-s(j(n)): A204983(?), A204984

s(n)=2^n, powers of 2

... k(n), j(n): A204987, A204988

... s(k(n)),s(j(n)): A204989, A140670(?)

... s(k(n))-s(j(n)): A204991, A204992

s(n)=C(n+1,2), triangular numbers

... k(n), j(n): A205002, A205003

... s(k(n)),s(j(n)): A205004, A205005

... s(k(n))-s(j(n)): A205006, A205007

s(n)=n^2, squares

... k(n), j(n): A204905, A204995

... s(k(n)),s(j(n)): A204996, A204997

... s(k(n))-s(j(n)): A204998, A204999

s(n)=(2n-1)^2, odd squares

... k(n), j(n): A205378, A205379

... s(k(n)),s(j(n)): A205380, A205381

... s(k(n))-s(j(n)): A205382, A205383

s(n)=n(3n-1), pentagonal numbers

... k(n), j(n): A205138, A205139

... s(k(n)),s(j(n)): A205140, A205141

... s(k(n))-s(j(n)): A205142, A205143

s(n)=n(2n-1), hexagonal numbers

... k(n), j(n): A205130, A205131

... s(k(n)),s(j(n)): A205132, A205133

... s(k(n))-s(j(n)): A205134, A205135

s(n)=C(2n-2,n-1), central binomial coefficients

... k(n), j(n): A205010, A205011

... s(k(n)),s(j(n)): A205012, A205013

... s(k(n))-s(j(n)): A205014, A205015

s(n)=(1/2)C(2n,n), (1/2)*(central binomial coefficients)

... k(n), j(n): A205386, A205387

... s(k(n)),s(j(n)): A205388, A205389

... s(k(n))-s(j(n)): A205390, A205391

s(n)=n(n+1), oblong numbers

... k(n), j(n): A205018, A205028

... s(k(n)),s(j(n)): A205029, A205030

... s(k(n))-s(j(n)): A205031, A205032

s(n)=n!, factorials

... k(n), j(n): A204932, A204933

... s(k(n)),s(j(n)): A204934, A204935

... s(k(n))-s(j(n)): A204936, A204937

s(n)=n!!, double factorials

... k(n), j(n): A204982, A205100

... s(k(n)),s(j(n)): A205101, A205102

... s(k(n))-s(j(n)): A205103, A205104

s(n)=3^n-2^n

... k(n), j(n): A205000, A205107

... s(k(n)),s(j(n)): A205108, A205109

... s(k(n))-s(j(n)): A205110, A205111

s(n)=Fibonacci(n+1)

... k(n), j(n): A204924, A204925

... s(k(n)),s(j(n)): A204926, A204927

... s(k(n))-s(j(n)): A204928, A204929

s(n)=Fibonacci(2n-1)

... k(n), j(n): A205442, A205443

... s(k(n)),s(j(n)): A205444, A205445

... s(k(n))-s(j(n)): A205446, A205447

s(n)=Fibonacci(2n)

... k(n), j(n): A205450, A205451

... s(k(n)),s(j(n)): A205452, A205453

... s(k(n))-s(j(n)): A205454, A205455

s(n)=Lucas(n)

... k(n), j(n): A205114, A205115

... s(k(n)),s(j(n)): A205116, A205117

... s(k(n))-s(j(n)): A205118, A205119

s(n)=n*(2^(n-1))

... k(n), j(n): A205122, A205123

... s(k(n)),s(j(n)): A205124, A205125

... s(k(n))-s(j(n)): A205126, A205127

s(n)=ceiling[n^2/2]

... k(n), j(n): A205394, A205395

... s(k(n)),s(j(n)): A205396, A205397

... s(k(n))-s(j(n)): A205398, A205399

s(n)=floor[(n+1)^2/2]

... k(n), j(n): A205402, A205403

... s(k(n)),s(j(n)): A205404, A205405

... s(k(n))-s(j(n)): A205406, A205407

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Let s(k)=prime(k). As in A204890, the ordering of differences s(k)-s(j), follows from the arrangement shown here:

k...........1..2..3..4..5...6...7...8...9

s(k)........2..3..5..7..11..13..17..19..23

...

s(k)-s(1)......1..3..5..9..11..15..17..21..27

s(k)-s(2).........2..4..8..10..14..16..20..26

s(k)-s(3)............2..6..8...12..14..18..24

s(k)-s(4)...............4..6...10..12..16..22

...

least (k,j) such that 1 divides s(k)-s(j) for some j is (2,1), so a(1)=2.

least (k,j) such that 2 divides s(k)-s(j): (3,2), so a(2)=3.

least (k,j) such that 3 divides s(k)-s(j): (3,1), so a(3)=3.

s[n_] := s[n] = Prime[n]; z1 = 400; z2 = 50;

Table[s[n], {n, 1, 30}] (* A000040 *)

u[m_] := u[m] = Flatten[Table[s[k] - s[j],

{k, 2, z1}, {j, 1, k - 1}]][[m]]

Table[u[m], {m, 1, z1}] (* A204890 *)

v[n_, h_] := v[n, h] = If[IntegerQ[u[h]/n], h, 0]

w[n_] := w[n] = Table[v[n, h], {h, 1, z1}]

d[n_] := d[n] = First[Delete[w[n],

Position[w[n], 0]]]

Table[d[n], {n, 1, z2}] (* A204891 *)

k[n_] := k[n] = Floor[(3 + Sqrt[8 d[n] - 1])/2]

m[n_] := m[n] = Floor[(-1 + Sqrt[8 n - 7])/2]

j[n_] := j[n] = d[n] - m[d[n]] (m[d[n]] + 1)/2

Table[k[n], {n, 1, z2}] (* A204892 *)

Table[j[n], {n, 1, z2}] (* A204893 *)

Table[s[k[n]], {n, 1, z2}] (* A204894 *)

Table[s[j[n]], {n, 1, z2}] (* A204895 *)

Table[s[k[n]] - s[j[n]], {n, 1, z2}] (* A204896 *)

Table[(s[k[n]] - s[j[n]])/n, {n, 1, z2}] (* A204897 *)

(* Program 2: generates A204892 and A204893 rapidly *)

s = Array[Prime[#] &, 120];

lk = Table[NestWhile[# + 1 &, 1, Min[Table[Mod[s[[#]] - s[[j]], z], {j, 1, # - 1}]] =!= 0 &], {z, 1, Length[s]}]

Table[NestWhile[# + 1 &, 1, Mod[s[[lk[[j]]]] - s[[#]], j] =!= 0 &], {j, 1, Length[lk]}]

(* Peter J. C. Moses, Jan 27 2012 *)

(PARI) a(n)=forprime(p=n+2, , forstep(k=p%n, p-1, n, if(isprime(k), return(primepi(p))))) \\ Charles R Greathouse IV, Mar 20 2013

Cf. A000040, A204890.

Sequence in context: A029086 A070046 A130120 * A164512 A127434 A266475

Adjacent sequences: A204889 A204890 A204891 * A204893 A204894 A204895

Clark Kimberling, Jan 20 2012

approved