Zrób kilka najlepszych kwadratów!

17

Co to jest Prime Square?

Prime Square to kwadrat, w którym wszystkie cztery krawędzie mają różne liczby pierwsze.
Ale które?
A jak je konstruujemy?

Oto przykład 4x4 Prime Square

1009  
0  0     
3  0   
1021    

Najpierw zaczynamy od lewego górnego rogu. Pracujemy zgodnie z ruchem wskazówek zegara .
Wybieramy najmniejszą liczbę pierwszą zawierającą 4cyfry, czyli 1009 .

Następnie potrzebujemy najmniejszej liczby pierwszej mającej 4cyfry, która zaczyna się od a 9. To jest 9001

Trzecia (4-cyfrowa) liczba pierwsza musi mieć 1ostatnią cyfrę (ponieważ 9001 kończy się na 1),
a także być najmniejszą 4-cyfrową liczbą pierwszą z tą właściwością, która nie była wcześniej używana jako zbocze .
Ta liczba pierwsza to 1021

Czwarta liczba pierwsza musi zawierać 4cyfry, zaczyna się od 1(ponieważ 1009 zaczyna się od a 1) i kończy się na 1(ponieważ 1021 zaczyna się od a 1)
Najmniejsza 4-cyfrowa liczba pierwsza z tą właściwością, która nie była wcześniej używana jako krawędź, to 1031

Twoje zadanie

Otrzymasz liczbę całkowitą nod 3 to 100
Ta liczba będzie wymiarami n x nkwadratu
Następnie musisz wypisać ten kwadrat dokładnie w postaci następujących przypadków testowych

Przypadki testowe

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
  • Dane wejściowe i wyjściowe można podać dowolną dogodną metodą .
  • Możesz wydrukować go do STDOUT lub zwrócić jako wynik funkcji.
  • Dopuszczalny jest pełny program lub funkcja.
  • Dopuszczalna jest dowolna ilość obcych białych znaków, pod warunkiem, że liczby odpowiednio się wyrównają
  • Standardowe luki są zabronione.
  • To jest więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

EDYCJA
Jest to możliwe dla wszystkich n
Oto liczby pierwszen=100

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000289        
9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000091            
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000711             
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002191     



A dla tych z was, którzy nie sądzicie, że jest to możliwe tutaj, WSZYSTKIE przypadki testowe

J42161217
źródło
Jeśli n może wzrosnąć do 100, warto mieć kilka większych przypadków testowych niż n = 10.
gastropner
4
Czy można udowodnić, że jest to możliwe dla wszystkich n: P? To nie problem z wyzwaniem, po prostu ciekawy.
Magic Octopus Urn
2
@MagicOctopusUrn Zdecydowanie nie jest to możliwe dla wszystkich n: dla n= 1 nie możemy spełnić ograniczenia, że ​​cztery krawędzie są różnymi liczbami pierwszymi, podczas gdy dla n= 2 jesteśmy zmuszeni wybrać 11,13,23, w którym momencie końcowa krawędź jest 12, który jest złożony. Nie mam dowodu na to, że jest to możliwe dla wszystkich n> 2, ale zszokowałoby mnie nauczenie się inaczej: nieoficjalnie, im więcej cyfr, tym więcej „pokoju wahadłowego”, aby spełnić ograniczenia.
Daniel Wagner
pk+1pkk463n4
2
@MagicOctopusUrn Twierdzenie o liczbach pierwszych dla postępów arytmetycznych mówi coś dość silnego o gęstości liczb pierwszych kończących się na 1, 3, 7 i 9 (w zapisie weź n = 10, a = 1/3/7/9); dla wystarczająco dużych nistnieją co najmniej dwie liczby pierwsze nzaczynające się od 1 i kończące się każdą z tych cyfr (stąd możemy wybrać dolną krawędź) i są co najmniej trzy liczby pierwsze zaczynające się od 1 i kończące się na 1 (stąd możemy wybrać Lewa krawędź).
Daniel Wagner

Odpowiedzi:

4

05AB1E , 64 63 56 53 48 46 bajtów

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

-1 bajtów dzięki @ Mr.Xcoder
-5 bajtów dzięki @Grimy .

n>4n>7

Wyjaśnienie:

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

Zobacz moją wskazówkę 05AB1E (rozdział Jak kompresować duże liczby całkowite? ), Aby zrozumieć, dlaczego tak Ž9¦jest 2460. I zapoznaj się z moją wskazówką 05AB1E, aby zrozumieć, jak kwadrat jest generowany przy Λwbudowanym kanwie.

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

Kevin Cruijssen
źródło
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Λ
Ponury
@Grimy Thanks! Bardzo fajne golfa. Udało mi się zapisać 2 dodatkowe bajty w oparciu o twoją 48-bajtową wersję, zmieniając ÐθsXÅ?‚sXÅ¿ªna θyXÅ?yXÅ¿). Nie jestem do końca pewien, dlaczego )działa w zakresie pętli, ponieważ spodziewałbym się, że zawinie również listę pierwszą w jej pierwszej iteracji. Ale nawet bez tego użycie yyzamiast zamiast Ðssoszczędza 1 bajt. :)
Kevin Cruijssen
4

05AB1E , 35 33 32 31 bajtów

-1 bajt dzięki Kevin Cruijssen

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

Wypróbuj online!

Wyjaśnienie:

°                 # 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
Ponury
źródło
Jest to częściowo oparte na odpowiedzi Kevina , ale w tym momencie jest na tyle inne, że czułem, że zasługuje na swoją własną odpowiedź, a nie na komentarz.
Grimmy,
1
Dopiero teraz widzę tę odpowiedź. Bardzo dobrze! Oprócz ogólnej metody (a zatem pierwszej i ostatniej części), określenie czterech liczb pierwszych i zbudowanie łańcucha odbywa się tak inaczej, że mogę zrozumieć oddzielną odpowiedź. +1 ode mnie Btw, możesz zapisać bajt usuwając Θat . Tylko 1jest truthy w 05AB1E, tak if Ni if N == 1są takie same.
Kevin Cruijssen
1
@KevinCruijssen Thanks! Oczywiście wiedziałem o tym, ale zapomniałem go użyć. Z perspektywy czasu Θijest to odpowiednik 05AB1E if (cond == true)...
Grimmy,
Tak, zgadza się. :) Θnadal może być przydatne, jeśli chcesz przekonwertować wszystko oprócz 1celu 0. Ale w przypadku instrukcji if inie jest to tak naprawdę konieczne, jak w przypadku pseudokodu == true.
Kevin Cruijssen
2

JavaScript (ES8),  205 ... 185 177  173 bajtów

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

Wypróbuj online!

W jaki sposób?

Krok # 1: obliczenie 4 liczb pierwszych

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

Krok # 2: formatowanie wyniku

[...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
źródło
2

Galaretka , 89 82 bajtów

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

Wypróbuj online!

Zdecydowanie może być bardziej golfowy, ale działa skutecznie dla dużych liczb.

Nick Kennedy
źródło
2

Galaretka , 59 bajtów

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

Wypróbuj online!

Krótsza, ale znacznie mniej wydajna odpowiedź Jelly.

Nick Kennedy
źródło
1

JavaScript, 484 bajty

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

Ostatnia nienazwana funkcja zwraca grafikę ASCII.

Oryginalny kod

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

Najlepsza i średnia złożoność czasu: Ω (100 n n) w notacji Big-Omega Knutha (n kroków do odejmowania n cyfr, 10 n odejmowań na sprawdzenie podzielności, 10 n sprawdzenie podzielności dla kontroli pierwszej i Ω (1) wykonane kontrole pierwsze ).

Najgorsza złożoność czasowa: Ω (1000 n n) w notacji Big-Omega Knutha (n kroków do odejmowania n cyfr, 10 n odejmowań na sprawdzenie podzielności, 10 n sprawdzenie podzielności dla kontroli pierwszej i 10 n wykonanych kontroli pierwszych).

Podejrzewam, że n=100zajmuje około 10 203 obliczeń.

Sidenote: Zweryfikowałem składnię za pomocą UglifyJS 3 i grałem w nią znacznie lepiej niż ja, oszczędzając 47,13% więcej i zarabiając 282 bajty. Jednak postanowiłem nie robić tego, bo czuję, że to oszustwo.

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

Właśnie usunął ostatnią funkcję, ponieważ nigdy nie są używane. Stało się gorzej, jeśli został przypisany i nie został usunięty, co oznacza dodanie dodatkowego kodu.

Naruyoko
źródło
3
To wydaje się niekompletne? I nie grałeś w golfa?
connectyourcharger
Tak. Ukończony / grał w golfa.
Naruyoko