#### Document Type

Article

#### Department

Mathematics (HMC)

#### Publication Date

1995

#### Abstract

Define f on the integers n > 1 by the recurrence f(n) = min( n, min_{m|n}( 2f(m) + 3f(n/m) ). The function f has f(n) = n as its upper envelope, attained for all prime n.

The goal of this paper is to determine the corresponding lower envelope. It is shown that this has the form f(n) ~ C(log n)^{1 + 1/γ} for certain constants γ and C, in the sense that for any ε > 0, the inequality f(n) ≤ (C + ε)(log n)^{1 + 1/γ} holds for infinitely many n, while f(n) ≤ (C + ε)(log \,n )^{1 + 1/γ} holds for only finitely many. In fact, γ = 0.7878... is the unique real solution of the equation 2^{ -γ} + 3^{-γ} = 1, and C = 1.5595... is given by the expression C = ( γ( 2^{ -γ} log( 2^{γ}) + 3^{-γ} log( 3^{γ} ) )^{1/γ} / ( γ + 1)( 15^{-γ} log^{γ + 1}( 5/2 + 3^{-γ} ) ∑_{5 ≤ k ≤ 7} log^{γ + 1}((k + 1)/1) ∑_{8 ≤ k ≤ 15} log^{γ + 1} ((k + 1)/1) )^{1/γ} ).

This paper also considers the function f_{0} defined by replacing the integers n > 1 with the reals n > 1 in the above recurrence: f_{0}(x) = min{ x,inf_{1 < y < x} (2f_{0}(x/y) + 3f_{0}(x/y) }. The author shows that f_{0}(x) ~ C_{0}( log x )^{1 + 1/γ}, where C_{0} = 1.5586... is given by C_{0} = 6e( 2^{-γ} log 2^{-γ} + 3^{-γ} log 3^{-γ} )^{1/γ} ( γ /( γ + 1))^{1 + 1/γ} and is smaller than C by a factor of 0.9994... .

#### Rights Information

© 1995 Society for Industrial and Applied Mathematics

#### Recommended Citation

Nicholas Pippenger. "Analysis of a Recurrence Arising from a Construction for Nonblocking Networks", Society for Industrial and Applied Mathematics Journal of Discrete Mathematics, 8, 322 (1995).