login
Total number of primes which can be reached via Cunningham chains, starting with prime(n), not counting this starting prime.
1

%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