cp's OEIS Frontend

A323866 Number of aperiodic toroidal necklaces of positive integers summing to n.

%I A323866 #12 Jan 14 2024 00:15:27
%S A323866 1,1,1,3,5,12,18,42,72,145,262,522,960,1879,3531,6831,13013,25148,
%T A323866 48177,93186,179507,347509,671955,1303257,2527162,4910681,9545176,
%U A323866 18579471,36183505,70540861,137603801,268655547,524842088,1026067205,2007118657,3928564113
%N A323866 Number of aperiodic toroidal necklaces of positive integers summing to n.
%C A323866 The 1-dimensional (Lyndon word) case is A059966.
%C A323866 We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.
%H A323866 Andrew Howroyd, <a href="/A323866/b323866.txt">Table of n, a(n) for n = 0..200</a>
%H A323866 S. N. Ethier, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Ethier/ethier2.html">Counting toroidal binary arrays</a>, J. Int. Seq. 16 (2013) #13.4.7.
%e A323866 Inequivalent representatives of the a(6) = 18 toroidal necklaces:
%e A323866   [6] [1 5] [2 4] [1 1 4] [1 2 3] [1 3 2] [1 1 1 3] [1 1 2 2] [1 1 1 1 2]
%e A323866 .
%e A323866   [1] [2] [1 1]
%e A323866   [5] [4] [1 3]
%e A323866 .
%e A323866   [1] [1] [1]
%e A323866   [1] [2] [3]
%e A323866   [4] [3] [2]
%e A323866 .
%e A323866   [1] [1]
%e A323866   [1] [1]
%e A323866   [1] [2]
%e A323866   [3] [2]
%e A323866 .
%e A323866   [1]
%e A323866   [1]
%e A323866   [1]
%e A323866   [1]
%e A323866   [2]
%t A323866 primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
%t A323866 facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
%t A323866 ptnmats[n_]:=Union@@Permutations/@Select[Union@@(Tuples[Permutations/@#]&/@Map[primeMS,facs[n],{2}]),SameQ@@Length/@#&];
%t A323866 apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
%t A323866 neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
%t A323866 Table[If[n==0,1,Length[Union@@Table[Select[ptnmats[k],And[apermatQ[#],neckmatQ[#]]&],{k,Times@@Prime/@#&/@IntegerPartitions[n]}]]],{n,0,10}]
%o A323866 (GAP) List([0..30], A323866); # See A323861 for code; _Andrew Howroyd_, Aug 21 2019
%Y A323866 Cf. A000031, A000670, A000740, A001037, A008965, A059966, A060223, A185700.
%Y A323866 Cf. A323858, A323861, A323865, A323871.
%K A323866 nonn
%O A323866 0,4
%A A323866 _Gus Wiseman_, Feb 04 2019
%E A323866 Terms a(16) and beyond from _Andrew Howroyd_, Aug 21 2019