cp's OEIS Frontend

A090423 Primes that can be written in binary representation as concatenation of other primes.

%I A090423 #32 May 16 2021 10:48:12
%S A090423 11,23,29,31,43,47,59,61,71,79,83,109,113,127,151,157,167,173,179,181,
%T A090423 191,223,229,233,239,241,251,271,283,317,337,347,349,353,359,367,373,
%U A090423 379,383,431,433,439,457,463,467,479,487,491,499,503,509,541,563,599,607
%N A090423 Primes that can be written in binary representation as concatenation of other primes.
%C A090423 A090418(a(n)) > 1; subsequence of A090421.
%H A090423 Reinhard Zumkeller, <a href="/A090423/b090423.txt">Table of n, a(n) for n = 1..10000</a>
%e A090423 337 is 101010001 in binary,
%e A090423 10 is 2,
%e A090423 10 is 2,
%e A090423 10001 is 17, partition is 10_10_10001, so 337 is in the sequence.
%o A090423 (Python)
%o A090423 # Primes = [2,...,607]
%o A090423 from sympy import sieve
%o A090423 primes = list(sieve.primerange(1, 608))
%o A090423 def tryPartioning(binString):   # First digit is not 0
%o A090423     l = len(binString)
%o A090423     for t in range(2, l-1):
%o A090423         substr1 = binString[:t]
%o A090423         if (int('0b'+substr1,2) in primes) or (t>=4 and tryPartioning(substr1)):
%o A090423             substr2 = binString[t:]
%o A090423             if substr2[0]!='0':
%o A090423                 if (int('0b'+substr2,2) in primes) or (l-t>=4 and tryPartioning(substr2)):
%o A090423                     return 1
%o A090423     return 0
%o A090423 for p in primes:
%o A090423     if tryPartioning(bin(p)[2:]):
%o A090423         print(p, end=',')
%o A090423 (Python)
%o A090423 from sympy import isprime, primerange
%o A090423 def ok(p):
%o A090423   b = bin(p)[2:]
%o A090423   for i in range(2, len(b)-1):
%o A090423     if isprime(int(b[:i], 2)) and b[i] != '0':
%o A090423       if isprime(int(b[i:], 2)) or ok(int(b[i:], 2)): return True
%o A090423   return False
%o A090423 def aupto(lim): return [p for p in primerange(2, lim+1) if ok(p)]
%o A090423 print(aupto(607)) # _Michael S. Branicky_, May 16 2021
%o A090423 (Haskell)
%o A090423 a090423 n = a090423_list !! (n-1)
%o A090423 a090423_list = filter ((> 1 ) . a090418 . fromInteger) a000040_list
%o A090423 -- _Reinhard Zumkeller_, Aug 06 2012
%o A090423 (PARI) is_A090423(n)={isprime(n)&&for(i=2, #binary(n)-2, bittest(n, i-1)&&isprime(n%2^i)&&is_A090421(n>>i)&&return(1))} \\ _M. F. Hasler_, Apr 21 2015
%Y A090423 Cf. A090422, A000040, A004676, A007088.
%K A090423 nonn,base
%O A090423 1,1
%A A090423 _Reinhard Zumkeller_, Nov 30 2003
%E A090423 Corrected by _Alex Ratushnyak_, Aug 03 2012