Rozszerzanie OEIS: liczenie diamentowych płytek

46

Obiecuję, że będzie to moje ostatnie wyzwanie dotyczące diamong tilings (przynajmniej przez jakiś czas). Z drugiej strony to wyzwanie nie ma nic wspólnego ze sztuką ASCII i nie jest też golfem kodowym, więc w rzeczywistości jest zupełnie inaczej.

Przypominamy, że każdy sześciokąt można nazwać trzema różnymi diamentami:

Ciekawym pytaniem jest, ile z tych nachyleń istnieje dla danego rozmiaru sześciokąta. Wygląda na to, że liczby te zostały dokładnie zbadane i można je znaleźć w OEIS A008793 .

Problem staje się jednak trudniejszy, jeśli zapytamy, ile istnieje przechyleń do momentu obrotu i odbicia . Na przykład dla długości boku N = 2 istnieje 20 następujących nachyleń:

   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /\_\_\   /\_\_\   /\_\_\   /\_\_\   /_/\_\   /_/\_\   /\_\_\   /_/\_\   /_/\_\   /_/\_\ 
 /\/\_\_\ /\/_/\_\ /\/_/_/\ /\/_/\_\ /\_\/\_\ /\_\/_/\ /\/_/_/\ /\_\/\_\ /\_\/_/\ /_/\/\_\
 \/\/_/_/ \/\_\/_/ \/\_\_\/ \/_/\/_/ \/\_\/_/ \/\_\_\/ \/_/\_\/ \/_/\/_/ \/_/\_\/ \_\/\/_/
  \/_/_/   \/_/_/   \/_/_/   \_\/_/   \/_/_/   \/_/_/   \_\/_/   \_\/_/   \_\/_/   \_\/_/ 
   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /_/_/\   /\_\_\   /_/\_\   /_/_/\   /_/\_\   /_/\_\   /_/_/\   /_/_/\   /_/_/\   /_/_/\ 
 /\_\_\/\ /\/_/_/\ /_/\/_/\ /\_\_\/\ /\_\/_/\ /_/\/_/\ /_/\_\/\ /\_\_\/\ /_/\_\/\ /_/_/\/\
 \/\_\_\/ \/_/_/\/ \_\/\_\/ \/_/\_\/ \/_/_/\/ \_\/_/\/ \_\/\_\/ \/_/_/\/ \_\/_/\/ \_\_\/\/
  \/_/_/   \_\_\/   \_\/_/   \_\/_/   \_\_\/   \_\_\/   \_\/_/   \_\_\/   \_\_\/   \_\_\/ 

Ale wiele z nich jest identycznych podczas rotacji i refleksji. Jeśli weźmiemy pod uwagę te symetrie, pozostanie tylko 6 różnych nachyleń:

   ____     ____     ____     ____     ____     ____  
  /\_\_\   /\_\_\   /\_\_\   /_/\_\   /_/\_\   /_/\_\ 
 /\/\_\_\ /\/_/\_\ /\/_/_/\ /\_\/_/\ /\_\/_/\ /_/\/\_\
 \/\/_/_/ \/\_\/_/ \/\_\_\/ \/\_\_\/ \/_/\_\/ \_\/\/_/
  \/_/_/   \/_/_/   \/_/_/   \/_/_/   \_\/_/   \_\/_/ 

   2        2        6        6        1        3

gdzie liczby wskazują krotność każdego kafelka. Zauważ, że w przypadku większych sześciokątów istnieją również tile z krotnością 4 i 12.

Wygląda na to, że liczba przechyleń do symetrii została zbadana mniej dokładnie. Wpis AIS66931 OEIS wymienia tylko pięć terminów:

1, 1, 6, 113, 20174

gdzie pierwszy termin dotyczy długości boku, N = 0a ostatni termin długości boku N = 4.

Jestem pewien, że możemy to zrobić lepiej!

Twoim zadaniem jest obliczenie liczby przechyleń dla danej długości boku.

To jest . Twój wynik będzie najwyższą długością boku, Ndla której Twój kod wygeneruje poprawny wynik w ciągu 30 minut na mojej maszynie. W przypadku remisu, będę zaakceptować przedstawienie która produkuje wynik na które N najszybciej.

Jak zwykle nie możesz zakodować wyników, które już znasz, aby wygrać remis. Algorytm, który rozwiązuje, N = 3powinien być identyczny z tym, który rozwiązuje N = 5.

Twoje zgłoszenie nie może zajmować więcej niż 4 GB pamięci. Dam trochę swobody, jeśli działasz blisko tego limitu, ale jeśli konsekwentnie przekraczasz ten limit lub jeśli znacznie przekroczysz ten limit, nie liczę tego Nza twoje poddanie się.

Przetestuję wszystkie zgłoszenia na moim komputerze z systemem Windows 8, więc upewnij się, że wybrany język jest swobodnie dostępny w systemie Windows. Jedynym wyjątkiem jest Mathematica (ponieważ akurat mam licencję). Dołącz instrukcje dotyczące sposobu kompilowania / uruchamiania kodu.

Oczywiście możesz swobodnie obliczyć więcej terminów w swoim czasie (dla nauki i dla innych, aby porównać ich liczby), ale wynik Twojej odpowiedzi zostanie określony w ciągu tych 30 minut.

Martin Ender
źródło
4
Zauważ, że ponieważ N = 6daje wynik większy niż 10 ^ 12, niekonstruktywne rozwiązanie jest prawie na pewno konieczne, aby dojść tak daleko.
Peter Taylor,
1
@PeterTaylor Miałem nadzieję, że pozwoli to na więcej miejsca na ulepszenia. Być może najpierw kilka prostych konstruktywnych odpowiedzi, które mogą zrobić N = 5, aby uzyskać lepszy wgląd w problem, a następnie potencjalnie podejścia hybrydowe, które nie muszą konstruować wszystkich przechyleń, ale mogą ekstrapolować całkowitą liczbę z kilku skonstruowanych ... a potem może coś analitycznego, jeśli naprawdę będziemy mieli szczęście. :)
Martin Ender
2
Ryzykując stwierdzenie tego, co oczywiste, wydaje mi się, że każde takie kafelkowanie odpowiada rzutowi zestawu kostek jednostkowych widzianych z odległego punktu widzenia, np. Z (100, -100,100). Uważam, że to zmniejsza ciężar konstruowania kafelków.
DavidC
1
@DavidCarraher Rzeczywiście. Mówiąc dokładniej, taki układ kostek jednostkowych jest schematem 3D Younga . (Może to komuś pomaga.)
Martin Ender
@DavidCarraher Jeśli spojrzysz wystarczająco mocno na duży sześciokąt, zobaczysz 2 różne sposoby interpretowania go jako diagramu Younga. Oczywistym sposobem (przynajmniej dla mnie) jest zobaczenie płaskiego obszaru u góry i po lewej stronie z brakiem prostopadłościanu 2x2x1 w lewym górnym rogu. Ale jest na to inny sposób: pusta strefa w tym obszarze z prostopadłościanem 2x2x1. Pomocne może być przechylenie o 60 stopni. Boli mnie oczy, ale myślę, że dwa młode schematy pasują do siebie, być może poprzez odbicie jednego z nich. OEIS A008793 jest bardzo ostrożny ze swoim sformułowaniem: „liczba przegród płaskich, których młode diagramy ...”
Level River St

Odpowiedzi:

80

Algebra, teoria grafów, inwersja Möbiusa, badania i Java

Grupa symetrii sześciokąta jest dwuścienną grupą rzędu 12 i jest generowana przez obrót o 60 stopni i odbicie lustrzane na średnicy. Ma 16 podgrup, ale niektóre z nich są nietrywialnymi grupami koniugacji (te, które mają tylko odbicia, mają 3 możliwości wyboru osi), więc istnieje 10 zasadniczo różnych symetrii, które może mieć kafelek sześciokąta:

Obrazy 10 symetrii

Liczbę diamentowych pochyłości podzbioru trójkątnej sieci można obliczyć jako wyznacznik , więc moim początkowym podejściem było ustalenie jednego wyznacznika dla każdej z symetrii sześciokąta, aby obliczyć liczbę nachyleń, które mają co najmniej te symetrie ; a następnie użyj inwersji Möbiusa w algebrze padania ich zbioru (w zasadzie uogólnienie zasady włączenia-wykluczenia), aby obliczyć liczbę przechyleń, których grupą symetrii jest dokładnie każdy z 10 przypadków. Jednak niektóre symetrie mają nieprzyjemne warunki brzegowe, więc musiałem zsumować wykładniczo wiele wyznaczników. Na szczęście wartości uzyskane dlan < 10dało mi wystarczającą ilość danych, aby móc zidentyfikować odpowiednie sekwencje w OEIS i złożyć razem zamkniętą formę (dla pewnej wartości „zamkniętej”, która dopuszcza skończone produkty). Trochę dyskusji na temat sekwencji i odniesień do dowodów, w formalnym piśmie, które przygotowałem, aby uzasadnić aktualizacje sekwencji OEIS.

Po załatwieniu podwójnego liczenia okazuje się, że cztery z dziesięciu wartości starannie się anulują, więc musimy tylko obliczyć pozostałe sześć, a następnie wykonać ważoną sumę.

Kod ten trwa mniej niż 30 sekund N=1000na moim komputerze.

import java.math.BigInteger;

public class OptimisedCounter {
    private static int[] minp = new int[2];

    public static void main(String[] args) {
        if (args.length > 0) {
            for (String arg : args) System.out.println(count(Integer.parseInt(arg)));
        }
        else {
            for (int n = 0; n < 16; n++) {
                System.out.format("%d\t%s\n", n, count(n));
            }
        }
    }

    private static BigInteger count(int n) {
        if (n == 0) return BigInteger.ONE;

        if (minp.length < 3*n) {
            int[] wider = new int[3*n];
            System.arraycopy(minp, 0, wider, 0, minp.length);
            for (int x = minp.length; x < wider.length; x++) {
                // Find the smallest prime which divides x
                for (wider[x] = 2; x % wider[x] != 0; wider[x]++) { /* Do nothing */ }
            }
            minp = wider;
        }

        BigInteger E = countE(n), R2 = countR2(n), F = countF(n), R3 = countR3(n), R = countR(n), FR = countFR(n);
        BigInteger sum = E.add(R3);
        sum = sum.add(R2.add(R).multiply(BigInteger.valueOf(2)));
        sum = sum.add(F.add(FR).multiply(BigInteger.valueOf(3)));
        return sum.divide(BigInteger.valueOf(12));
    }

    private static BigInteger countE(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= i + n; j++) w[j]--;
            for (int j = i + n + 1; j <= i + 2*n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countR2(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            w[3*i+2]++;
            for (int j = 3*i + 1; j <= 2*i + n + 1; j++) w[j]--;
            for (int j = 2*i + n + 1; j <= i + n + n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countF(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            for (int j = 2*i + 1; j <= 2*i + n; j++) w[j]--;
            for (int j = i + n + 1; j <= i + 2*n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countR3(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        return countE(n / 2).pow(2);
    }

    private static BigInteger countR(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        int m = n / 2;
        int[] w = new int[3*m-1];
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= 3*i+1; j++) w[j] += 2;
            for (int j = 1; j <= i + m; j++) w[j] -= 2;
        }
        return powerProd(w);
    }

    private static BigInteger countFR(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        int m = n / 2;
        int[] w = new int[3*n-2];
        for (int j = 1; j <= m; j++) w[j]--;
        for (int j = 2*m; j <= 3*m-1; j++) w[j]++;
        for (int i = 0; i <= 2*m-3; i++) {
            for (int j = i + 2*m + 1; j <= i + 4*m; j++) w[j]++;
            for (int j = 2*i + 3; j <= 2*i + 2*m + 2; j++) w[j]--;
        }
        return powerProd(w);
    }

    private static BigInteger powerProd(int[] w) {
        BigInteger result = BigInteger.ONE;
        for (int x = w.length - 1; x > 1; x--) {
            if (w[x] == 0) continue;

            int p = minp[x];
            if (p == x) result = result.multiply(BigInteger.valueOf(p).pow(w[p]));
            else {
                // Redistribute it. This should ensure we avoid negatives.
                w[p] += w[x];
                w[x / p] += w[x];
            }
        }

        return result;
    }
}
Peter Taylor
źródło
24
Jesteś naprawdę bogiem wśród śmiertelników. Mam nadzieję, że Twoje rozwiązanie zostanie opublikowane w prestiżowym czasopiśmie.
Alex A.
To jest niesamowite. BTW mój (obecnie nie opublikowany) kod daje 22306956 dla N = 5: 22231176 (12) +275 (4) +75328 (6) +352 (2), rozbieżność 1, co jest nieparzyste. Nie mam pojęcia, że ​​tu robisz, czy nadaje się na podział według symetrii? Dla N = 4 jestem 16 niższy od ciebie i oeis.org/A066931/a066931.txt Z tego odniesienia wynika, że ​​mam 16 zbyt wielu krotności 12, które muszę przekonwertować na 32 krotność 6. Nie jestem zbyt zaskoczony, nawet N są dla mnie trudniejsze. Ale nie mam problemów z nieparzystym N i dostaję prawidłowe odpowiedzi dla 0 <N <4. Poszuka oczywistych problemów i opublikuję mój kod jutro.
Level River St
@steveverrill, jeśli rozumiem notację, dla N = 5 robię to 22231176 (12) + 75328 (6) + 275 (4) + 176 (2). Myślę, że nie dzielisz indeksu 2 przez 2. (FWIW dla liczb nieparzystych wszystkie mają oś symetrii przechodzącą przez dwa wierzchołki i symetrię rotacyjną rzędu 3).
Peter Taylor
@steveverrill, a dla N = 4 rozbieżność wydaje się idealnie pasować do liczby, która ma oś symetrii przechodzącą przez punkty środkowe dwóch krawędzi.
Peter Taylor,
3
Imponujące, że to rozwiązałeś. Mam nadzieję, że ostatecznie opublikujesz odpowiedź, którą nie-matematycy mogą podążać.
DavidC
15

do

Wprowadzenie

Jak skomentował David Carraher, najprostszym sposobem analizy płytki sześciokątnej wydaje się być wykorzystanie jej izomorfizmu z trójwymiarowym diagramem Younga, zasadniczo kwadratem x, y wypełnionym całkowitymi słupkami wysokości, których wysokości muszą pozostać takie same lub wzrosnąć w miarę zbliżania się do osi Z.

Zacząłem od algorytmu znajdowania sum, który jest bardziej podatny na dostosowanie do zliczania symetrii niż opublikowany algorytm, który opiera się na odchyleniu do jednej z trzech osi kartezjańskich.

Algorytm

Zaczynam od wypełnienia komórek płaszczyzn x, y i z 1, podczas gdy reszta obszaru zawiera zera. Gdy to zrobisz, buduję wzór warstwa po warstwie, przy czym każda warstwa zawiera komórki, które mają wspólną odległość 3D manhattan od początku. Komórka może zawierać tylko 1, jeśli trzy komórki poniżej również zawierają 1. jeśli którakolwiek z nich zawiera 0, wówczas komórka musi być 0.

Zaletą budowania wzoru w ten sposób jest to, że każda warstwa jest symetryczna względem linii x = y = z. Oznacza to, że każdą warstwę można sprawdzić niezależnie pod kątem symetrii.

Sprawdzanie symetrii

Symetrie bryły są następujące: 3-krotny obrót wokół linii x = y = z -> 3-krotny obrót wokół środka sześciokąta; oraz 3 x odbicia o 3 płaszczyznach zawierających linię x = y = z i każdą z osi x, y, z -> odbicie o liniach przechodzących przez narożniki sześciokąta.

Daje to tylko 6-krotną symetrię. Aby uzyskać pełną symetrię sześciokąta, należy rozważyć inny rodzaj symetrii. Każda bryła (zbudowana z 1) ma komplementarną bryłę (zbudowana z 0). Gdy N jest nieparzyste, bryła uzupełniająca musi różnić się od oryginalnej bryły (ponieważ nie jest możliwe, aby miały taką samą liczbę kostek). Jednak gdy komplementarna bryła zostanie obrócona, okaże się, że jej reprezentacja 2D jako płytki diamentowej jest identyczna (z wyjątkiem 2-krotnej operacji symetrii) z oryginalną bryłą. Tam, gdzie N jest parzyste, możliwe jest, że ciało stałe jest samo-odwrotne.

Można to zobaczyć w przykładach dla N = 2 w pytaniu. Patrząc od lewej strony, pierwszy sześciokąt wygląda jak solidny sześcian z 8 małymi kostkami, podczas gdy ostatni sześciokąt wygląda jak pusta skorupa z 0 małymi kostkami. Patrząc z prawej strony, sytuacja jest odwrotna. Sześciokąty 3, 4 i 5 oraz 16, 17 i 18 sześciokąty wyglądają tak, jakby zawierały 2 lub 6 kostek, a zatem uzupełniają się w 3 wymiarach. Są one powiązane ze sobą w 2 wymiarach za pomocą 2-krotnej operacji symetrii (2-krotny obrót lub odbicie wokół osi przez krawędzie sześciokąta). Z drugiej strony, 9, 10, 11 i 12 sześciokąty pokazują wzory 3D, które są ich własnymi uzupełnieniami, a zatem mają wyższą symetrię (dlatego są to jedyne wzorce o nieparzystej krotności).

Zauważ, że posiadanie (N ^ 3) / 2 kostek jest warunkiem koniecznym do samouzupełniania się, ale ogólnie nie jest warunkiem wystarczającym, jeśli N> 2. Wynikiem tego wszystkiego jest to, że w przypadku nieparzystego N przechylenie zawsze występuje w parach (N ^ 3) / 2 kostki należy dokładnie sprawdzić.

Bieżący kod (generuje właściwą sumę dla N = 1,2,3,5. Błąd, jak omówiono dla N = 4).

int n;                     //side length

char t[11][11][11];        //grid sized for N up to 10

int q[29][192], r[29];     //tables of coordinates for up to 10*3-2=28 layers 

int c[9];                  //counts arrangements found by symmetry class. c[8] contains total.


//recursive layer counting function. m= manhattan distance, e= number of cells in previous layers, s=symmetry class.
void f(int m,int e,int s){

  int u[64], v[64], w[64]; //shortlists for x,y,z coordinates of cells in this layer
  int j=0;                 
  int x,y,z;

  for (int i=r[m]*3; i; i-=3){
    // get a set of coordinates for a cell in the current layer.
    x=q[m][i-3]; y= q[m][i-2]; z= q[m][i-1];
    // if the three cells in the previous layer are filled, add it to the shortlist u[],v[],w[]. j indicates the length of the shortlist.
    if (t[x][y][z-1] && t[x][y-1][z] && t[x-1][y][z]) u[j]=x, v[j]=y, w[j++]=z ;
  }


  // there are 1<<j possible arrangements for this layer.   
  for (int i = 1 << j; i--;) {

    int d = 0;

    // for each value of i, set the 1's bits of t[] to the 1's bits of i. Count the number of 1's into d as we go.
    for (int k = j; k--;) d+=(t[u[k]][v[k]][w[k]]=(i>>k)&1);

    // we have no interest in i=0 as it is the empty layer and therefore the same as the previous recursion step. 
    // Still we loop through it to ensure t[] is properly cleared.      

    if(i>0){
      int s1=s;    //local copy of symmetry class. 1's bit for 3 fold rotation, 2's bit for reflection in y axis.
      int sc=0;    //symmetry of self-complement.

      //if previous layers were symmetrical, test if the symmetry has been reduced by the current layer 
      if (s1) for (int k = j; k--;) s1 &= (t[u[k]][v[k]][w[k]]==t[w[k]][u[k]][v[k]]) | (t[u[k]][v[k]][w[k]]==t[w[k]][v[k]][u[k]])<<1;

      //if exactly half the cells are filled, test for self complement
      if ((e+d)*2==n*n*n){
        sc=1;
        for(int A=1; A<=(n>>1); A++)for(int B=1; B<=n; B++)for(int C=1; C<=n; C++) sc&=t[A][B][C]^t[n+1-A][n+1-B][n+1-C];
      }

      //increment counters for total and for symmetry class.
      c[8]++; c[s1+(sc<<2)]++;

      //uncomment for graphic display of each block stacking with metadata. not recommended for n>3.
      //printf("m=%d  j=%d  i=%d c1=%d-2*%d=%d c3=%d cy=%d(cs=%d) c3v=%d ctot=%d\n",m,j,i,c[0],c[2],c[0]-2*c[2],c[1],c[2],c[2]*3,c[3],c[8]);
      //printf("m=%d  j=%d  i=%d C1=%d-2*%d=%d C3=%d CY=%d(CS=%d) C3V=%d ctot=%d\n",m,j,i,c[4],c[6],c[4]-2*c[6],c[5],c[6],c[6]*3,c[7],c[8]);
      //for (int A = 0; A<4; A++, puts(""))for (int B = 0; B<4; B++, printf(" "))for (int C = 0; C<4; C++) printf("%c",34+t[A][B][C]);

      //recurse to next level.
      if(m<n*3-2)f(m + 1,e+d,s1);

    }
  } 
}

main()
{
  scanf("%d",&n);

  int x,y,z;

  // Fill x,y and z planes of t[] with 1's
  for (int a=0; a<9; a++) for (int b=0; b<9; b++) t[a][b][0]= t[0][a][b]= t[b][0][a]= 1;

  // Build table of coordinates for each manhattan layer
  for (int m=1; m < n*3-1; m++){
    printf("m=%d : ",m);
    int j=0;
    for (x = 1; x <= n; x++) for (y = 1; y <= n; y++) {
      z=m+2-x-y;
      if (z>0 && z <= n) q[m][j++] = x, q[m][j++] = y, q[m][j++]=z, printf(" %d%d%d ",x,y,z);
      r[m]=j/3;
    }
    printf(" : r=%d\n",r[m]);
  }

  // Set count to 1 representing the empty box (symmetry c3v)
  c[8]=1; c[3]=1; 

  // Start searching at f=1, with 0 cells occupied and symmetry 3=c3v
  f(1,0,3); 

  // c[2 and 6] only contain reflections in y axis, therefore must be multiplied by 3.
  // Similarly the reflections in x and z axis must be subtracted from c[0] and c[4].
  c[0]-=c[2]*2; c[2]*=3; 
  c[4]-=c[6]*2; c[6]*=3;



  int cr[9];cr[8]=0;
  printf("non self-complement                   self-complement\n");
  printf("c1  %9d/12=%9d           C1  %9d/6=%9d\n",   c[0], cr[0]=c[0]/12,     c[4], cr[4]=c[4]/6);
  if(cr[0]*12!=c[0])puts("c1 division error");if(cr[4]*6!=c[4])puts("C1 division error");

  printf("c3  %9d/4 =%9d           C3  %9d/2=%9d\n",   c[1], cr[1]=c[1]/4,      c[5], cr[5]=c[5]/2);
  if(cr[1]*4!=c[1])puts("c3 division error");if(cr[5]*2!=c[5])puts("C3 division error");

  printf("cs  %9d/6 =%9d           CS  %9d/3=%9d\n",   c[2], cr[2]=c[2]/6,      c[6], cr[6]=c[6]/3);
  if(cr[2]*6!=c[2])puts("cs division error");if(cr[6]*3!=c[6])puts("CS division error");

  printf("c3v %9d/2 =%9d           C3V %9d/1=%9d\n",   c[3], cr[3]=c[3]/2,      c[7], cr[7]=c[7]);
  if(cr[3]*2!=c[3])puts("c3v division error");  

  for(int i=8;i--;)cr[8]+=cr[i]; 
  printf("total =%d unique =%d",c[8],cr[8]);    
}

Wynik

Program generuje tabelę wyników 8 wpisów, zgodnie z 8 symetriami bryły. Bryła może mieć dowolną z 4 następujących symetrii (notacja Schoenfliesa)

c1: no symmetry
c3: 3-fold axis of rotation (produces 3-fold axis of rotation in hexagon tiling)
cs: plane of reflection (produces line of reflection in hexagon tiling)
c3v both of the above (produces 3-fold axis of rotation and three lines of reflection through the hexagon corners)

Dodatkowo, gdy bryła ma dokładnie połowę komórek z jedynkami i połowę z zerami, istnieje możliwość odwrócenia wszystkich jedynek i zer, a następnie odwrócenia współrzędnych przez środek przestrzeni sześcianu. To właśnie nazywam samouzupełnianiem, ale bardziej matematyczny termin byłby „antysymetryczny w stosunku do centrum inwersji”.

Ta operacja symetrii daje 2-krotną oś obrotu w kafelku sześciokąta.

Wzory o tej symetrii są wymienione w osobnej kolumnie. Występują tylko tam, gdzie N jest parzyste.

Moje obliczenie wydaje się być nieco wyłączone dla N = 4. W dyskusji z Peterem Taylorem wydaje się, że nie wykrywam przechyłek, które mają jedynie symetrię linii przechodzącej przez krawędzie sześciokąta. Jest tak prawdopodobnie dlatego, że nie testowałem samokompletu (antysymetrii) dla operacji innych niż (inwersja) x (tożsamość). Testowanie samokompletu dla operacji (inwersja) x (odbicie) i (inwersja) x (3-krotny obrót ) może odkryć brakujące symetrie. Spodziewałbym się wtedy, że pierwsza linia danych dla N = 4 będzie wyglądać tak (16 mniej w C1 i 32 więcej w C1):

c1   224064/12=18672          C1  534/6=89

Dzięki temu sumy będą zgodne z odpowiedzią Petera i https://oeis.org/A066931/a066931.txt

prąd wyjściowy jest następujący.

N=1
non self-complement     self-complement
c1      0/12= 0           C1  0/6= 0
c3      0/4 = 0           C3  0/2= 0
cs      0/6 = 0           CS  0/3= 0
c3v     2/2 = 1           C3V 0/1= 0
total =2 unique =1

non self-complement     self-complement
N=2
c1      0/12= 0           C1  0/6= 0
c3      0/4 = 0           C3  0/2= 0
cs     12/6 = 2           CS  3/3= 1
c3v     4/2 = 2           C3V 1/1= 1
total =20 unique =6

N=3
non self-complement     self-complement
c1    672/12=56           C1  0/6= 0
c3      4/4 = 1           C3  0/2= 0
cs    288/6 =48           CS  0/3= 0
c3v    16/2 = 8           C3V 0/1= 0
total =980 unique =113

N=4 (errors as discussed)
non self-complement     self-complement
c1   224256/12=18688          C1  342/6=57
c3       64/4 =16             C3  2/2= 1
cs     8064/6 =1344           CS  54/3=18
c3v      64/2 =32             C3V 2/1= 2
total =232848 unique =20158

N=5
non self-complement     self-complement
c1  266774112/12=22231176        C1  0/6= 0
c3       1100/4 =275             C3  0/2= 0
cs     451968/6 =75328           CS  0/3= 0
c3v       352/2 =176             C3V 0/1= 0
total =267227532 unique =22306955

Lista spraw (zaktualizowana)

Uporządkuj bieżący kod.

Zrobione mniej więcej

Zaimplementuj sprawdzanie symetrii dla bieżącej warstwy i przekaż parametr dla symetrii poprzedniej warstwy (nie ma sensu sprawdzać, czy ostatnia warstwa była asymetryczna).

Gotowe, wyniki dla nieparzystego N zgadzają się z opublikowanymi danymi

Dodaj opcję, aby ukryć liczenie liczb asymetrycznych (powinno działać znacznie szybciej)

Można to zrobić, dodając kolejny warunek do wywołania rekurencji: if(s1 && m<n*3-2)f(m + 1,e+d,s1)Skraca czas działania dla N = 5 z 5 minut do około sekundy. W rezultacie pierwszy wiersz wyniku staje się całkowitym śmieciem (podobnie jak sumy całkowite), ale jeśli suma jest już znana z OEIS, liczbę asymetrycznych przechyleń można odtworzyć, przynajmniej dla nieparzystej N.

Ale nawet dla N liczba asymetrycznych (zgodnie z symetriami c3v) ciał stałych, które są samouzupełnianiem, zostałaby utracona. W tym przypadku przydatny może być osobny program dedykowany ciałom stałym z dokładnie (N ** 3) / 2 komórkami z 1. Przy tym dostępnym (i liczącym poprawnie) wypróbowanie N = 6 może być możliwe, ale uruchomienie zajmie dużo czasu.

Zaimplementuj zliczanie komórek, aby zredukować wyszukiwanie do (N ^ 3) / 2 kostek.

Nie zrobione, oczekiwane oszczędności będą marginalne

Zaimplementuj sprawdzanie symetrii (komplementarne bryły) dla wzorów zawierających dokładnie (N ^ 3) / 2 kostki.

Zrobione, ale wydaje się, że występują pominięcia, patrz N = 4.

Znajdź sposób na wybranie najniższej leksykalnie liczby z asymetrycznej.

Oczekuje się, że oszczędności nie będą tak duże. Tłumienie asymetrycznych liczb eliminuje większość tego. Jedynym sprawdzanym odbiciem jest płaszczyzna przechodząca przez oś y (xiz obliczane są później przez pomnożenie przez 3). Liczby z tylko symetrią obrotową są liczone w obu postaciach enancjomerycznych. Być może działałby prawie dwa razy szybciej, gdyby tylko jeden został policzony.

Aby to ułatwić, prawdopodobnie popraw sposób wyświetlania współrzędnych w każdej warstwie (tworzą one zdegenerowane grupy 6 lub 3, ewentualnie z grupą 1 w dokładnym środku warstwy).

Ciekawe, ale prawdopodobnie na stronie są inne pytania do zbadania.

Level River St
źródło