# Prime decimal representations of prime binary numbers [duplicate]

Problem Statement: Consider a number n in base-10. Find the smallest base-10 integer i greater than n, such that both the decimal and binary representations of i are prime (when viewed in decimal).

Input: a number in decimal
Output: The smallest base-10 number greater than n, which when viewed in both binary and decimal, is prime.

Examples:
Input:

• 1
• 3
• 100
• 1234567

Output:

• 3
• 5
• 101
• 1234721

Explanations:

• 3 is prime. 3 in binary is 11, which is also prime. 3 is the smallest number larger than 1 which satisfies these properties.
• 5 is prime. 5 in binary is 101, which is also prime. 5 is the smallest number larger than 3 which satisfies these properties.
• 101 is prime. 101 in binary is 1100101, which is also prime. 101 is the smallest number larger than 100 which satisfies these properties.
• 1234721 is prime. 1234721 in binary is 100101101011100100001, which is also prime. 1234721 is the smallest number larger than 1234567 which satisfies these properties.

Here are your test cases, ordered in ascending difficulty according to my own naive implementation. Please include a Try it online! in your answer:

Input:

• n = 1325584480535587277061226381983816, a.k.a. (((((((1 + 2) * 3) ** 4) + 5) * 6) ** 7) + 8) * 9
• n = 1797010299914431210413179829509605039731475627537851106401, a.k.a ((3^4)^5)^6
• n = 2601281349055093346554910065262730566475782, a.k.a 0^0 + 1^1 + 2^2 + ... + 28^28 + 29^29
• n = 20935051082417771847631371547939998232420940314, a.k.a. 0! + 1! + ... + 38! + 39!
• n = 123456789101112131415161718192021222324252627282930

Output:

• 1325584480535587277061226381986899
• 1797010299914431210413179829509605039731475627537851115949
• 2601281349055093346554910065262730566501899
• 20935051082417771847631371547939998232420981273
• 123456789101112131415161718192021222324252627319639

If you manage to get the correct outputs for these 5 test cases in under 3 seconds total, your code can be considered. This is , the shortest code in bytes wins.

• The input has an upper bound of 10,000, but the code also has to be able to solve a test case 10^53 times larger than that? Does that mean a solution that uses 32-bit integers and perfectly handles inputs less than 10,000 is invalid? Aug 29 '20 at 23:29
• @RyanRudes if it were me, I would just remove the time limit entirely. What is your intention behind the time limit? Aug 29 '20 at 23:35
• @Sisyphus I suppose your right, there are no actual intentions that effect this contest. I'll just remove it. Aug 29 '20 at 23:36
• VTC as duplicate of just about every prime question on the board. Is this number a prime? It's really just testing if two numbers are both prime with a binary conversion in the middle. It's not that interesting and has been overdone on CGCC. Aug 29 '20 at 23:50
• @RyanRudes In case you didn't know, it's preferred that challenge ideas go through the Sandbox first so you can get feedback before they go live. (Don't interpret this as a direct comment on the current challenge; it's just for future reference.) Aug 30 '20 at 0:05

# 05AB1E, 7 bytes

I saw in the comments that you may remove the time limit, so consider this as an answer only in case you are removing the time limit, since it times out even for 1234567.

[ÅNDbp#


Explanation:

[ÅNDbp#
Input is at the top of the stack
[          Infinite loop
ÅN        Next prime
D       Duplicate that
b      Binary representation
p     Is it a prime number?
#    Break the loop if it is, printing the top of the stuck, which is the next number that match both conditions.


Try on online!

# Jelly, 9 bytes

‘ÆnBḌẒ¬Ʋ¿


A monadic Link accepting an integer, n, that yields a list conting just one element, the next prime above n which is prime and has a decimal-read binary representation which is prime.

As a full program the integer is implicitly printed to STDOUT.

Try it online! Or see the test-suite.

### How?

‘ÆnBḌẒ¬Ʋ¿ - Link: n
‘         - increment n -> k=n+1
¿ - while...
Ʋ  - ...condition: last four links as a monad - f(k):
B      -      int to binary list
Ḍ     -      decimal list to int
Ẓ    -      is prime?
¬   -      NOT
Æn       - ...do: (k=) next prime
- yield k


# Wolfram Language (Mathematica), 68 bytes

(t=NextPrime)[#//.x_/;!PrimeQ@FromDigits@IntegerDigits[t@x,2]:>x+1]&


Try it online!

# SageMath, 61 bytes

f=lambda n,p=is_prime:p(n+1)and p(f'{n+1:b}')and n+1or f(n+1)


Try it online!

# Python 3 (145 bytes)

I am the author of this question; this is a non-golfed example if anyone doesn't understand the task. You don't need to upvote this.

from sympy import isprime
for case in range(5):
n = int(input())
i = n + 1
while True:
if isprime(int(bin(i)[2:])) and isprime(i):
print (i)
break
i += 1


It runs in approx. 2.79 seconds on Try on online!

• Runs much faster if one tests the smaller number first, TIO Aug 29 '20 at 23:40
• If it is non-golfed, then it would be better to put it in the question body as a reference instead. Answers should make an attempt at the winning criteria
– Jo King
Aug 30 '20 at 10:20