cp's OEIS Frontend

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

%I A090418 #31 Jun 01 2024 11:56:08
%S A090418 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,
%T A090418 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,
%U A090418 0,0,1,2,0,1,0,0,0,0,1,2,0,1,0,2,0,1,1
%N A090418 Number of ways to write n in binary representation as a concatenation of primes.
%H A090418 Reinhard Zumkeller, <a href="/A090418/b090418.txt">Table of n, a(n) for n = 0..10000</a> (corrected by _Georg Fischer_, Jan 20 2019)
%F A090418 a(A090419(n))=0; a(A090420(n))=1; a(A090421(n))>0;
%F A090418 a(A090422(n))=1; a(A090423(n))>1;
%F A090418 a(A090424(n)) = n and a(m) <> n for m < A090424(n).
%F A090418 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
%e A090418 n=23 -> '10111': '10"111'==2"7, '101"11'==5"3 and '10111'==23, therefore a(23)=3.
%o A090418 (Haskell)
%o A090418 import Data.List (stripPrefix, unfoldr)
%o A090418 import Data.Maybe (fromJust)
%o A090418 a090418 n = a090418_list !! (n-1)
%o A090418 a090418_list = 0 : f 2 where
%o A090418    f x = (sum $ map g bpss) : f (x + 1) where
%o A090418      g ps | suffix == Nothing = 0
%o A090418           | suffix' == []     = 1
%o A090418           | last suffix' == 0 = 0
%o A090418           | otherwise         = a090418 $ fromBits suffix'
%o A090418           where suffix' = fromJust suffix
%o A090418                 suffix = stripPrefix ps $ toBits x
%o A090418      bpss = take (fromInteger $ a000720 x) $
%o A090418                   map (toBits . fromInteger) a000040_list
%o A090418    toBits = unfoldr
%o A090418             (\u -> if u == 0 then Nothing else Just (mod u 2, div u 2))
%o A090418    fromBits = foldr (\b v -> 2 * v + b) 0
%o A090418 -- _Reinhard Zumkeller_, Aug 06 2012
%o A090418 (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
%Y A090418 Cf. A004676, A007088.
%Y A090418 Cf. A191232, A000040.
%Y A090418 Cf. A090421, A090423, A257318.
%K A090418 nonn,base
%O A090418 0,12
%A A090418 _Reinhard Zumkeller_, Nov 30 2003
%E A090418 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
%E A090418 Data in b-file double-checked with independent PARI code by _M. F. Hasler_, Apr 21 2015