User talk:Gangleri/tests/sandbox/squares

bugzilla:21572 save referencing the newest version of page using one of its history id

---

→ help:Displaying a formula
→ prime signature

Construction

If $n\,$ is the order of a most-perfect magic square then $n=4\cdot n^{'}$ . Assuming the prime decomposition of $n\,$ is

$n=p_{1}^{e_{1}}\cdot \ldots \cdot p_{M}^{e_{M}}=\prod _{k=1}^{M}p_{k}^{e_{k}}$ where $p_{i}<p_{j}\,$ for $i<j\,$ and $p_{1}=2\,$

Let $e_{total}\,$ be the the sum of the exponents: $e_{total}=\sum _{k=1}^{M}{e_{k}}$ .

Let $B\,$ be the canonical base for the representation of the integer numbers from $0\,$ to $n-1\,$ in a positional numeral system based on a mixture of prime numbers. It will contain $e_{total}\,$ $2\,$ -tuples:

$B=\left(\underbrace {\underbrace {\left(p_{1},1\right),\dots ,\left(p_{1},e_{1}\right)} _{e_{1}},\dots ,\underbrace {\left(p_{M},1\right),\dots ,\left(p_{M},e_{M}\right)} _{e_{M}}} _{M}\right)$

$C=\left(1,p_{1},\dots ,\prod _{m=1}^{pos-1}{p_{k}},\dots ,\prod _{m=1}^{e_{total}-1}{p_{k}}\right)$

is the weight of the canonical base $B\,$ . Both define together the positional numeral system.

The algorithm to find the representation of an integer $a\,$ between $1\,$ and $n\,$ is as follows:

initialisation

$k:=1\,$

$a:=a-1\,$

$c:=1\,$

$e_{total}\,$ computations

$b_{k}:=a\,{\bmod {\,}}p_{k}\,$ , where $p_{k}\,$ is the first value of the $k\,$ -th 2-tuple in $B\,$

$a:={\frac {\left(a-b_{k}\right)}{p_{k}}}\,$

$c_{k}:=c\,$ , this is the computation of $C\,$

$c:=c\cdot p_{k}\,$

$k:=k+1\,$

Any number $a\,$ between $1\,$ and $n\,$ can now be written as

$a=1+\sum _{k=1}^{e_{total}}{b_{k}}\cdot {c_{k}}$ where $0\leq b_{k}\leq p_{k}-1$ and $b_{k}\,$ ∈ $\mathbb {N} _{0}$

In the following the $e_{total}\,$ -tuple formed by the values $b_{k}\,$ is called coefficients in the positional numeral system defined by $B\,$ and $C\,$ .

Constructing auxiliary squares

Let $S\,$ be the set of the integer numbers from $1\,$ and $n\,$ . It is possible to choose a random $n\,$ -tuple named $S_{r}\,$ as follows:

initialisation

$k:=1\,$

$S:=S\,$

$c:=1\,$

${\frac {n}{2}}\,$ computations

a random element $n_{k}\,$ of $S\,$ is assigned to the the $k\,$ -th element of $S_{r}\,$

$S:=S\setminus \{n_{k}\}\,$

$S:=S\setminus \{n+1-n_{k}\}\,$

$k:=k+1\,$

Now it is possible to decompose each element of the $n\,$ -tuple $S_{r}\,$ in the positional numeral system defined by $B\,$ and $C\,$ calculating the coefficients for each element. Regrouping the appropriate coefficients it is possible to compute $e_{total}\,$ different $n\,$ -tuples $S_{r,k}\,$ where $S_{r,k}\,$ relates to the $m\,$ -th occurence of the prime number $p_{k^{'}}\,$ .

Each $n\,$ -tuple $S_{r,k}\,$ is used to construct an auxiliary square $A_{r,k}\,$ of order $n\,$ as follows:

the rows of $A_{r,k}\,$ with an odd number consist of the $n\,$ -tuples $S_{r,k}\,$

the rows of $A_{r,k}\,$ with an even number consist of the prime number $p_{k^{'}}\,$ -complements of $n\,$ -tuples $S_{r,k}\,$

for any value $0\leq b_{k^{''}}\leq p_{k^{'}}-1$ and $b_{k^{''}}\,$ ∈ $\mathbb {N} _{0}$ its complement is $p_{k^{'}}-1-b_{k^{''}}\,$

All steps from above can be repeated for columns. This is how a random $n\,$ -tuple named $S_{c}\,$ is choosen which will drive the computation of $e_{total}\,$ different $n\,$ -tuples $S_{c,k}\,$ where $S_{c,k}\,$ relates to the $m\,$ -th occurence of the prime number $p_{k^{'}}\,$ .

Finaly $e_{total}\,$ different auxiliary squares $A_{c,k}\,$ of order $n\,$ are generated as follows:

the columns of $A_{c,k}\,$ with an odd number consist of the transpose of the $n\,$ -tuples $S_{c,k}\,$

the columns of $A_{c,k}\,$ with an even number consist of the prime number $p_{k^{'}}\,$ -complements of the transpose of the $n\,$ -tuples $S_{c,k}\,$

The set of auxiliary squares $\{A_{r,k}\mid 1\leq k\leq e_{total}\}\cup \{A_{c,k}\mid 1\leq k\leq e_{total}\}\,$ has many interesting properties:

the sum of any 2×2 subsquare is constant inside a particular square

the sum of two cells with a distance of n/2 along a (major) diagonal is constant inside a particular square

choosing an ordered subset of $m\,$ auxiliary squares one can generate $n^{2}\,$ (one for each element) $m\,$ -tuples ; counting all different kind of $m\,$ -tuples show an equal distribution of these tuples

Parameterizing of the auxiliary squares

Magic squares of order $n\,$ contain all values from $1\,$ to $n^{2}\,$ .

$n^{2}=p_{1}^{2\cdot e_{1}}\cdot \ldots \cdot p_{M}^{2\cdot e_{M}}=\prod _{k=1}^{M}p_{k}^{2\cdot e_{k}}$ where $p_{i}<p_{j}\,$ for $i<j\,$ and $p_{1}=2\,$

In order to represent the integer numbers from $1\,$ to $n^{2}\,$ in a positional numeral system any base similar to the ones already used above needs to have $2\cdot e_{total}\,$ tuples. Below a noncanocal base is presented::

$B^{'}=\left(\underbrace {\underbrace {\left(p_{1},r\right),\dots ,\left(p_{1},r\right)} _{e_{1}},\dots ,\underbrace {\left(p_{M},r\right),\dots ,\left(p_{M},r\right)} _{e_{M}},} _{M}\underbrace {\underbrace {\left(p_{1},c\right),\dots ,\left(p_{1},c\right)} _{e_{1}},\dots ,\underbrace {\left(p_{M},c\right),\dots ,\left(p_{M},c\right)} _{e_{M}}} _{M}\right)$

Let $B^{''}\,$ be a permutation of the $2\cdot e_{total}\,$ $2\,$ -tuples of $B^{'}\,$ where for two consecutive $2\,$ -tuples $\left(p_{i},x_{i}\right)$ and $\left(p_{i+1},x_{i+1}\right)$

$x_{i}=x_{i+1}\,$ implies $p_{i}\leq p_{i+1}\,$

Let $P\,$ be the set of all permutations $B^{''}\,$ of $B^{'}\,$ as described above. The question is what is the number of elements of $P\,$. The requested number can be calculated with a function named $\beth \,$ which depends only on the number and values of the prime decomposition of $n\,$ ; i.e. $\beth \left({e_{1}},\ldots {e_{M}}\right)\,$ . Examples of its calculation are given here.
Description about the calculation of $\beth \,$ will follow. One can see that
$\beth \left({e_{1}},\ldots {e_{r}},\ldots {e_{s}},\ldots {e_{M}}\right)=\beth \left({e_{1}},\ldots {e_{s}},\ldots {e_{s}},\ldots {e_{M}}\right)\,$ if $r=s\,$

From the construction one can see that this method allows the construction of

$2^{n}\cdot ({\frac {n}{2}}!)^{2}\cdot \beth (e_{1},...,e_{M})\,$ different squares. See matching A051235.
If $n=2^{m}\,$ where $m\geq 2\,$ the function $\beth (m)\,$ simplifies to $\beth (m)={\binom {2\cdot m}{m}}\,$ and the number of most-perfect magic squares of order is
$2^{2^{m}}\cdot ({\frac {2^{m}}{2}}!)^{2}\cdot {\binom {2\cdot m}{m}}\,$ ( partialy matching A151932 )

To be continued.