• CARMA Special Semester in Computation and Visualisation
  • Speaker: Prof. Richard Brent, CARMA, The University of Newcastle
  • Title: Algorithms for the Multiplication Table Problem
  • Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Tue, 29th May 2018
  • To participate remotely, connect to the ViewMe meeting called "carmaspecial" (you can enter that name, or the meeting number 1689883675). This will be persistant for future talks in this series. The ViewMe client is free and you do not need an account. You can install ViewMe on a computer or phone to take part, or use the web interface (Firefox or Chrome) at https://viewme.ezuce.com/webrtc/?meetingID=1689883675. It's quite easy to use, but for assistance please contact Andrew.Danson@newcastle.edu.au. Some guides are available at https://viewme.ezuce.com/support/guides-tutorials/.
  • Abstract:

    Let $M(n)$ be the number of distinct entries in the multiplication table for integers smaller than $n$. More precisely, $M(n) := |\{ij \mid\ 0<= i,j <n\}|$. The order of magnitude of $M(n)$ was established in a series of papers by various authors, starting with Erdös (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).

    Bio: 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.

  • [Permanent link]