A090418 Number of ways to write n in binary representation as a concatenation of primes.

0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 2, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 3, 0, 0, 0, 0, 0, 2, 1, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 3, 0, 2, 2, 4, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 3, 0, 3, 1, 2, 0, 0, 0, 1, 0, 0, 1, 2, 0, 1, 0, 0, 0, 0, 1, 2, 0, 1, 0, 2, 0, 1, 1

Offset

0,12

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 (corrected by Georg Fischer, Jan 20 2019)

Formula

a(A090419(n))=0; a(A090420(n))=1; a(A090421(n))>0;

a(A090422(n))=1; a(A090423(n))>1;

a(A090424(n)) = n and a(m) <> n for m < A090424(n).

a(n) = 0 if a = 0 (mod 4); a(n) = a(floor(n/4)) if a = 2 (mod 4). - M. F. Hasler, Apr 21 2015

Example

n=23 -> '10111': '10"111'==2"7, '101"11'==5"3 and '10111'==23, therefore a(23)=3.

Prog

(Haskell)
import Data.List (stripPrefix, unfoldr)
import Data.Maybe (fromJust)
a090418 n = a090418_list !! (n-1)
a090418_list = 0 : f 2 where
   f x = (sum $ map g bpss) : f (x + 1) where
     g ps | suffix == Nothing = 0
          | suffix' == []     = 1
          | last suffix' == 0 = 0
          | otherwise         = a090418 $ fromBits suffix'
          where suffix' = fromJust suffix
                suffix = stripPrefix ps $ toBits x
     bpss = take (fromInteger $ a000720 x) $
                  map (toBits . fromInteger) a000040_list
   toBits = unfoldr
            (\u -> if u == 0 then Nothing else Just (mod u 2, div u 2))
   fromBits = foldr (\b v -> 2 * v + b) 0
-- Reinhard Zumkeller, Aug 06 2012
(PARI) A090418(n)={ while( n>9 && !bittest(n, 0), bittest(n, 1)||return; n>>=2); n<10 && return(isprime(n)); sum(k=2, #binary(n)-2, if(bittest(n, k-1)&&isprime(n%2^k), A090418(n>>k)), isprime(n))} \\ M. F. Hasler, Apr 21 2015

Crossrefs

Cf. A004676, A007088.

Cf. A191232, A000040.

Cf. A090421, A090423, A257318.

Sequence in context: A351563 A362983 A352822 * A363877 A322452 A076754

Adjacent sequences: A090415 A090416 A090417 * A090419 A090420 A090421

Keyword

nonn,base

Author

Reinhard Zumkeller, Nov 30 2003

Extensions

Thanks to Alex Ratushnyak, who found an error in A090423, which was the consequence of errors in this sequence; the program was rewritten and data was recomputed by Reinhard Zumkeller, Aug 06 2012

Data in b-file double-checked with independent PARI code by M. F. Hasler, Apr 21 2015

Status

approved