##
**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 a_{1},...,a_{n} such that i| a_{i} 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))^{-1}**sum**_{m = 1}^{L(n)}f(n,m) > n(log n)^{\alpha}, (n > n_{0}), where L(n) denotes the l.c.m. of 1,2,...,n and n_{0} is a certain numerical constant. Theorem 6. Let \beta = log(5^{5/2}3^{-3/2}2^{-1}). Then

(L(n))^{-1}**sum**_{m = 1}^{L(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