PARI/GP is easy to
use, fast, and powerful (freeware!) tool for number-theoretical
computations. As a rather frequent user of PARI/GP, I have developed
a number of advanced scripts that I would like to share with the
world. The most useful of them (at my humble opinion) are presented
at this page.
Development of these scripts in many cases was insprired by certain
computationally hard sequences in the On-line
of Integer Sequences (OEIS) and occasionally resulted in
extension of such sequences. Whenever appropriate I illustrate the
scripts usage with simple programs computing sequences in OEIS.
I welcome comments and suggestions regarding the scripts presented
at this page. In particular, please let
me know about:
bugs and miscalculations (a must to report!).
efficiency / performance concerns, both algorithmic and
practical. Please tell me if you know a way to speed up things
or a faster algorithm than currently implemented.
PARI/GP implementation issues including programming style,
your experience with these scripts. I would be pleased to know
if you found them applicable to a computational problem of your
interest (e.g., if they helped to extend a sequence in OEIS).
N.B. Some of the scripts planned for publication are not yet in a
publishable form, in which case only an announce is given. Please
email me, if you have an urgent need to try out a script that is
not yet present.
I. Number of Hamiltonian paths and cycles in graphs
hamiltonian.gp provides two functions nhp(A) and nhc(A) that compute the number
of Hamiltonian paths and cycles respectively in the graph defined by
the adjacency n × n matrix
A. The running time
complexity is 2n+O(log n) arithmetic
The underlying method is described in:
M. A. Alekseyev and G. P. Michon. "Making Walks Count: From Silent Circles to Hamiltonian Cycles".
In: J. Beineke, J. Rosenhouse (eds.) The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Volume 2, Princeton University Press, 2017, pp. 157–168.
ISBN 978-0-691-17192-0. doi:10.1515/9781400889136-012 doi:10.2307/j.ctt1s4773q.14 arXiv:1602.01396
invphi.gp provides two functions invphi(n) and numinvphi(n) computing all
and the number of such solutions respectively. While the
functionality of numinvphi(n) is
identical to length(invphi(n)),
the former is a bit faster.
valuation of binomial(n,k) with
respect to prime p
Notes. The input m is factored inside binocoprime(n,k,m) and that may
take time for large m. The
functionality of binoval(n,k,p)
is equivalent to valuation(binomial(n,k),p)
but the former does not compute binomial(n,k)
explicitly and takes only O(log(n))
ngs.gp provides the function numsubgrp(p,a) that for a prime
p and a vector a = [ a1, a2, ..., ak ] computes the number of
subgroups of the direct product of cyclic groups C(pa1) x
C(pa2) x ... x C(pak). It implements the formula
given in the paper: G. A. Miller, On
the Subgroups of an Abelian Group. The Annals of Mathematics, 2nd Ser. 6:1 (1904),
V. The Number of Self-Dual (Normal) Bases of GF(qm)
nsdb.gp provides two functions sd(m,q) and sdn(m,q) that compute
respectively the number of distinct self-dual and self-dual normal
bases of the finite field GF(qm) over GF(q).
The number q is a power of
prime in sd(m,q) and a
prime in sdn(m,q). This
script implements the formulae given in the paper: Dieter Jungnickel, Alfred J. Menezes, Scott A.
Vanstone, On the Number
of Self-Dual Bases of GF(qm) Over GF(q). Proceedings of the American
Mathematical Society 109:1 (1990), 23-29.
nseqadj.gp provides a function M(s) which, for a given k-dimensional vector s, computes the number of
linear sequences, consisting elements from k classes with s[i]
elements in the i-th
class, where every pair of adjacent elements are from distinct
classes. This script implements the formula given in the paper: L. Q. Eifler, K. B. Reid Jr., D. P. Roselle, Sequences with
adjacent elements unequal.
Aequationes Mathematicae 6:2-3 (1971), 256-262.
VII. Number of Monic Irreducible Multivariate Polynomials over
numirrpol.gp provides a function numirrpol(q,n,u) that counts
the number of monic irreducible polynomials in n variables over GF(q) of degree at most u. Namely, it returns a vector
of size u with the j-th component (j=1,2,...,u) equal to the
number of such polynomials of degree j.
The implementation is based on the formula that I derived and posted in Russian
forum in 2006. I also used it to contribute a whole bunch of related
sequences (A115457 .. A115505) to OEIS. While I viewed this formula
rather trivial and/or well-known, to my surprise the same formula
was recently published in:
A. Bodin, Number of irreducible polynomials in several
variables over finite fields. Amer. Math. Monthly
115 (2008), 653-660.
Interestingly, this publication even cites the sequence A115457 that I added
to OEIS back in 2006.