%I #27 Sep 16 2023 12:03:04
%S 2,3,3,4,4,5,7,5,5,6,6,7,10,7,7,8,8,9,13,9,9,10,16,10,16,10,10,11,11,
%T 12,19,12,20,12,12,13,22,13,13,14,14,15,24,15,15,16,25,16,26,16,16,17,
%U 29,17,30,17,17,18,18,19,31,19,32,19,19,20,33,20,20,21
%N Least k such that n divides s(k)-s(j) for some j in [1,k), where s(k)=prime(k).
%C 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.)
%C 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.
%C Guide to related sequences:
%C ...
%C s(n)=prime(n), primes
%C ... k(n), j(n): A204892, A204893
%C ... s(k(n)),s(j(n)): A204894, A204895
%C ... s(k(n))-s(j(n)): A204896, A204897
%C s(n)=prime(n+1), odd primes
%C ... k(n), j(n): A204900, A204901
%C ... s(k(n)),s(j(n)): A204902, A204903
%C ... s(k(n))-s(j(n)): A109043(?), A000034(?)
%C s(n)=prime(n+2), primes >=5
%C ... k(n), j(n): A204908, A204909
%C ... s(k(n)),s(j(n)): A204910, A204911
%C ... s(k(n))-s(j(n)): A109043(?), A000034(?)
%C s(n)=prime(n)*prime(n+1) product of consecutive primes
%C ... k(n), j(n): A205146, A205147
%C ... s(k(n)),s(j(n)): A205148, A205149
%C ... s(k(n))-s(j(n)): A205150, A205151
%C s(n)=(prime(n+1)+prime(n+2)/2: averages of odd primes
%C ... k(n), j(n): A205153, A205154
%C ... s(k(n)),s(j(n)): A205372, A205373
%C ... s(k(n))-s(j(n)): A205374, A205375
%C s(n)=2^(n-1), powers of 2
%C ... k(n), j(n): A204979, A001511(?)
%C ... s(k(n)),s(j(n)): A204981, A006519(?)
%C ... s(k(n))-s(j(n)): A204983(?), A204984
%C s(n)=2^n, powers of 2
%C ... k(n), j(n): A204987, A204988
%C ... s(k(n)),s(j(n)): A204989, A140670(?)
%C ... s(k(n))-s(j(n)): A204991, A204992
%C s(n)=C(n+1,2), triangular numbers
%C ... k(n), j(n): A205002, A205003
%C ... s(k(n)),s(j(n)): A205004, A205005
%C ... s(k(n))-s(j(n)): A205006, A205007
%C s(n)=n^2, squares
%C ... k(n), j(n): A204905, A204995
%C ... s(k(n)),s(j(n)): A204996, A204997
%C ... s(k(n))-s(j(n)): A204998, A204999
%C s(n)=(2n-1)^2, odd squares
%C ... k(n), j(n): A205378, A205379
%C ... s(k(n)),s(j(n)): A205380, A205381
%C ... s(k(n))-s(j(n)): A205382, A205383
%C s(n)=n(3n-1), pentagonal numbers
%C ... k(n), j(n): A205138, A205139
%C ... s(k(n)),s(j(n)): A205140, A205141
%C ... s(k(n))-s(j(n)): A205142, A205143
%C s(n)=n(2n-1), hexagonal numbers
%C ... k(n), j(n): A205130, A205131
%C ... s(k(n)),s(j(n)): A205132, A205133
%C ... s(k(n))-s(j(n)): A205134, A205135
%C s(n)=C(2n-2,n-1), central binomial coefficients
%C ... k(n), j(n): A205010, A205011
%C ... s(k(n)),s(j(n)): A205012, A205013
%C ... s(k(n))-s(j(n)): A205014, A205015
%C s(n)=(1/2)C(2n,n), (1/2)*(central binomial coefficients)
%C ... k(n), j(n): A205386, A205387
%C ... s(k(n)),s(j(n)): A205388, A205389
%C ... s(k(n))-s(j(n)): A205390, A205391
%C s(n)=n(n+1), oblong numbers
%C ... k(n), j(n): A205018, A205028
%C ... s(k(n)),s(j(n)): A205029, A205030
%C ... s(k(n))-s(j(n)): A205031, A205032
%C s(n)=n!, factorials
%C ... k(n), j(n): A204932, A204933
%C ... s(k(n)),s(j(n)): A204934, A204935
%C ... s(k(n))-s(j(n)): A204936, A204937
%C s(n)=n!!, double factorials
%C ... k(n), j(n): A204982, A205100
%C ... s(k(n)),s(j(n)): A205101, A205102
%C ... s(k(n))-s(j(n)): A205103, A205104
%C s(n)=3^n-2^n
%C ... k(n), j(n): A205000, A205107
%C ... s(k(n)),s(j(n)): A205108, A205109
%C ... s(k(n))-s(j(n)): A205110, A205111
%C s(n)=Fibonacci(n+1)
%C ... k(n), j(n): A204924, A204925
%C ... s(k(n)),s(j(n)): A204926, A204927
%C ... s(k(n))-s(j(n)): A204928, A204929
%C s(n)=Fibonacci(2n-1)
%C ... k(n), j(n): A205442, A205443
%C ... s(k(n)),s(j(n)): A205444, A205445
%C ... s(k(n))-s(j(n)): A205446, A205447
%C s(n)=Fibonacci(2n)
%C ... k(n), j(n): A205450, A205451
%C ... s(k(n)),s(j(n)): A205452, A205453
%C ... s(k(n))-s(j(n)): A205454, A205455
%C s(n)=Lucas(n)
%C ... k(n), j(n): A205114, A205115
%C ... s(k(n)),s(j(n)): A205116, A205117
%C ... s(k(n))-s(j(n)): A205118, A205119
%C s(n)=n*(2^(n-1))
%C ... k(n), j(n): A205122, A205123
%C ... s(k(n)),s(j(n)): A205124, A205125
%C ... s(k(n))-s(j(n)): A205126, A205127
%C s(n)=ceiling[n^2/2]
%C ... k(n), j(n): A205394, A205395
%C ... s(k(n)),s(j(n)): A205396, A205397
%C ... s(k(n))-s(j(n)): A205398, A205399
%C s(n)=floor[(n+1)^2/2]
%C ... k(n), j(n): A205402, A205403
%C ... s(k(n)),s(j(n)): A205404, A205405
%C ... s(k(n))-s(j(n)): A205406, A205407
%H Charles R Greathouse IV, <a href="/A204892/b204892.txt">Table of n, a(n) for n = 1..10000</a>
%e Let s(k)=prime(k). As in A204890, the ordering of differences s(k)-s(j), follows from the arrangement shown here:
%e k...........1..2..3..4..5...6...7...8...9
%e s(k)........2..3..5..7..11..13..17..19..23
%e ...
%e s(k)-s(1)......1..3..5..9..11..15..17..21..27
%e s(k)-s(2).........2..4..8..10..14..16..20..26
%e s(k)-s(3)............2..6..8...12..14..18..24
%e s(k)-s(4)...............4..6...10..12..16..22
%e ...
%e least (k,j) such that 1 divides s(k)-s(j) for some j is (2,1), so a(1)=2.
%e least (k,j) s.t. 2 divides s(k)-s(j): (3,2), so a(2)=3.
%e least (k,j) s.t. 3 divides s(k)-s(j): (3,1), so a(3)=3.
%t s[n_] := s[n] = Prime[n]; z1 = 400; z2 = 50;
%t Table[s[n], {n, 1, 30}] (* A000040 *)
%t u[m_] := u[m] = Flatten[Table[s[k] - s[j],
%t {k, 2, z1}, {j, 1, k - 1}]][[m]]
%t Table[u[m], {m, 1, z1}] (* A204890 *)
%t v[n_, h_] := v[n, h] = If[IntegerQ[u[h]/n], h, 0]
%t w[n_] := w[n] = Table[v[n, h], {h, 1, z1}]
%t d[n_] := d[n] = First[Delete[w[n],
%t Position[w[n], 0]]]
%t Table[d[n], {n, 1, z2}] (* A204891 *)
%t k[n_] := k[n] = Floor[(3 + Sqrt[8 d[n] - 1])/2]
%t m[n_] := m[n] = Floor[(-1 + Sqrt[8 n - 7])/2]
%t j[n_] := j[n] = d[n] - m[d[n]] (m[d[n]] + 1)/2
%t Table[k[n], {n, 1, z2}] (* A204892 *)
%t Table[j[n], {n, 1, z2}] (* A204893 *)
%t Table[s[k[n]], {n, 1, z2}] (* A204894 *)
%t Table[s[j[n]], {n, 1, z2}] (* A204895 *)
%t Table[s[k[n]] - s[j[n]], {n, 1, z2}] (* A204896 *)
%t Table[(s[k[n]] - s[j[n]])/n, {n, 1, z2}] (* A204897 *)
%t (* Program 2: generates A204892 and A204893 rapidly *)
%t s = Array[Prime[#] &, 120];
%t lk = Table[NestWhile[# + 1 &, 1, Min[Table[Mod[s[[#]] - s[[j]], z], {j, 1, # - 1}]] =!= 0 &], {z, 1, Length[s]}]
%t Table[NestWhile[# + 1 &, 1, Mod[s[[lk[[j]]]] - s[[#]], j] =!= 0 &], {j, 1, Length[lk]}]
%t (* _Peter J. C. Moses_, Jan 27 2012 *)
%o (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
%Y Cf. A000040, A204890.
%K nonn
%O 1,1
%A _Clark Kimberling_, Jan 20 2012