## All HMC Faculty Publications and Research

Article

#### Department

Mathematics (HMC)

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 ) \sim C( \log n )^{1 + 1/\gamma }$ for certain constants $\gamma$ and $C$, in the sense that for any $\varepsilon > 0$, the inequality $f( n ) \leq ( C + \varepsilon )( \log n )^{1 + 1/\gamma }$ holds for infinitely many $n$, while$f( n ) \leq ( C + \varepsilon )( \log \,n )^{1 + 1/\gamma }$ holds for only finitely many. In fact, $\gamma = 0.7878 \ldots$ is the unique real solution of the equation $2^{ - \gamma } + 3^{ - \gamma } = 1$, and $C = 1.5595 \ldots$ is given by the expression $C = \left( {\gamma \left( {2^{ - \gamma } \log 2^\gamma + 3^{ - \gamma } \log 3^\gamma } \right)^{1/\gamma } /\left( {\gamma + 1} \right)\left( {15^{ - \gamma } \log ^{\gamma + 1} \frac{5}{2} + 3^{ - \gamma } \sum _{5 \leq k \leq 7} \log ^{\gamma + 1} \frac{k + 1}{1} + \sum _{8 \leq k \leq 15} \log ^{\gamma + 1} \frac{k + 1}{1}} \right)^{1/\gamma } } \right)$.

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 ) \sim C_0 ( \log \,x )^{1 + 1/\gamma }$, where $C_0 = 1.5586 \ldots$ is given by $C_0 = 6e ( 2^{ - \gamma } \log 2^{ - \gamma } + 3^{ - \gamma } \log 3^{ - \gamma } )^{1/\gamma } \left( {\gamma /\left( {\gamma + 1} \right)} \right)^{1 + 1/\gamma }$ and is smaller than $C$ by a factor of 0.9994... .

#### Rights Information

© 1995 Society for Industrial and Applied Mathematics

﻿

COinS