Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #31 Oct 24 2024 23:51:56
%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