Ponder This Challenge - May 2026 - The Powers of a Binary Matrix

This riddle was proposed by Lorenzo Gianferrari Pini and Radu-Alexandru Todor - thanks!

Given a square binary matrix of order $N$, $A\in M(\mathbb{Z}_2)_{N\times N}$ such there is exactly one "1" value in each row and column of $A$, we can find the lowest $m>0$ such that $A^m=I$, the identity matrix.

Denote by $g(N)$ the maximum such $m$ when going over all the matrices in $M(\mathbb{Z}_2)_{N\times N}$ satisfying the above condition.

For example, $g(10)=30$ and $g(50) = 180180$.

Your goal: Find $g(10^6)\ \text{mod}\ (10^9+7)$.

A bonus "*" will be given for finding $g(10^8)\ \text{mod}\ (10^9+7)$.

Solution

• Click here to view the solution

  The numerical solutions are

  • 534192793
  • 41567508

  The binary matrix formulation is a thin disguise for Landau's function, $g(n)$ which gives the largest order to an element of the symmetic group $S_n$ (the group of permutations on $n$ elements).

  Since this is a known function, the main challange of the riddle was to find heuristic for efficient computations.

  A common approach is to consider the computation of $g(n)$ as a solution to a specific Knapsack problem:

  Since every element of $S_n$ is a product of distinct cycles on $n$ elements total, and its order is the LCM of the lengths of the cycles, the challange is to find numbers $d_1,\ldots,d_k$ such that $d_1+\ldots+d_k=n$ while maximizing $LCM(d_1,\ldots,d_k)$, which can be done via dynamic programming.

Solvers

• *King Pig (1/5/2026 9:49 AM IDT)
• *Alper Halbutogullari (1/5/2026 11:49 AM IDT)
• Ahmet Yuksel (1/5/2026 1:22 PM IDT)
• *Lazar Ilic (1/5/2026 1:51 PM IDT)
• *Paul Lupascu (1/5/2026 3:38 PM IDT)
• *Jean-François Hermant (1/5/2026 5:48 PM IDT)
• *Bertram Felgenhauer (1/5/2026 7:20 PM IDT)
• Stéphane Higueret (1/5/2026 10:37 PM IDT)
• Hakan Summakoğlu (2/5/2026 12:38 AM IDT)
• *Prashant Wankhede (2/5/2026 12:54 AM IDT)
• *Carter Tran (2/5/2026 3:46 AM IDT)
• *Jack Saleeby (2/5/2026 5:58 AM IDT)
• *Quentin Higueret (2/5/2026 6:03 AM IDT)
• *Pitiwat Chimplee (2/5/2026 2:22 PM IDT)
• *Richard Gosiorovsky (2/5/2026 3:09 PM IDT)
• David Greer (2/5/2026 5:36 PM IDT)
• Simon Atileh (2/5/2026 10:46 PM IDT)
• *Bert Dobbelaere (2/5/2026 11:10 PM IDT)
• *Martin Thorne (3/5/2026 5:51 AM IDT)
• Latchezar Christov (3/5/2026 10:15 PM IDT)
• Shirish Chinchalkar (3/5/2026 10:50 PM IDT)
• *Daniel Bitin (4/5/2026 12:30 AM IDT)
• *Philip Naveen (4/5/2026 5:10 AM IDT)
• *Franciraldo Cavalcante (4/5/2026 5:13 AM IDT)
• *Junyu Zhou (4/5/2026 7:30 AM IDT)
• *Stephen Ebert (4/5/2026 9:27 AM IDT)
• *Jiri Spitalsky (4/5/2026 10:38 AM IDT)
• Nadir S. (4/5/2026 11:46 AM IDT)
• *Guangxi Liu (4/5/2026 11:53 AM IDT)
• Michael Liepelt (4/5/2026 11:55 AM IDT)
• Juergen Koehl (4/5/2026 12:10 PM IDT)
• Hugo Pfoertner (4/5/2026 9:46 PM IDT)
• Dominik Reichl (4/5/2026 11:31 PM IDT)
• *Dawson Yao (5/5/2026 12:00 AM IDT)
• *Rethna Pulikkoonattu (5/5/2026 12:13 AM IDT)
• Jason Shaw (5/5/2026 4:22 AM IDT)
• *Kang Jin Cho (5/5/2026 5:15 AM IDT)
• Amos Guler (5/5/2026 2:35 PM IDT)
• *Shouky Dan & Tamir Ganor (5/5/2026 4:57 PM IDT)
• Jan Fricke (5/5/2026 5:01 PM IDT)
• *Evan Semet (5/5/2026 5:30 PM IDT)
• William Hakob Logian (6/5/2026 9:25 AM IDT)
• Mickle Jiao (6/5/2026 3:12 PM IDT)
• *Sanandan Swaminathan (7/5/2026 3:21 AM IDT)
• Siebel Goose (7/5/2026 8:06 AM IDT)
• *Daniel Chong Jyh Tar (7/5/2026 5:31 PM IDT)
• John Tromp (7/5/2026 6:57 PM IDT)
• Karl D’Souza (7/5/2026 10:38 PM IDT)
• *Arpit Shrivastava (8/5/2026 11:37 AM IDT)
• Trevor Nerbas (8/5/2026 7:27 PM IDT)
• *Liubing Yu (8/5/2026 11:26 PM IDT)
• Chern Arthas (9/5/2026 10:07 AM IDT)
• Christoph Baumgarten (9/5/2026 4:34 PM IDT)
• Kipp Johnson (9/5/2026 10:54 PM IDT)
• *Ashwin Mathews (10/5/2026 10:33 PM IDT)
• *Erik Hostens (12/5/2026 9:44 AM IDT)
• Fabio Michele Negroni (12/5/2026 7:20 PM IDT)
• Alex Fleischer (12/5/2026 8:24 PM IDT)
• Dan Dima (13/5/2026 9:32 AM IDT)
• Nick Trapp (14/5/2026 12:19 AM IDT)
• Morteza Esmaeili (15/5/2026 12:07 AM IDT)
• *Vladimir Volevich (15/5/2026 2:10 PM IDT)
• Armin Krauss (15/5/2026 5:46 PM IDT)
• Marc Casas (16/5/2026 1:00 AM IDT)
• Arthur Vause (16/5/2026 2:59 PM IDT)
• Dieter Beckerle (16/5/2026 6:40 PM IDT)
• Michael Vahle (17/5/2026 3:32 PM IDT)
• Hansraj Nahata & Govind Jujare (18/5/2026 1:48 AM IDT)
• Laurence Warne (18/5/2026 6:49 PM IDT)
• Jupally Raviteja Rao (19/5/2026 7:28 AM IDT)
• Gary M. Gerken (20/5/2026 6:12 AM IDT)
• Reiner Martin (23/5/2026 10:01 PM IDT)
• *David F.H. Dunkley (24/5/2026 4:40 AM IDT)
• *Justin Mazenauer (25/5/2026 9:17 PM IDT)
• Fabio Filatrella (26/5/2026 2:56 AM IDT)
• *Nickita Khylkouski (26/5/2026 4:38 AM IDT)
• Fakih Karademir (26/5/2026 12:30 PM IDT)
• *Motty Porat (27/5/2026 12:09 AM IDT)
• Steffen Wolf (27/5/2026 7:22 PM IDT)
• Lorenz Reichel (28/5/2026 2:22 PM IDT)
• *Lorenzo Gianferrari Pini (28/5/2026 3:39 PM IDT)
• *Prajit Adhikari (29/5/2026 9:07 AM IDT)
• *Tim Walters (29/5/2026 10:17 AM IDT)
• *Guy Daniel Hadas (30/5/2026 11:12 PM IDT)
• *Jackson La Vallee (31/5/2026 7:40 AM IDT)
• Alexander Bielik (1/6/2026 7:54 AM IDT)
• Chris Shannon (1/6/2026 8:18 AM IDT)
• *Lucas Reymond (1/6/2026 11:46 PM IDT)
• Oscar Volpatti (2/6/2026 1:52 AM IDT)
• Radu-Alexandru Todor (2/6/2026 10:50 PM IDT)
• Nyles Heise (3/6/2026 5:41 AM IDT)
• Marco Bellocchi (4/6/2026 7:07 PM IDT)
• *Li Li (6/6/2026 5:09 PM IDT)
• George Wellen (8/6/2026 1:55 AM IDT)
• Resnina Tathyana (8/6/2026 6:35 PM IDT)
• Michael Schuresko (8/6/2026 6:57 PM IDT)
• *Maths ForFun2 (10/6/2026 9:19 AM IDT)