6
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – Jonathan Frech Sep 8 '17 at 13:34
  • \$\begingroup\$ @JonathanFrech Cool, thanks \$\endgroup\$ – HyperNeutrino Sep 8 '17 at 13:38
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonathan Frech Sep 8 '17 at 15:37
  • \$\begingroup\$ Looks good, but the output should contains new lines in it! You are almost done. \$\endgroup\$ – Cyril Gandon Sep 8 '17 at 15:56
  • \$\begingroup\$ @CyrilGandon done \$\endgroup\$ – HyperNeutrino Sep 8 '17 at 16:54
2
\$\begingroup\$

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
    $€     - ...do: last two links as a monad for €ach:
  Ṗ        -   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€©8,8jÇÐĿḊ€ḣ€⁸Ṛ;®ẋ€⁸¤ḣ:@ð... - Main link (continued): W, N
   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:
          Ç                      -   call the last link (1) as a monad
             Ḋ€                  - dequeue €ach (remove the leading 8 from each)
                 ⁸               - chain's right argument, N
               ḣ€                - head €ach to index (remove the trailing 8(s))
                  Ṛ              - reverse
                        ¤        - nilad followed by link(s) as a nilad:
                    ®            -   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
\$\endgroup\$
  • \$\begingroup\$ Beautiful result, how Jelly succeed to find a prime that fast with 360 digits? \$\endgroup\$ – Cyril Gandon Sep 10 '17 at 8:40
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Jonathan Allan Sep 10 '17 at 9:15

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.