# Build the Trinity Hall Prime

Based on this challenge and this Math.SE question. Idea originally come from a Numberphile video. The goal is to reproduce the logic of Professor McKee when he builds this prime.

Your task is to build the Trinity Hall Prime, at a much lower scale. You are given a single number N greater than 2, representing the length of the prime we need.

# Rules

• N is decomposed into a rectangle W(idth) x H(eight). W and H must be close, so 12 is 4x3 and 16 is 4x4 with W >= H
• The first line got only 8's
• The next lines have 8's in the outer and 1's in the middle
• Each lines have 2 more 1's and 2 less 8's than the previous, except if W is odd, then the second line have only one 1 in the middle
• Once you got your emblem, find the first prime greater than the emblem.
• 2 <= N <= 16
• This is , so newlines must be part of the output.
• This is , so shortest code, in bytes, wins.

# Test cases:

I   Emblem    O
================
2   88        89

3   888       907

4   88        88
11        19

6   888       888
818       827

8   8888      8888
8118      8133

9   888       888
818       818
111       159

10  88888     88888
88188     88213

16  8888      8888
8118      8118
1111      1111
1111      1159


# Python 3, 194 bytes

n=int(input())
R=range
w=n//max(i*(i*i<=n>1>n%i)for i in R(1,n))
m=0
for i in R(n):m=m*10+1+7*(abs(i%w*2-w+1)//2*w>i-w)
while any(m%p<1for p in R(2,m)):m+=1
m=str(m)
while m:print(m[:w]);m=m[w:]


Try it online!

too slow for most inputs, especially x > 8

-6 bytes thanks to Jonathan Frech
-98 bytes thanks to Leaky Nun

• You can save two bytes by defining j="".join (adding 9+1 bytes) and replacing ''.join with j (saving 6*2 bytes; 10-12 = -2). Sep 8, 2017 at 13:34
• @JonathanFrech Cool, thanks Sep 8, 2017 at 13:38
• Also, as the input is always one integer, you can replace eval with int to save one entire byte. Using Python 2, one could entirely remove eval() (6 bytes) and the print parentheses (1 byte) to save 7 bytes. Sep 8, 2017 at 15:37
• Looks good, but the output should contains new lines in it! You are almost done. Sep 8, 2017 at 15:56
• @CyrilGandon done Sep 8, 2017 at 16:54

# Jelly,  57  56 bytes

ŒgṖḊ$€2¦j8 Æd:2‘ịÆDðL€©8,8jÇÐĿḊ€ḣ€⁸Ṛ;®ẋ€⁸¤ḣ:@ðFḌÆnDṁ⁸Gḟ⁶  A monadic link taking a number and returning a list of characters. As a full program it prints the result. Try it online! ### How? ŒgṖḊ$€2¦j8 - Link 1, previous 8-padded-row builder: list current 8-padded-row
-                                         e.g. [8,8 , 1,1,1 , 8,8]
Œg         - group runs of equal elements                [[8,8],[1,1,1],[8,8]]
¦   - sparse application:
2    - ...to indices: 2
Ṗ        -   pop                                       [[8,8],[1,1  ],[8,8]]
Ḋ       -   dequeue                                   [[8,8],[  1  ],[8,8]]
j8 - join with eights                             [8,8, 8, 1, 8, 8,8]
-   (note: from ...818... this yields an extra 8 - dealt with by ḣ€ in Main)

Æd:2‘ịÆDð... - Main link: number, N
Æd           - divisor count of N
:2         - integer divided by 2
‘        - increment
ÆD     - divisors of N
ị       - index into (yields W)
ð    - start a new dyadic chain with W on the left and N on the right...

L€                            - length of €ach of implicit range(W) = list of W 1s
©                           - (copy to register for later reuse)
8,8                        - literal [8,8]
j                       - join -> [8,1,1,...,1,8] with W 1s
ÐĿ                    - collect inputs until fixed point:
Ḋ€                  - dequeue €ach (remove the leading 8 from each)
⁸               - chain's right argument, N
ḣ€                - head €ach to index (remove the trailing 8(s))
Ṛ              - reverse
®            -   recall the [1,1,...W times...,1] from the register
⁸         -   chain's left argument, W
ẋ€          -   repeat €ach (making W more rows of W 1s)
;             - concatenate
:@     - integer division (sw@p arguments) = N:W = H
ḣ       - head to index (gets the first H rows - the mask, M)
ð    - start a new dyadic chain with arguments M, N

...FḌÆnDṁ⁸Gḟ⁶ - Main link (continued): M, N
F          - flatten M
Ḍ         - from decimal list to number
Æn       - next prime
D      - to decimal list
⁸    - chain's left argument, M
ṁ     - mould like (reshape like the mask)
G   - format as a grid (all digits to characters, add spaces and newlines)
⁶ - literal space character
ḟ  - filter discard (Gḟ⁶ instead of Y as single row results are possible)
- as a full program: implicit print

• Beautiful result, how Jelly succeed to find a prime that fast with 360 digits? Sep 10, 2017 at 8:40
• Jelly uses sympy's nextprime, which in turn makes use of its isprime which, for numbers greater than 2^64, uses BPSW - while this is a probabilistic test no composite false-positives are known. Note that it takes a lot longer if one tries 1350 (times out on TIO). Sep 10, 2017 at 9:15