A140656 Arises in a simple, polynomial-time algorithm for the matrix torsion problem.

1, 3, 40322, 6402373705728003, 263130836933693530167218012160000004, 30414093201713378043612608166064768844377641568960512000000000005, 61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000006

Offset

0,2

Comments

Nicolas, Corollary 1, p.4, cites Mandel and Simon, Lemma 4.1: let d be in N^*, then every d x d torsion matrix M satisfies M^((2*d^2)! + d) = M^d.

Abstract: The Matrix Torsion Problem (MTP) is: given a square matrix M with rational entries, decide whether two distinct powers of M are equal. It has been shown by Cassaigne and the author that the MTP reduces to the Matrix Power Problem (MPP) in polynomial time: given two square matrices A and B with rational entries, the MTP is to decide whether B is a power of A. Since the MPP is decidable in polynomial time, it is also the case of the MTP. However, the algorithm for MPP is highly nontrivial. The aim of this note is to present a simple, direct, polynomial-time algorithm for the MTP.

Links

Table of n, a(n) for n=0..6.

Francois Nicolas, A simple, polynomial-time algorithm for the matrix torsion problem, arXiv:0806.2068

Formula

a(n) = (2*n^2)! + n = A000142(2*A000290(n)) + n = A000142(A001105(n)) + n.

Example

a(0) = (2*0^2)! + 0 = 1.
a(1) = (2*1^2)! + 1 = 3.
a(2) = (2*2^2)! + 2 = 40322.
a(3) = (2*3^2)! + 3 = 6402373705728003.
a(4) = (2*4^2)! + 4 = 263130836933693530167218012160000004.

Crossrefs

Cf. A000142, A000290, A001105.

Sequence in context: A086509 A068161 A116313 * A135760 A003541 A086829

Adjacent sequences: A140653 A140654 A140655 * A140657 A140658 A140659

Keyword

easy,nonn

Author

Jonathan Vos Post, Jul 10 2008

Status

approved