Journal of Integer Sequences, Vol. 11 (2008), Article 08.4.5

Jumping Sequences

Steve Butler
Department of Mathematics
University of California, Los Angeles
Los Angeles, CA 90095

Ron Graham and Nan Zang
Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 92093


An integer sequence $a(n)$ is called a jump sequence if $a(1)=1$ and $1\leq a(n)<n$ for $n\geq 2$. Such a sequence has the property that $a^k(n)=a(a(\cdots(a(n))\cdots))$ goes to $1$ in finitely many steps. We call the pattern $(n,a(n),a^2(n),\ldots,a^\ell(n)=1)$ a jumping pattern from $n$ down to $1$. In this paper we look at jumping sequences that are weight minimizing with respect to various weight functions (where a weight $w(i,j)$ is given to each jump from $j$ down to $i$).

Our main result is to show that if $w(i,j)=(i+j)/i^2$, then the cost-minimizing jump sequence has the property that the number $m$ satisfies $m=a^q(p)$ for arbitrary $q$ and some $p$ (depending on $q$) if and only if $m$ is a Pell number.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000129 and A024581 .)

Received July 14 2008; revised version received October 6 2008. Published in Journal of Integer Sequences, October 18 2008.

Return to Journal of Integer Sequences home page