-3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – water_ghosts Aug 29 at 23:29
  • 5
    \$\begingroup\$ @RyanRudes if it were me, I would just remove the time limit entirely. What is your intention behind the time limit? \$\endgroup\$ – Sisyphus Aug 29 at 23:35
  • 3
    \$\begingroup\$ @Sisyphus I suppose your right, there are no actual intentions that effect this contest. I'll just remove it. \$\endgroup\$ – Ryan Rudes Aug 29 at 23:36
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ – Xcali Aug 29 at 23:50
  • 1
    \$\begingroup\$ @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.) \$\endgroup\$ – Dingus Aug 30 at 0:05
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 68 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
-1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Runs much faster if one tests the smaller number first, TIO \$\endgroup\$ – Jonathan Allan Aug 29 at 23:40
  • 4
    \$\begingroup\$ 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 \$\endgroup\$ – Jo King Aug 30 at 10:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.