Faites des carrés principaux!

17

Qu'est-ce qu'un Prime Square?

Un carré premier est un carré où les quatre arêtes sont des nombres premiers différents.
Mais lesquels?
Et comment les construisons-nous?

Voici un exemple d'un Prime Square 4x4

1009  
0  0     
3  0   
1021    

Nous commençons d'abord par le coin supérieur gauche. Nous travaillons dans le sens horaire .
Nous choisissons le plus petit nombre premier ayant des 4chiffres qui est 1009 .

Ensuite, nous avons besoin du plus petit nombre premier ayant des 4chiffres, qui commence par a 9. C'est 9001

Le troisième nombre premier (4 chiffres) doit avoir 1comme dernier chiffre (car 9001 se termine par 1)
et doit également être le plus petit nombre premier à 4 chiffres avec cette propriété qui n'a pas été utilisée auparavant comme bord .
Ce nombre premier est 1021

Le quatrième nombre premier doit avoir des 4chiffres, commencer par un 1(car 1009 commence par a 1) et se terminer par un 1(car 1021 commence par a 1)
Le plus petit nombre premier à 4 chiffres avec cette propriété qui n'a pas été utilisé auparavant comme bord est 1031

Ta tâche

Vous recevrez un entier à npartir de 3 to 100
Ce nombre sera les dimensions du n x ncarré
Ensuite, vous devez sortir ce carré exactement sous la forme des cas de test suivants

Cas de test

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
  • L'entrée et la sortie peuvent être fournies par n'importe quelle méthode pratique .
  • Vous pouvez l'imprimer sur STDOUT ou le renvoyer en tant que résultat de fonction.
  • Un programme complet ou une fonction sont acceptables.
  • N'importe quelle quantité d'espace blanc étranger est acceptable, tant que les chiffres sont alignés de manière appropriée
  • Les failles standard sont interdites.
  • Il s'agit de donc toutes les règles de golf habituelles s'appliquent et le code le plus court (en octets) l'emporte.

EDIT
Ceci est possible pour tous n
Voici les nombres premiers pourn=100

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000289        
9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000091            
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000711             
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002191     



Et pour ceux d'entre vous que vous ne pensez pas que ce soit possible, voici TOUS les cas de test

J42161217
la source
Si n peut aller jusqu'à 100, il pourrait être bon d'avoir des cas de test plus grands que n = 10.
gastropner
4
Est-il prouvable que cela est possible pour tous n: P? Pas un problème avec le défi, juste curieux.
Urne de poulpe magique
2
@MagicOctopusUrn Ce n'est certainement pas possible pour tous n: pour n= 1, nous ne pouvons pas satisfaire la contrainte que les quatre arêtes sont des nombres premiers différents, tandis que pourn = 2, nous sommes obligés de choisir 11,13,23, à quel point l'arête finale est 12 qui est composite. Je n'ai pas de preuve qu'il est possible pour tous n> 2, mais je serais choqué d'apprendre autrement: informellement, plus il y a de chiffres, plus il y a de "marge de manœuvre" pour satisfaire les contraintes.
Daniel Wagner
pk+1pkk463n4
2
@MagicOctopusUrn Le théorème des nombres premiers pour les progressions arithmétiques dit quelque chose d'assez fort sur la densité des nombres premiers se terminant par 1, 3, 7 et 9 (dans la notation, prenez n = 10, a = 1/3/7/9 ); pour suffisamment grandn il y a au moins deux nombres premiers ncommençant par 1 et se terminant par chacun de ces chiffres (nous pouvons donc choisir un bord inférieur) et il y a au moins trois nombres premiers commençant par 1 et se terminant par 1 (nous pouvons donc choisir un Bord gauche).
Daniel Wagner

Réponses:

4

05AB1E , 64 63 56 53 48 46 octets

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

-1 octet grâce à @ Mr.Xcoder
-5 octets grâce à @Grimy .

n>4n>sept

Explication:

°                 # 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)

Voir cette astuce de mes 05AB1E (section Comment compresser les grands entiers? ) Pour comprendre pourquoi Ž9¦est 2460. Et consultez cette astuce 05AB1E pour comprendre comment le carré est Λsorti avec le canevas intégré.

NĀiR}¦I¯JŽ9¦SΛn=4[1009,9001,1021,1031][1009,"001","201","301"]Λ
uneI
b¯J"1009001201301"n=4
cŽ9¦S[2,4,6,0][→,↓,←,↑]

Kevin Cruijssen
la source
1
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Λ
Grimmy
@Grimy Merci! Très beaux golfs. J'ai pu enregistrer 2 octets supplémentaires en fonction de votre version de 48 octets en passant ÐθsXÅ?‚sXÅ¿ªà θyXÅ?yXÅ¿). Je ne sais pas exactement pourquoi )fonctionne dans le cadre de la boucle, car je m'attendais à ce qu'il encapsule également la liste principale dans sa liste lors de la première itération. Mais même sans cela, l'utilisation de yyau lieu de Ðsssauve toujours 1 octet. :)
Kevin Cruijssen
4

05AB1E , 35 33 32 31 octets

-1 octet grâce à Kevin Cruijssen

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

Essayez-le en ligne!

Explication:

°                 # 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
Grimmy
la source
Ceci est partiellement basé sur la réponse de Kevin , mais à ce stade, il est suffisamment différent pour que je pense qu'il méritait sa propre réponse plutôt qu'un commentaire.
Grimmy
1
Je vois seulement maintenant cette réponse. Très agréable! En dehors de la méthode générale (et donc des première et dernière parties), la détermination des quatre nombres premiers et la construction de la chaîne se font si différemment que je peux comprendre la réponse séparée. +1 de moi. Btw, vous pouvez enregistrer un octet en supprimant le Θat . Seul 1est vrai en 05AB1E, donc if Net if N == 1sont les mêmes.
Kevin Cruijssen
1
@KevinCruijssen Merci! Bien sûr, je le savais, mais j'ai oublié de l'utiliser. Rétrospectivement, Θiest l'équivalent 05AB1E de if (cond == true)...
Grimmy
Oui, c'est vrai. :) Θpeut toujours être utile si vous voulez tout convertir sauf 1en 0. Mais pour l'instruction if i, ce n'est pas vraiment nécessaire, tout comme votre pseudocode avec == true.
Kevin Cruijssen
2

JavaScript (ES8),  205 ...  185177173 octets

n>8

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`
`)

Essayez-le en ligne!

Comment?

Étape # 1: calcul des 4 nombres premiers

[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()

Étape # 2: formatage de la sortie

[...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
Arnauld
la source
2

Gelée , 89 82 octets

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

Essayez-le en ligne!

Pourrait certainement être golfeur, mais fonctionne efficacement pour les grands nombres.

Nick Kennedy
la source
2

Gelée , 59 octets

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

Essayez-le en ligne!

Réponse de Jelly plus courte mais beaucoup moins efficace.

Nick Kennedy
la source
1

JavaScript, 484 octets

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]}

La dernière fonction sans nom renvoie l'art ASCII.

Code d'origine

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];
}

Complexité temporelle optimale et moyenne: Ω (100 n n) dans la notation des grands oméga de Knuth (n étapes pour soustraire n nombres de chiffres, 10 n soustractions par contrôle de divisibilité, 10 n contrôle de divisibilité pour contrôle principal et Ω (1) contrôles principaux effectués ).

Pire complexité du temps: Ω (1000 n n) dans la notation des grands oméga de Knuth (n étapes pour soustraire n nombres numériques, 10 n soustractions par contrôle de divisibilité, 10 n contrôle de divisibilité pour contrôle principal et 10 n contrôles principaux effectués).

Je suppose que cela n=100prend environ 10 203 calculs.

Sidenote: J'ai validé la syntaxe en utilisant UglifyJS 3, et il a joué beaucoup mieux que moi, économisant 47,13% de plus et gagnant 282 octets. Cependant, j'ai décidé de ne pas en faire mon score car j'ai l'impression que c'est de la triche.

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))));

Il vient de supprimer la dernière fonction car elles ne sont jamais utilisées. En fait, cela a empiré s'il était attribué et non supprimé, à l'exclusion du code supplémentaire que j'ai ajouté.

Naruyoko
la source
3
Cela semble incomplet? Et pas joué au golf?
connectyourcharger
Oui. Terminé / golfé.
Naruyoko