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
Improve this question
\$\endgroup\$

2 Answers 2

Reset to default
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

Improve this answer
\$\endgroup\$
15
  • \$\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\$ Commented Sep 8, 2017 at 13:34
  • \$\begingroup\$ @JonathanFrech Cool, thanks \$\endgroup\$ Commented Sep 8, 2017 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\$ Commented Sep 8, 2017 at 15:37
  • \$\begingroup\$ Looks good, but the output should contains new lines in it! You are almost done. \$\endgroup\$ Commented Sep 8, 2017 at 15:56
  • \$\begingroup\$ @CyrilGandon done \$\endgroup\$ Commented Sep 8, 2017 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
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Beautiful result, how Jelly succeed to find a prime that fast with 360 digits? \$\endgroup\$ Commented Sep 10, 2017 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\$ Commented Sep 10, 2017 at 9:15

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.