12
\$\begingroup\$

Output a sequence of all the primes that are of the following form: 123...91011...(n-1)n(n-1)..11109...321. That is, ascending decimal numbers up to some n, followed by a descending tail, all concatenated.

Background

Recently, Numberphile posted a video about primes that follow this pattern.

Output

1 -> 12345678910987654321 (n=10)
2 -> 123...244524462445...321 (n=2446)

No more terms are known, but it's likely that there are infinitely many.

\$\endgroup\$
3
  • \$\begingroup\$ In other words, the subsequnce of A173426 filtered by primality. \$\endgroup\$ Dec 19 '21 at 12:34
  • \$\begingroup\$ Two questions: 1. Is the output format flexible? 2. Is a probabilistic primality test ok, or is a deterministic test required? \$\endgroup\$ Dec 23 '21 at 0:31
  • \$\begingroup\$ @cubiclettuce Use standard sequence output formats (click the tag for more info). I'd say that a deterministic test is required. \$\endgroup\$
    – AnttiP
    Dec 24 '21 at 9:07
11
\$\begingroup\$

05AB1E, 7 bytes

∞η€ûJʒp

Try it online! Times out on TIO without printing a single number because the primality test is too slow. Takes 77 seconds locally for the first number and will never† get to the second number.

∞η       Prefixes of [1, 2, 3, ...]
  €û     Palindromize each prefix
    J    Join each into a number
     ʒp  Filter: keep primes

Local output:

05AB1E git:master ❯ ./osabie programs/mwp.abe
["12345678910987654321"

† in the lifetime of the universe, the test is \$\mathcal{O(\sqrt{n} \log{}n})\$.

\$\endgroup\$
7
\$\begingroup\$

Jelly, 8 bytes

ŒḄV©ẒƊ#®

Try it online!

By default sequence I/O rules, this inputs a value k and outputs the prime corresponding to k.

This is a monadic link f(k) that returns the prime. It also outputs the n value for that prime as a side effect - this should be considered a function that returns the prime. I've included a 9 byte version that doesn't output anything extra below.

ŒḄV©ẒƊ#ṛ®

Try it online!


Both can handle \$k = 1\$ on TIO, can't handle \$k = 2\$ or above.

How they work

ŒḄV©ẒƊ#® - Main link. Takes k on the left
     Ɗ#  - Find the first n such that the following is true:
ŒḄ       -   Bounced range of n; [1, 2, ..., n, ..., 2, 1]
  V      -   Evaluated as an integer: 12...n...21
   ©     -   Save this in the register
    Ẓ    -   Is this prime?
       ® - Print n and return the register

The second uses ṛ® instead of ®. The causes the program to discard the value of n rather than printing it, and then ® returns the register.

\$\endgroup\$
0
\$\begingroup\$

Python 3, 213 bytes

def A(n):return int(''.join(str(d)for d in range(1,n+1))+''.join(str(d)for d in range(n-1,0,-1)))
i=5
w=0
y=int(input())
while 1:
	p=n=1;exec("p*=n*n;n+=1;"*~-A(i))
	if p%n==1:w+=1
	if w==y:print(A(i));break
	i+=1

Try it online!

Probably should be correct. If you find bugs then comment the answer.

Upvote Lynn solution of prime checking!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I may be misunderstanding something, but where is i updated? It seems that we will always print A(5)... \$\endgroup\$
    – pajonk
    Dec 18 '21 at 20:22
  • \$\begingroup\$ no, infinite loop because the i don't increment. \$\endgroup\$
    – Fmbalbuena
    Dec 18 '21 at 21:50
0
\$\begingroup\$

Here I used the Miller-Rabin Primality Test to approximate if the number is in fact prime.

import math
import random

def miller_rabin(n, k):

    # Implementation uses the Miller-Rabin Primality Test
    # The optimal number of rounds for this test is 40
    # See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
    # for justification

    # If number is even, it's a composite number

    if n == 2 or n == 3:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            print(_)
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def constructNumber(n):
    numberArray = []
    for i in range(n):
        numberArray.append(str(i+1))
    for i in range(n-1):
        numberArray.append(str((n-1)-i))
    return int(''.join(numberArray))

if __name__ == "__main__":
    print(miller_rabin((constructNumber(10)),40))

Miller-Rabin Python Source

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Welcome to Code Golf! This site is for competitive programming, so we require answers to make a serious attempt at golfing. Make sure to read our tips questions if you want some hints! Also, since this only seems to approximate whether a number is prime, it's wouldn't be valid (it's cool though!). \$\endgroup\$ Dec 21 '21 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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