Let M(n) be the number of distinct entries in the multiplication table for integers smaller than n. More precisely, M(n) := |{ij |0<=i, j <=}|.
The order of magnitude of M(n) was established in a series of papers by various authors, starting with Erdos (1950) and ending with Ford (2008), but an asymptotic formula for M(n) is still unknown. After describing some of the history of M(n) I will consider two algorithms for computing M(n) exactly for moderate values of n, and several Monte Carlo algorithms for estimating M(n) accurately for large n. This leads to consideration of algorithms, due to Bach (1985–88) and Kalai (2003), for generating random factored integers — integers r that are uniformly distributed in a given interval, together with the complete prime factorisation of r. The talk will describe ongoing work with Carl Pomerance (Dartmouth, New Hampshire) and Jonathan Webster (Butler, Indiana).
Richard Brent is a graduate of Monash and Stanford Universities. His research interests include analysis of algorithms, computational complexity, parallel algorithms, structured linear systems, and computational number theory. He has worked at IBM Research (Yorktown Heights), Stanford, Harvard, Oxford, ANU and the University of Newcastle (NSW). In 1978 he was appointed Foundation Professor of Computer Science at ANU, and in 1983 he joined the Centre for Mathematical Analysis (also at ANU). In 1998 he moved to Oxford, returning to ANU in 2005 as an ARC Federation Fellow. He was awarded the Australian Mathematical Society Medal (1984), the Hannan Medal of the Australian Academy of Science (2005), and the Moyal Medal (2014). Brent is a Fellow of the Australian Academy of Science, the Australian Mathematical Society, the IEEE, ACM, IMA, SIAM, etc. He has supervised twenty PhD students and is the author of two books and about 270 papers. In 2011 he retired from ANU and moved to Newcastle to join CARMA, at the invitation of the late Jon Borwein.
Host University: The University of Newcastle
Seminar Convener: Professor Richard Brent (University of Newcastle)
1. Book your University’s Access Grid Room, or a university or APAC etc. Access Grid Room that you are able to use, and
2. Send an email to the seminar convener at the University of Newcastle (Richard Brent) to advise that you will be attending the seminar.