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.

%I A164917 #16 Dec 14 2017 04:13:31
%S A164917 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,
%T A164917 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,
%U A164917 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
%N A164917 Smallest number of steps to reach prime(n) by applying the map x->A060308(x) starting from any member of A164368.
%C A164917 Starting from some prime, iterated application of A060308 (or of the equivalent A059788) generates a chain of increasing prime numbers.
%C A164917 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).
%C A164917 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.
%H A164917 V. Shevelev, <a href="http://arXiv.org/abs/0908.2319">On critical small intervals containing primes</a>, arXiv:0908.2319 [math.NT], 2009.
%e A164917 The first prime chains of the mapping with A060308 initialized with members of A164368 are
%e A164917 2->3->5->7->13->23->43->83->163->317->631->1259->2503->..
%e A164917 11->19->37->73->139->277->547->1093->2179->4357->8713->17419->..
%e A164917 17->31->61->113->223->443->883->1759->3517->7027->14051->28099->..
%e A164917 29->53->103->199->397->787->1571->3137->6271->12541->25073->..
%e A164917 41->79->157->313->619->1237->2473->4943->9883->19763->39521->..
%e A164917 47->89->173->337->673->1327->2647->5281->10559->21107->..
%e A164917 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.
%p A164917 A060308 := proc(n) prevprime(2*n+1) ; end:
%p A164917 isA164368 := proc(p) local q ; q := nextprime(floor(p/2)) ; RETURN(numtheory[pi](2*q) -numtheory[pi](p) >= 1); end:
%p A164917 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:
%p A164917 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:
%p A164917 seq(A164917(n),n=1..120) ; # _R. J. Mathar_, Sep 24 2009
%t A164917 A060308[n_] := NextPrime[2*n + 1, -1];
%t A164917 isA164368[p_] := Module[{q}, q = NextPrime[Floor[p/2]]; Return[PrimePi[2*q] - PrimePi[p] >= 1]];
%t A164917 A164368[n_] := A164368[n] = Module[{a}, If[n == 1, 2, a = NextPrime[ A164368[n-1]]; While[Not @ isA164368[a], a = NextPrime[a]]; Return[a]]];
%t A164917 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];
%t A164917 Table[A164917[n], {n, 1, 120}] (* _Jean-François Alcover_, Dec 14 2017, after _R. J. Mathar_ *)
%Y A164917 Cf. A006992, A104272, A164368, A164288.
%K A164917 nonn
%O A164917 1,3
%A A164917 _Vladimir Shevelev_, Aug 31 2009
%E A164917 Edited, examples added and extended by _R. J. Mathar_, Sep 24 2009