A060308 -id:A060308 - cp's OEIS frontend

A164917 Smallest number of steps to reach prime(n) by applying the map x->A060308(x) starting from any member of A164368.

0, 1, 2, 3, 0, 4, 0, 1, 5, 0, 1, 2, 0, 6, 0, 1, 0, 2, 0, 0, 3, 1, 7, 1, 0, 0, 2, 0, 0, 1, 0, 1, 0, 1, 0, 0, 2, 8, 0, 2, 0, 0, 0, 1, 0, 1, 1, 2, 0, 0, 0, 0, 0, 1, 2, 0, 0, 1, 2, 0, 0, 1, 0, 0, 3, 9, 1, 3, 0, 0, 1, 1, 0, 0, 1, 2, 1, 2, 0, 0, 0, 2, 0, 0, 0, 3, 1, 1, 0, 1, 1, 1, 0, 0, 2, 0, 3, 0, 1, 2, 3, 1, 1, 0, 0, 2

Offset: 1

Vladimir Shevelev, Aug 31 2009

nonn

Starting from some prime, iterated application of A060308 (or of the equivalent A059788) generates a chain of increasing prime numbers.
The nature of these chains is to reach higher in the list of primes, sometimes "over-satisfying" Bertrand's postulate by skipping some nearer primes, almost doubling of possible. On the other hand, A164368 contains the primes that would be skipped by a chain which contains the prime slightly above half of their value. The sequence shows how far up in chains starting from some member of A164368 we find prime(n), or equivalently, how many inverse applications of the map we need to hit a member of A164368 if starting at prime(n).
Note that by construction A164368(k) starts with the smallest prime that is not member of any chain started from any previous A164368. So each prime exists at some place in one of these chains, and the number of steps a(n) to reach it from the start of its chain is well defined.

			The first prime chains of the mapping with A060308 initialized with members of A164368 are
2->3->5->7->13->23->43->83->163->317->631->1259->2503->..
11->19->37->73->139->277->547->1093->2179->4357->8713->17419->..
17->31->61->113->223->443->883->1759->3517->7027->14051->28099->..
29->53->103->199->397->787->1571->3137->6271->12541->25073->..
41->79->157->313->619->1237->2473->4943->9883->19763->39521->..
47->89->173->337->673->1327->2647->5281->10559->21107->..
The a(1) to a(4) representing the first 4 primes are all on the first chain, and need 0 to 3 steps to be reached from 2 = A164368(1). a(5) asks for the number of steps for A000040(5)=11 which is on the second chain, and needs 0 steps.

V. Shevelev, On critical small intervals containing primes, arXiv:0908.2319 [math.NT], 2009.

Cf. A006992, A104272, A164368, A164288.

A060308 := proc(n) prevprime(2*n+1) ; end:
isA164368 := proc(p) local q ; q := nextprime(floor(p/2)) ; RETURN(numtheory[pi](2*q) -numtheory[pi](p) >= 1); end:
A164368 := proc(n) option remember; local a; if n = 1 then 2; else a := nextprime( procname(n-1)) ; while not isA164368(a) do a := nextprime(a) ; od: RETURN(a) ; fi; end:
A164917 := proc(n) local p,a,j,q,itr ; p := ithprime(n) ; a := 1000000000000000 ; for j from 1 do q := A164368(j) ; if q > p then break; fi; itr := 0 ; while q < p do q := A060308(q) ; itr := itr+1 ; od; if q = p then if itr < a then a := itr; fi; fi; od: a ; end:
seq(A164917(n),n=1..120) ; # R. J. Mathar, Sep 24 2009

A060308[n_] := NextPrime[2*n + 1, -1];
isA164368[p_] := Module[{q}, q = NextPrime[Floor[p/2]]; Return[PrimePi[2*q] - PrimePi[p] >= 1]];
A164368[n_] := A164368[n] = Module[{a}, If[n == 1, 2, a = NextPrime[ A164368[n-1]]; While[Not @ isA164368[a], a = NextPrime[a]]; Return[a]]];
A164917[n_] := Module[{p, a, j, q, itr}, p = Prime[n]; a = 10^15; For[j = 1 , True, j++, q = A164368[j]; If[q > p, Break[]]; itr = 0; While[q < p, q = A060308[q]; itr++]; If[q == p, If[itr < a, a = itr]]]; a];
Table[A164917[n], {n, 1, 120}] (* Jean-François Alcover, Dec 14 2017, after R. J. Mathar *)

Edited, examples added and extended by R. J. Mathar, Sep 24 2009

A118747 a(n) = product[k=1..n] P(k), where P(k) is the largest prime <= 2*k. a(n) = product[k=1..n] A060308(k).

Original entry on oeis.org

2, 6, 30, 210, 1470, 16170, 210210, 2732730, 46456410, 882671790, 16770764010, 385727572230, 8871734161290, 204049885709670, 5917446685580430, 183440847252993330, 5686666264842793230, 176286654210126590130

Offset: 1

Jonathan Vos Post, Apr 29 2006

Cf. A020482, A049653, A060266-A060268, A060264, A060265, A060308, A118455, A118456, A118748.

A164918 The smallest starting prime which reaches prime(n) by repeated application of the map x->A060308(x).

Original entry on oeis.org

2, 2, 2, 2, 11, 2, 17, 11, 2, 29, 17, 11, 41, 2, 47, 29, 59, 17, 67, 71, 11, 41, 2, 47, 97, 101, 29, 107, 109, 17, 127, 67, 137, 11, 149, 151, 41, 2, 167, 47, 179, 181, 191, 97, 197, 29, 107, 17, 227, 229, 233, 239, 241, 127, 67, 263, 269, 137, 11, 281, 283, 149, 307, 311, 41

Offset: 1

Vladimir Shevelev, Aug 31 2009

nonn

a(n) is the starting value of the prime chain described in A164917 which contains (touches) prime(n).

By construction, each member of this sequence here is one of the values of A164368, the head elements of all chains of this map.

			The first four values are 2 because prime(1)=2, prime(2)=3, prime(3)=5 and prime(4)=7 are all in the prime chain starting at 2.

V. Shevelev, On critical small intervals containing primes, arXiv:0908.2319 [math.NT], 2009.

Cf. A006992, A164917, A104272, A164368, A164288.

A060308 := proc(n) prevprime(2*n+1) ; end:
isA164368 := proc(p) local q ; q := nextprime(floor(p/2)) ; return (numtheory[pi](2*q) -numtheory[pi](p) >= 1); end proc:
A164368 := proc(n) option remember; local a; if n = 1 then 2; else a := nextprime( procname(n-1)) ; while not isA164368(a) do a := nextprime(a) ; end do : RETURN(a) ; end if; end proc:
A164918 := proc(n) local p, a, j, q, itr ; p := ithprime(n) ; a := 1000000000000000 ; for j from 1 do q := A164368(j) ; if q > p then break; end if; itr := 0 ; while q < p do q := A060308(q) ; itr := itr+1 ; end do; if q = p then return A164368(j) ; end if; end do: end proc:
seq(A164918(n), n=1..120) ; # R. J. Mathar, Mar 12 2010

lp[n_] := NextPrime[2n, -1];
a[n_] := For[pn = Prime[n]; p = 2, p <= pn, p = NextPrime[p], nwl = NestWhileList[lp, p, # <= Prime[n]&]; If[MemberQ[nwl, pn], Return[p]]];
Array[a, 120] (* Jean-François Alcover, Dec 01 2017 *)

Edited and extended by R. J. Mathar, Mar 12 2010

A135145 Values of m where A020482(m) != A060308(m-1).

Original entry on oeis.org

49, 61, 64, 74, 95, 104, 110, 125, 146, 151, 154, 163, 166, 173, 184, 199, 205, 209, 215, 229, 238, 244, 250, 259, 266, 269, 278, 293, 314, 320, 335, 346, 350, 355, 359, 364, 376, 385, 391, 394, 398, 403, 410, 419, 424, 427, 436, 439, 448, 451, 454, 460

Offset: 1

Harry J. Smith, Nov 20 2007

nonn

Usually the greatest p with p,q both prime, p+q = 2m, is equal to the largest prime <= 2m-2, but not always. These are the exceptions.

Almost all natural numbers are in the sequence so the above comment is misleading in general, and only fitting for small numbers. - Jens Kruse Andersen, Jul 13 2014

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000

Cf. A020482, A060308.

a2[n_] := {p, q} /. {ToRules @ Reduce[p+q == 2*n, {p, q}, Primes]} // Max; a8[n_] := Max[FactorInteger[(2*n)!/n!^2]]; Select[Range[500], a2[#] != a8[#-1]&] (* Jean-François Alcover, Dec 19 2013 *)

for(m=2, 1000, p=precprime(2*m-2); if(!isprime(2*m-p), print1(m", "))) \\ Jens Kruse Andersen, Jul 12 2014

A238256 A060308 begins with one 2, one 3, one 5, two 7's, one 11, two 13's, i.e., d(n) = 1, 1, 1, 2, 1, 2, 1, 2, 3, 1,... times the primes (A000040). a(n) uses this distribution with noncomposites (A008578).

Original entry on oeis.org

1, 2, 3, 5, 5, 7, 11, 11, 13, 17, 17, 19, 19, 19, 23, 29, 29, 29, 31, 31, 37, 41, 41, 43, 43, 43, 47, 47, 47, 53, 59, 59, 59, 61, 61, 67, 71, 71, 71, 73, 73, 79, 79, 79, 83, 83, 83, 83, 89, 89, 97, 101, 101, 103, 107, 107, 109, 109, 109, 109, 109, 109, 109

Offset: 1

Paul Curtz, Mar 10 2014

nonn

Paul Curtz, Table of n, a(n) for n = 1..63

Cf. A224911.

lista(nn) = {nn = nn\2; v = vector(nn, i, precprime(2*i)); vnc = concat(1, vector(nn, i, prime(i))); nv = vector(1, i, vnc[i]); ivnc = 1; for (i=2, #v, if (v[i] == v[i-1], nv = concat(nv, nv[#nv]), ivnc++; nv = concat(nv, vnc[ivnc]));); for (i=1, #nv, print1(nv[i], ", "));} \\ Michel Marcus, Mar 20 2014

Conjecture: a(n) is the greatest noncomposite (A008578) dividing A238691(n-1).

A244207 Numbers 2m such that A020482(m) != A060308(m-1).

Original entry on oeis.org

98, 122, 128, 148, 190, 208, 220, 250, 292, 302, 308, 326, 332, 346, 368, 398, 410, 418, 430, 458, 476, 488, 500, 518, 532, 538, 556, 586, 628, 640, 670, 692, 700, 710, 718, 728, 752, 770, 782, 788, 796, 806, 820, 838, 848, 854, 872, 878, 896, 902, 908, 920

Offset: 1

Ivan Panchenko, Jun 22 2014

nonn

Usually the greatest p with p, q both prime, p + q = 2m, is equal to the largest prime <= 2m - 2, but not always. These are the exceptions, called "b numbers" ("b-Zahlen") by Nils Johan Pipping.
Almost all numbers are in the sequence. Only the beginning of the sequence is sparse. - Jens Kruse Andersen, Jul 12 2014
Let p be the smallest prime < 2n such that 2n-p is prime, and let r < 2n be the smallest odd nonprime > 1 such that 2n-r is prime; this sequence lists the numbers 2n for which r < p. - David James Sycamore, Jan 14 2019

			From _David James Sycamore_, Jan 14 2019: (Start)
98 is a term because (see 3rd comment above) p = 11 and r = 9.
128 is a term because then p = 19 and r = 15.
908 is a term because then p = 31 and r = 21. (End)

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000

Cf. A020482, A060308. Equals twice A135145.

for(m=2, 1000, p=precprime(2*m-2); if(!isprime(2*m-p), print1(2*m", "))) \\ Jens Kruse Andersen, Jul 12 2014

A135143 Values of A020482 where A020482(m) != A060308(m-1).

Original entry on oeis.org

79, 109, 109, 137, 179, 197, 197, 239, 281, 283, 277, 313, 313, 317, 349, 379, 397, 401, 419, 439, 463, 457, 487, 499, 521, 521, 509, 569, 617, 617, 659, 673, 683, 691, 701, 709, 739, 757, 769, 769, 773, 787, 809, 827, 829, 823, 859, 859, 883, 883, 877

Offset: 1

Harry J. Smith, Nov 20 2007

nonn

Usually the greatest p with p,q both prime, p+q = 2m, is equal to the largest prime <= 2m-2, but not always. These are the exceptions.

Cf. A020482, A060308.

A135144 Values of A060308 where A020482(m) != A060308(m-1).

Original entry on oeis.org

89, 113, 113, 139, 181, 199, 211, 241, 283, 293, 293, 317, 317, 337, 359, 389, 401, 409, 421, 449, 467, 479, 491, 509, 523, 523, 547, 577, 619, 631, 661, 683, 691, 701, 709, 719, 743, 761, 773, 773, 787, 797, 811, 829, 839, 839, 863, 863, 887, 887, 887

Offset: 1

Harry J. Smith, Nov 20 2007

nonn

Usually the greatest p with p,q both prime, p+q = 2m, is equal to the largest prime <= 2m-2, but not always. These are the exceptions.

Cf. A020482, A060308.

A035250 Number of primes between n and 2n (inclusive).

Original entry on oeis.org

1, 2, 2, 2, 2, 2, 3, 2, 3, 4, 4, 4, 4, 3, 4, 5, 5, 4, 5, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 7, 7, 8, 8, 9, 10, 9, 9, 10, 10, 10, 10, 9, 10, 10, 10, 9, 10, 10, 11, 12, 12, 12, 13, 13, 14, 14, 14, 13, 13, 12, 12, 13, 13, 14, 14, 13, 14, 15, 15, 14, 14, 13, 14, 15

Offset: 1

Erich Friedman

nonn

By Bertrand's Postulate (proved by Chebyshev), there is always a prime between n and 2n, i.e., a(n) is positive for all n.
The number of primes in the interval [n,2*n) is the same sequence as this, except that a(1) = 0. - N. J. A. Sloane, Oct 18 2024
The smallest and largest primes between n and 2n inclusive are A007918 and A060308 respectively. - Lekraj Beedassy, Jan 01 2007
The number of partitions of 2n into exactly two parts with first part prime, n > 1. - Wesley Ivan Hurt, Jun 15 2013

			The primes between n = 13 and 2n = 26, inclusive, are 13, 17, 19, 23; so a(13) = 4.
a(5) = 2, since 2(5) = 10 has 5 partitions into exactly two parts: (9,1),(8,2),(7,3),(6,4),(5,5).  Two primes are among the first parts: 7 and 5.

Aigner, M. and Ziegler, G. Proofs from The Book (2nd edition). Springer-Verlag, 2001.

N. J. A. Sloane, Table of n, a(n) for n = 1..20000 (first 1000 terms from T. D. Noe)
International Mathematics Olympiad, Proof of Bertrand's Postulate [Via Wayback Machine]

Cf. A073837, A073838, A099802, A060715.
Related sequences:
Primes (p) and composites (c): A000040, A002808, A000720, A065855.
Primes between p(n) and 2*p(n): A063124, A070046; between c(n) and 2*c(n): A376761; between n and 2*n: A035250, A060715, A077463, A108954.
Composites between p(n) and 2*p(n): A246514; between c(n) and 2*c(n): A376760; between n and 2*n: A075084, A307912, A307989, A376759.

a035250 n = sum $ map a010051 [n..2*n] -- Reinhard Zumkeller, Jan 08 2012

[#PrimesInInterval(n, 2*n): n in [1..80]]; // Bruno Berselli, Sep 05 2012

with(numtheory): A035250:=n->pi(2*n)-pi(n-1): seq(A035250(n), n=1..100); # Wesley Ivan Hurt, Aug 09 2014

f[n_] := PrimePi[2n] - PrimePi[n - 1]; Array[f, 76] (* Robert G. Wilson v, Dec 23 2012 *)

a(n)=primepi(2*n)-primepi(n-1) \\ Charles R Greathouse IV, Jul 01 2013

a(n) = A000720(2*n) - A000720(n-1); a(n) <= A179211(n). - Reinhard Zumkeller, Jul 05 2010
a(A059316(n)) = n and a(m) <> n for m < A059316(n). - Reinhard Zumkeller, Jan 08 2012
a(n) = sum(A010051(k): k=n..2*n). [Reinhard Zumkeller, Jan 08 2012]
a(n) = pi(2n) - pi(n-1). [Wesley Ivan Hurt, Jun 15 2013]

A060264 First prime after 2n.

Original entry on oeis.org

2, 3, 5, 7, 11, 11, 13, 17, 17, 19, 23, 23, 29, 29, 29, 31, 37, 37, 37, 41, 41, 43, 47, 47, 53, 53, 53, 59, 59, 59, 61, 67, 67, 67, 71, 71, 73, 79, 79, 79, 83, 83, 89, 89, 89, 97, 97, 97, 97, 101, 101, 103, 107, 107, 109, 113, 113, 127, 127, 127, 127, 127, 127, 127, 131

Offset: 0

Labos Elemer, Mar 23 2001

Conjecture: for n > 2, this is the least prime p such that 1^2, 2^2, 3^2, ..., n^2 are distinct mod p. Checked to 10^4. - Charles R Greathouse IV, Dec 03 2022

Harry J. Smith, Table of n, a(n) for n = 0..1000

Cf. A020482, A049653, A059786, A060308, A088633, A151800.

Cf. A005843.

a060264 = a151800 . (* 2)  -- Reinhard Zumkeller, Nov 15 2013

A060264 := proc(n)
        nextprime(2*n) ;
end proc:

Table[NextPrime[2n],{n,0,100}] (* Vladimir Joseph Stephan Orlovsky, Mar 03 2011 *)

a(n) = nextprime(2*n + 1)  \\ Harry J. Smith, Jul 03 2009

a(n) = A151800(2*n). - Reinhard Zumkeller, Nov 15 2013

cp's OEIS Frontend

A164917 Smallest number of steps to reach prime(n) by applying the map x->A060308(x) starting from any member of A164368.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A118747 a(n) = product[k=1..n] P(k), where P(k) is the largest prime <= 2*k. a(n) = product[k=1..n] A060308(k).

Views

Author

Keywords

Crossrefs

A164918 The smallest starting prime which reaches prime(n) by repeated application of the map x->A060308(x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A135145 Values of m where A020482(m) != A060308(m-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A238256 A060308 begins with one 2, one 3, one 5, two 7's, one 11, two 13's, i.e., d(n) = 1, 1, 1, 2, 1, 2, 1, 2, 3, 1,... times the primes (A000040). a(n) uses this distribution with noncomposites (A008578).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A244207 Numbers 2m such that A020482(m) != A060308(m-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A135143 Values of A020482 where A020482(m) != A060308(m-1).

Views

Author

Keywords

Comments

Crossrefs

A135144 Values of A060308 where A020482(m) != A060308(m-1).

Views

Author

Keywords

Comments

Crossrefs

A035250 Number of primes between n and 2n (inclusive).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs