A118255 a(1)=1, then a(n)=2*a(n-1) if n is prime, a(n)=2*a(n-1)+1 if n not prime.

1, 2, 4, 9, 18, 37, 74, 149, 299, 599, 1198, 2397, 4794, 9589, 19179, 38359, 76718, 153437, 306874, 613749, 1227499, 2454999, 4909998, 9819997, 19639995, 39279991, 78559983, 157119967, 314239934, 628479869, 1256959738, 2513919477, 5027838955, 10055677911

Offset: 1

Author

Pierre CAMI, Apr 19 2006

Keywords

• nonn

Comments

In base 2 a(n) is the concatenation for i=1 to n of A005171(i).

Examples

			a(2) = 2*1 = 2 as 2 is prime;
a(3) = 2*2 = 4 as 3 is prime;
a(4) = 2*4+1 = 9 as 4 is composite;
a(5) = 2*9 = 18 as 5 is prime.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..3322 (terms 1..1000 from Harvey P. Dale)

Crossrefs

Cf. A000225, A005171, A051006, A072762, A118256, A118257.

Programs

Maple

f:=proc(n) option remember; if n=1 then RETURN(1); fi; if isprime(n) then 2*f(n-1) else 2*f(n-1)+1; fi; end; # N. J. A. Sloane

Mathematica

nxt[{n_,a_}]:={n+1,If[PrimeQ[n+1],2a,2a+1]}; Transpose[NestList[nxt,{1,1},40]][[2]] (* Harvey P. Dale, Jan 22 2015 *)
Array[FromDigits[#, 2] &@ Array[Boole[! PrimeQ@ #] &, #] &, 34] (* Michael De Vlieger, Nov 01 2016 *)

Python

from sympy import isprime, prime
def a(n): return int("".join(str(1-isprime(i)) for i in range(1, n+1)), 2)
print([a(n) for n in range(1, 35)]) # Michael S. Branicky, Jan 10 2022

Python

# faster version for initial segment of sequence
from sympy import isprime
from itertools import count, islice
def agen(): # generator of terms
    an = 0
    for k in count(1):
        an = 2 * an + int(not isprime(k))
        yield an
print(list(islice(agen(), 34))) # Michael S. Branicky, Jan 10 2022

Formula

a(n) = floor(k * 2^n) where k = 0.585317... = 1 - A051006. [Charles R Greathouse IV, Dec 27 2011]

From Ridouane Oudra, Aug 26 2019: (Start)

a(n) = 2^n - 1 - (1/2)*(pi(n) + Sum_{i=1..n} 2^(n-i)*pi(i)), where pi = A000720

a(n) = A000225(n) - A072762(n). (End)

Extensions

Corrected by Omar E. Pol, Nov 08 2007

Corrections verified by N. J. A. Sloane, Nov 17 2007