Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 426.10048
Autor: Erdös, Paul; Pomerance, Carl
Title: Matching the natural numbers up to n with distinct multiples in another interval. (In English)
Source: Indag. Math. 42, 147-161 (1980).
Review: Let m and n be positive and let f(n,m) denote the least integer so that in (m,n+f(n,m)] there are distinct integers a1,...,an such that i| ai for i = 1,2,... n. The authors study the function f(n,m) and in particular the function f(n) defined by f(n) = n+f(n,n). They establish some nice results on f(n,m) and we state some of them. Theorem 2. For n \geq 3, f(n) \geq (2e- ½ +o(1))n(\frac{log n}{log log n}) ½ .
Theorem 3. Let r be the positive number satisfying e-r = r. Then
f(n) \leq (\frac{r ½ }{1-r}+o(1))n(log n) ½ . Theorem 4. For all positive integers m,n we have f(n,m) \leq 4n([n ½]+1). Theorem 5. Let \alpha = 1-(log(e log 2))(log 2)-1. Then
(L(n))-1summ = 1L(n)f(n,m) > n(log n)\alpha, (n > n0), where L(n) denotes the l.c.m. of 1,2,...,n and n0 is a certain numerical constant. Theorem 6. Let \beta = log(55/23-3/22-1). Then
(L(n))-1summ = 1L(n) f(n,m) \leq n\exp((\beta+o(1)) (\frac{log n}{log log n}). The proofs are fairly involved and a detailed study of the paper would be rewarding in the opinion of the reviewer. Some of the ideas involved in the proof are marriage theorem, some results of de Bruijn, some results of Tenenbaum.
Reviewer: K.Ramachandra
Classif.: * 11N37 Asymptotic results on arithmetic functions
Keywords: consecutive integers; Marriage theorem; de Bruijn's theorem; Tenenbaum's theorem
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag