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,2

Comments

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

Links

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

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)

Example

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.

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A152537 A182028 A081253 * A206927 A019299 A052932

Adjacent sequences: A118252 A118253 A118254 * A118256 A118257 A118258

Keyword

nonn

Author

Pierre CAMI, Apr 19 2006

Extensions

Corrected by Omar E. Pol, Nov 08 2007

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

Status

approved