17
\$\begingroup\$

What is a Prime Square?

A Prime Square is a square where all four edges are different prime numbers.
But which ones?
And how do we construct them?

Here is an example of a 4x4 Prime Square

1009  
0  0     
3  0   
1021    

First we start from the upper left corner. We are working clockwise.
We pick the smallest prime number having 4 digits which is 1009.

Then we need the smallest prime number having 4 digits, which starts with a 9. This is 9001

The third (4-digits) prime number must have 1 as its last digit (because 9001 ends with 1)
and also be the smallest 4-digit prime with this property that has not been used before as an edge.
This prime number is 1021

The fourth prime number must have 4 digits, start with a 1 (because 1009 starts with a 1) and end with a 1 (because 1021 starts with a 1)
The smallest 4-digit prime number with this property that has not been used before as an edge is 1031

Your TASK

You will be given an integer n from 3 to 100
This number will be the dimensions of the n x n square
Then you must output this square exactly in the form of the following test cases

Test Cases

n=3  
Output    

101
3 0
113     

n=5    
Output     

10007
0   0
0   0    
9   0    
10061     

n=7     
Output    

1000003    
0     0     
0     0     
0     0     
0     0     
8     1     
1000037      

n=10      
Output     

1000000007      
0        0      
0        0     
0        0      
0        0       
0        0       
0        0      
1        0      
8        0       
1000000021      

n=20       
Output     

10000000000000000051     
0                  0          
0                  0           
0                  0           
0                  0          
0                  0           
0                  0          
0                  0           
0                  0           
0                  0          
0                  0          
0                  0          
0                  0           
0                  0           
0                  0          
0                  0            
0                  0          
0                  0              
9                  8      
10000000000000000097
  • Input and output can be given by any convenient method.
  • You can print it to STDOUT or return it as a function result.
  • Either a full program or a function are acceptable.
  • Any amount of extraneous whitespace is acceptable, so long as the numbers line up appropriately
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

EDIT
This is possible for all n
Here are the primes for n=100

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000289        
9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000091            
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000711             
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002191     



And for those of you that you don't think this is possible here are ALL the test cases

\$\endgroup\$
  • \$\begingroup\$ If n can go up to 100, it might be good to have some larger test cases than n = 10. \$\endgroup\$ – gastropner May 1 at 20:25
  • 4
    \$\begingroup\$ Is it provable that this is possible for all n :P? Not a problem with the challenge, just curious. \$\endgroup\$ – Magic Octopus Urn May 1 at 20:26
  • 2
    \$\begingroup\$ @MagicOctopusUrn It is definitely not possible for all n: for n=1, we cannot satisfy the constraint that the four edges are different primes, while for n=2, we are forced to choose 11,13,23, at which point the final edge is 12 which is composite. I don't have a proof that it is possible for all n>2, but would be shocked to learn otherwise: informally, the more digits there are, the more "wiggle room" there is to satisfy the constraints. \$\endgroup\$ – Daniel Wagner May 2 at 0:47
  • \$\begingroup\$ @DanielWagner Many upper bounds on the ratio between \$p_{k+1}\$ and \$p_k\$ have been proved over the years, improving Bertrand's postulate by a significant margin. The formula given here for \$k\ge463\$ should be enough to prove that this holds for \$n\ge4\$. \$\endgroup\$ – Arnauld May 2 at 1:21
  • 2
    \$\begingroup\$ @MagicOctopusUrn The prime number theorem for arithmetic progressions says something fairly strong about the density of primes ending in 1, 3, 7, and 9 (in the notation there, take n=10, a=1/3/7/9); for sufficiently large n there are at least two primes of length n starting with 1 and ending with each of those digits (hence we can choose a bottom edge) and there are at least three primes starting with 1 and ending with 1 (hence we can choose a left edge). \$\endgroup\$ – Daniel Wagner May 2 at 2:25
4
\$\begingroup\$

05AB1E, 64 63 56 53 48 46 bytes

°ÅPIùćÐ4FˆθUKD.ΔθyXÅ?yXÅ¿)¯gè}ÐNĀiR}¦}I¯JŽ9¦SΛ

-1 byte thanks to @Mr.Xcoder
-5 bytes thanks to @Grimy.

Try it online. (Times out for \$n>4\$. Here the slightly faster 53 bytes version which times out for \$n>7\$ instead.)

Explanation:

°                 # Raise the (implicit) input to the power 10
 ÅP               # Get a list of primes within the range [2, n^10]
   Iù             # Only keep those of a length equal to the input
ć                 # Extract the head; push the remainder-list and first prime separately
 Ð                # Triplicate this first prime
4F                # Loop 4 times:
  ˆ               #  Add the (modified) prime at the top of the stack to the global array
  θU              #  Pop and store the last digit of the prime in variable `X`
  K               #  Remove this prime from the prime-list
  D               #  Duplicate the prime-list
   .Δ             #  Find the first prime `y` in the prime list which is truthy for:
     θ            #   Get the last digit of prime `y`
     yXÅ?         #   Check if prime `y` starts with variable `X`
     yXÅ¿         #   Check if prime `y` ends with variable `X`
     )            #   Wrap the three results above into a list
      ¯g          #   Get the amount of items in the global array
        è         #   And use it to index into these three checks
                  #   (Note that only 1 is truthy for 05AB1E, so the `θ` basically checks
                  #    if the last digit of prime `y` is 1)
    }Ð            #  Triplicate the found prime
      NĀi }       #  If the loop index is 1, 2, or 3:
         R        #   Reverse the found prime
      ¦           #  And then remove the first digit of the (potentially reversed) prime
}                 # After the loop:
 I                # Push the input as length
 ¯J               # Push the global array joined together to a single string
 Ž9¦S             # Push compressed integer 2460 converted to a list of digits: [2,4,6,0]
 Λ                # Draw the joined string in the directions [2,4,6,0] (aka [→,↓,←,↑])
                  # of a length equal to the input
                  # (which is output immediately and implicitly as result)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ž9¦ is 2460. And see this 05AB1E tip of mine to understand how the square is output with the Λ Canvas builtin.

The relevant code for printing the Canvas in a square is: NĀiR}¦ and I¯JŽ9¦SΛ. Let's take n=4 as example. The primes it will find with the rest of the code are [1009,9001,1021,1031]. The first code-part mentioned in this paragraph will save them as this instead: [1009,"001","201","301"]. The second code part of this paragraph will then use the Canvas builtin Λ with options:
- \$a\$ (side-length) = I: the input
- \$b\$ (string to print) = ¯J: the global array joined together (so "1009001201301" for n=4)
- \$c\$ (direction) = Ž9¦S: the directions [2,4,6,0], which will be [→,↓,←,↑] respectively

\$\endgroup\$
  • 1
    \$\begingroup\$ 50: 4F°ÅP¯KIù.Δ1sЮθÅ¿Š®θÅ?Šθ)¯gè}©ˆ}ð¯2ô`€R«€¦J«Ž9¦SΛ 49: °ÅPIùć4FÐN1›iR}¦ˆθUKD.ΔÐθsXÅ?‚sXÅ¿ª¯gè]Ið¯J«Ž9¦SΛ 48: °ÅPIùćÐ4FˆθUKD.ΔÐθsXÅ?‚sXÅ¿ª¯gè}ÐNĀiR}¦}I¯JŽ9¦SΛ \$\endgroup\$ – Grimmy May 2 at 16:41
  • \$\begingroup\$ @Grimy Thanks! Very nice golfs. I've been able to save 2 more bytes based on your 48-byte version by changing ÐθsXÅ?‚sXÅ¿ª to θyXÅ?yXÅ¿). Not exactly sure why ) works within the scope of the loop though, since I would have expected it to wrap the prime-list also into its list in the first iteration. But even without that, the use of yy instead of Ðss still saves 1 byte. :) \$\endgroup\$ – Kevin Cruijssen May 3 at 7:22
4
\$\begingroup\$

05AB1E, 35 33 32 31 bytes

-1 byte thanks to Kevin Cruijssen

°ÅPIùΔÐXθÅ?Ïн©KX®¦«UNií]IXŽ9¦SΛ

Try it online!

Explanation:

°                 # 10 to the power of the input
 ÅP               # list of primes up to that
   Iù             # keep only those with the same length as the input

Δ                 # repeat until the list doesn't change
# This ends up doing a ton of unneeded work. 4F (to loop 4 times) would be
# enough, but Δ is shorter and the extra iterations don’t cause issues.
# At the start of each iteration, the stack only contains the list of primes,
# and the variable X contains the current list of digits we’ll want to print.
# Conveniently, X defaults to 1, which is our first digit.

 Ð    Ï           # push a filtered copy of the list, keeping only…
    Å?            # numbers that start with…
  Xθ              # the last character of X
       н          # get the first element: this is our next prime

 ©                # save this number to the register
  K               # remove it from the list of candidate primes
   X              # push X
    ®             # restore the number from the register
     ¦            # remove its first character
      «           # concatenate it to X
       U          # save the result to X

 Ni               # if N == 1 (second time through the loop)
   í              # reverse all elements in the list of candidate primes
    ]             # closes both this if and the main loop

      Λ           # Draw on a canvas…
I                 # using the input as length…
 X                # using X as the string to draw…
  Ž9¦S            # using [2,4,6,0] (aka [→,↓,←,↑]) as the directions to draw in
\$\endgroup\$
  • \$\begingroup\$ This is partially based on Kevin’s answer, but at this point it’s different enough that I felt it deserved its own answer rather than a comment. \$\endgroup\$ – Grimmy May 2 at 20:28
  • 1
    \$\begingroup\$ I only now see this answer. Very nice! Apart from the general method (and therefore the first and last parts), determining the four primes and building the string is done so differently that I can understand the separated answer. +1 from me. Btw, you can save a byte removing the Θ at . Only 1 is truthy in 05AB1E, so if N and if N == 1 are the same. \$\endgroup\$ – Kevin Cruijssen May 10 at 7:25
  • 1
    \$\begingroup\$ @KevinCruijssen Thanks! Of course I knew that, but I forgot to use it. In retrospect, Θi is the 05AB1E equivalent of if (cond == true)... \$\endgroup\$ – Grimmy May 10 at 10:35
  • \$\begingroup\$ Yep, that's right. :) Θ can still be useful if you want to convert everything except 1 to 0. But for the if-statement i, it's not really necessary just like your pseudocode with == true. \$\endgroup\$ – Kevin Cruijssen May 10 at 11:07
2
\$\begingroup\$

JavaScript (ES8),  205 ... 185 177  173 bytes

Times out on TIO for \$n>8\$ because of the very inefficient primality test.

n=>([a,b,c]=[0,-1,--n,0].map(p=o=i=>o[(g=n=>{for(k=n++;n%k--;);k|o[n]|p[i]-n%10?g(n):p=n+''})((~i?1:p%10)*10**n)|p]=p),[...p].map((d,i)=>i?i<n?d.padEnd(n)+b[i]:c:a).join`
`)

Try it online!

How?

Step #1: computing the 4 primes

[a, b, c] =               // save the 3 first primes into a, b and c
                          // (the 4th prime will be saved in p)
  [ 0, -1, --n, 0 ]       // decrement n and iterate over [ 0, -1, n, 0 ]
  .map(p =                // initialize p (previous prime) to a non-numeric value
       o =                // use o as a lookup table
  i =>                    // for each value i in the list defined above:
    o[                    //   update o:
      (g = n => {         //     g = recursive function taking n
        for(k = n++;      //       set k = n and increment n
            n % k--;);    //       decrement k until it's a divisor of n
                          //       (notice that k is decremented *after* the test)
        k |               //       if k is not equal to 0 (i.e. n is not prime)
        o[n] |            //       or n was already used
        p[i] - n % 10 ?   //       or the last digit of n does not match the connected
                          //       digit (if any) with the previous prime:
          g(n)            //         do a recursive call
        :                 //       else:
          p = n + ''      //         stop recursion and save n coerced to a string into p
      })(                 //     initial call to g with:
        (~i ? 1 : p % 10) //       either 10 ** n if i is not equal to -1
        * 10 ** n         //       or (p % 10) * 10 ** n if i = -1
      ) | p               //     yield p
    ] = p                 //   set o[p] = p
  )                       // end of map()

Step #2: formatting the output

[...p].map((d, i) =>      // for each digit d at position i in the last prime:
  i ?                     //   if this is not the first digit:
    i < n ?               //     if this is not the last digit:
      d.padEnd(n)         //       append d, followed by n - 1 spaces
      + b[i]              //       append the corresponding digit in the 2nd prime
    :                     //     else (last digit):
      c                   //       append the 3rd prime
  :                       //   else (first digit):
    a                     //     append the first prime
).join`\n`                // end of map(); join with carriage returns
\$\endgroup\$
2
\$\begingroup\$

Jelly, 89 82 bytes

1ịÆn⁺f®$¿
’⁵*;Æn$©µDṪṪ×ḢÇ©;@©µ;Ç⁺;0ị®¤%⁵n/Ɗ¿$$©;Ç⁺%⁵’$¿$$µŒœṪDZUḊṖj€⁶x³¤ḊḊ¤;@Ḣ;2ị$

Try it online!

Could definitely be golfier, but works efficiently for big numbers.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 59 bytes

DṪṪ=DZḢṪṪ3ƭƊ}Tịḟ@Ḣ
’;⁸⁵*æR/µḢ;ç¥⁺⁺µŒœṪDZUḊṖj€⁶x³¤ḊḊ¤;@Ḣ;2ị$

Try it online!

Shorter but much less efficient Jelly answer.

\$\endgroup\$
1
\$\begingroup\$

JavaScript, 484 bytes

i=a=>a?(l=a=>a[(L=a=>a.length-1)(a)])(a)==9?i(r(a))+0:(r=a=>a.substr(0,L(a)))(a)+(+l(a)+1)%10:"1";s=(a,b)=>b?a==b?"":s(l(a)<l(b)?s(r(a),1):r(a),r(b))+Math.abs(l(a)-l(b)):a;m=(a,b)=>!a||!((c=L(a)-L(b))<0||!c&&a<b)&&m(s(a,b),b);p=(a,b="2")=>a/2<b||!(m(a,b)||!p(a,i(b)));a=>{for(M=1+(R=a=>"0".repeat(b))(z=a-1);!p(M=i(M)););for(N=M[z]+R(z);!p(N=i(N)););for(O=1+R(x=a-2);!p(O+n[z]);O=i(O));for(P=R(x);!p(m[0]+P+O[0]);P=i(P));for(S="\n",j=0;j<x;)S+=P[i]+R(x)+N[++i]+"\n";return M+S+O+N[z]}

The last unnamed function returns the ASCII art.

Original code

function inc(a){
  if (!a) return "1";
  if (a[a.length-1]=="9") return inc(a.substr(0,a.length-1))+"0";
  return a.substr(0,a.length-1)+(+a[a.length-1]+1)%10;
}
function sub(a,b){
  if (!b) return a;
  if (a==b) return "";
  var v=a.substr(0,a.length-1);
  if (a[a.length-1]<b[b.length-1]) v=sub(v,1);
  return sub(v,b.substr(0,b.length-1))+Math.abs(a[a.length-1]-b[b.length-1])
}
function multof(a,b){
  if (!a) return true;
  if (a.length<b.length||a.length==b.length&&a<b) return false;
  return multof(sub(a,b),b);
}
function isprime(a){
  for (var i="2";a/2>i;i=inc(i)){
    if (multof(a,i)) return false;
  }
  return true;
}
function square(a){
  for (var m="1"+"0".repeat(a-1);!isprime(m);m=inc(m)){}
  for (var n=m[a-1]+"0".repeat(a-1);!isprime(n);n=inc(n)){}
  for (var o="1"+"0".repeat(a-2);!isprime(o+n[a-1]);o=inc(o)){}
  for (var p="0".repeat(a-2);!isprime(m[0]+p+o[0]);p=inc(p)){}
  var s="";
  for (var i=0;i<a-2;i++) s+=p[i]+"0".repeat(a-2)+n[i+1]+"\n";
  return m+"\n"+s+o+n[a-1];
}

Best and average time complexity: Ω(100nn) in Knuth's big-omega notation(n steps for subtracting n digit numbers, 10n substractions per divisibility check, 10n divisibility check for prime check, and Ω(1) prime checks done).

Worst time complexity: Ω(1000nn) in Knuth's big-omega notation(n steps for subtracting n digit numbers, 10n substractions per divisibility check, 10n divisibility check for prime check, and 10n prime checks done).

I suspect n=100 takes around 10203 calculations.

Sidenote: I validated syntax using UglifyJS 3, and it golfed it way better than I did, saving 47.13% more and earning 282 bytes. However, I decided not to make that my score since I feel like it is cheating.

i=(s=>s?9==(l=(l=>l[(L=(l=>l.length-1))(l)]))(s)?i(r(s))+0:(r=(l=>l.substr(0,L(l))))(s)+(+l(s)+1)%10:"1"),s=((L,i)=>i?L==i?"":s(l(L)<l(i)?s(r(L),1):r(L),r(i))+Math.abs(l(L)-l(i)):L),m=((l,r)=>!l||!((c=L(l)-L(r))<0||!c&&l<r)&&m(s(l,r),r)),p=((l,s="2")=>l/2<s||!(m(l,s)||!p(l,i(s))));

It just deleted the last function since they are never used. It actually became worse if it was assigned and not deleted, imcluding the additional code I added.

\$\endgroup\$
  • 3
    \$\begingroup\$ This seems incomplete? And not golfed? \$\endgroup\$ – connectyourcharger May 1 at 21:41
  • \$\begingroup\$ Yes. Completed/golfed. \$\endgroup\$ – Naruyoko May 1 at 23:16

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.