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

Author

Reinhard Zumkeller, Nov 30 2003

Keywords

• nonn
• base

Examples

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

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 (corrected by _Georg Fischer_, Jan 20 2019)

Crossrefs

Cf. A004676, A007088.

Cf. A191232, A000040.

Cf. A090421, A090423, A257318.

Programs

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

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

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