Digital Services        F A Q


Some Mysteries of Multiplication, and How to Generate Random Factored Integers

Dept. of Computer Science (February 6, 2015)

SEMINAR SERIES : Distinguished lecture

MAJOR SPEAKER : Brent, Richard
LENGTH : 62 min.
ACCESS : Open to all
SUMMARY : Let M (n) be the number of distinct entries in the multiplication table for integers smaller than 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 algorithms for computing M (n) exactly for moderate values of n, and 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. This is joint work with Carl Pomerance.  [Go to the full record in the library's catalogue]

  ●  Persistent link:
  ●  XML Dublin Core code for metadata harvesting

Recommended for You

This video is presented here with the permission of the speakers. Any downloading, storage, reproduction, and redistribution are strictly prohibited without the prior permission of the respective speakers. Go to Full Disclaimer.

  For enquiries, please contact Digital and Multimedia Services Section

© 2009-2023 All rights reserved