OFFSET
1,1
COMMENTS
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.
a(n) is the total count of direct binary descendants of the n-th prime plus their binary descendants, and so on.
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.
It is conjectured there are arbitrarily big terms (see the MathWorld link).
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
LINKS
Jens Kruse Andersen and Eric W. Weisstein, MathWorld: Cunningham Chain
EXAMPLE
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.
prime(4)=7 has one binary descendant 13, which has no binary descendants, so a(4)=1.
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.
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.
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Alex Ratushnyak, Jul 09 2012
STATUS
approved