A090423 - OEIS

%I #32 May 16 2021 10:48:12

%S 11,23,29,31,43,47,59,61,71,79,83,109,113,127,151,157,167,173,179,181,

%T 191,223,229,233,239,241,251,271,283,317,337,347,349,353,359,367,373,

%U 379,383,431,433,439,457,463,467,479,487,491,499,503,509,541,563,599,607

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

%C A090418(a(n)) > 1; subsequence of A090421.

%H Reinhard Zumkeller, <a href="/A090423/b090423.txt">Table of n, a(n) for n = 1..10000</a>

%e 337 is 101010001 in binary,

%e 10 is 2,

%e 10 is 2,

%e 10001 is 17, partition is 10_10_10001, so 337 is in the sequence.

%o (Python)

%o # Primes = [2,...,607]

%o from sympy import sieve

%o primes = list(sieve.primerange(1, 608))

%o def tryPartioning(binString):   # First digit is not 0

%o     l = len(binString)

%o     for t in range(2, l-1):

%o         substr1 = binString[:t]

%o         if (int('0b'+substr1,2) in primes) or (t>=4 and tryPartioning(substr1)):

%o             substr2 = binString[t:]

%o             if substr2[0]!='0':

%o                 if (int('0b'+substr2,2) in primes) or (l-t>=4 and tryPartioning(substr2)):

%o                     return 1

%o     return 0

%o for p in primes:

%o     if tryPartioning(bin(p)[2:]):

%o         print(p, end=',')

%o (Python)

%o from sympy import isprime, primerange

%o def ok(p):

%o   b = bin(p)[2:]

%o   for i in range(2, len(b)-1):

%o     if isprime(int(b[:i], 2)) and b[i] != '0':

%o       if isprime(int(b[i:], 2)) or ok(int(b[i:], 2)): return True

%o   return False

%o def aupto(lim): return [p for p in primerange(2, lim+1) if ok(p)]

%o print(aupto(607)) # _Michael S. Branicky_, May 16 2021

%o (Haskell)

%o a090423 n = a090423_list !! (n-1)

%o a090423_list = filter ((> 1 ) . a090418 . fromInteger) a000040_list

%o -- _Reinhard Zumkeller_, Aug 06 2012

%o (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 Cf. A090422, A000040, A004676, A007088.

%K nonn,base

%O 1,1

%A _Reinhard Zumkeller_, Nov 30 2003

%E Corrected by _Alex Ratushnyak_, Aug 03 2012