|
%I #39 Jun 05 2013 05:33:27
%S 7,6,3,1,2,0,0,2,1,1,1,1,2,0,0,1,0,0,0,0,0,2,1,5,1,0,0,0,0,1,0,1,0,1,
%T 0,0,1,0,0,1,4,0,1,0,0,1,1,0,0,1,1,1,0,1,0,0,0,1,0,1,0,1,1,0,0,0,2,1,
%U 0,0,0,3,1,0,1,0,0,0,0,0,1,0,1,0,2,1
%N Total number of primes which can be reached via Cunningham chains, starting with prime(n), not counting this starting prime.
%C Other definition: Count of the binary descendants of the n-th prime. Prime q is a binary descendant of prime p if 2*p-1 <= q <= 2*p+1.
%C a(n) is the total count of direct binary descendants of the n-th prime plus their binary descendants, and so on.
%C q=(p-1)*2 + b*2 + 1, where b is either 0 or 1. Thus if p>2 then in base 2: q is p with a digit inserted before the least significant digit.
%C It is conjectured there are arbitrarily big terms (see the MathWorld link).
%C If p==2 (mod 3), then only 2p+1 (==2 (mod 3) again) may be prime; 2p-1 will be divisible by 3. For p==1 (mod 3), only 2p-1 (==1 (mod 3) again) can be prime. Therefore, there can be no alternance in the +1/-1 choice (except for starting primes 2 and 3) when looking at all possible descendants. This leads to the formula by T. D. Noe. - _M. F. Hasler_, Jul 13 2012
%H Jens Kruse Andersen and Eric W. Weisstein, <a href="http://mathworld.wolfram.com/CunninghamChain.html">MathWorld: Cunningham Chain</a>
%F a(n) = max(A181697(n), A181715(n)) - 1 for n > 2. - _T. D. Noe_, Jul 12 2012
%e prime(3)=5 has one binary descendant 11, which has one b.d. 23, which has one b.d. 47. Because 47 has no binary descendants, a(3)=3.
%e prime(4)=7 has one binary descendant 13, which has no binary descendants, so a(4)=1.
%e As explained in the comment, for n>2 this equals the maximum length of either of the Cunningham chains, i.e., iterations of x->2x+1 resp. x->2x-1 before getting a composite. For prime(2)=3, the first map yields (3)->7->(15) and the second map yields (3)->5->(9), so there are 2 primes, but one has to add the a(4)+a(3)=3+1 descendants of these 2 primes, whence a(2)=2+4=6.
%e Starting with prime(1)=2, the "2x-1" map yields 3, to which one must add its a(2)=6 descendants. They already include the prime 5 = 2*2+1 and its descendants. Thus, a(1)=1+6=7.
%t des[n_] := {If[PrimeQ[2*n-1], s = AppendTo[s, 2*n-1]; des[2*n-1]]; If[PrimeQ[2*n+1], s = AppendTo[s, 2*n+1]; des[2*n+1]]}; Table[s = {}; des[Prime[n]]; Length[Union[s]], {n, 100}] (* _T. D. Noe_, Jul 11 2012 *)
%Y Cf. A000040.
%Y Cf. A005383 - primes of the form prime*2-1.
%Y Cf. A005385 - primes of the form prime*2+1.
%Y Cf. A214342 - count of the decimal descendants.
%Y Cf. A181697, A181715 (two kinds of Cunningham chains).
%K nonn,base,easy
%O 1,1
%A _Alex Ratushnyak_, Jul 09 2012
|
