A087656 Let f be defined on the rationals by f(p/q) =(p+1)/(q+1)=p_{1}/q_{1} where (p_{1},q_{1})=1. Let f^k(p/q)=p_{k}/q_{k} where (p_{k},q_{k})=1. Sequence gives least k such that p_{k}-q_{k} = 1 starting at n.

1, 2, 2, 4, 3, 6, 3, 4, 5, 10, 4, 12, 7, 6, 4, 16, 5, 18, 6, 8, 11, 22, 5, 8, 13, 6, 8, 28, 7, 30, 5, 12, 17, 10, 6, 36, 19, 14, 7, 40, 9, 42, 12, 8, 23, 46, 6, 12, 9, 18, 14, 52, 7, 14, 9, 20, 29, 58, 8, 60, 31, 10, 6, 16, 13, 66, 18, 24, 11, 70, 7, 72, 37, 10, 20, 16, 15, 78, 8, 8, 41, 82

Offset

3,2

Comments

Proof that this is the same as A059975 except for offset, from Joseph Myers, Feb 21 2004. Claim: a(n+1) = A059975(n). If p is the least prime factor of n then the rule here gives (n+1)/1 -> (n+2)/2 -> ... -> (n+p)/p = (n/p + 1)/1 so a(n+1) = a(n/p + 1) + (p-1) and clearly A059975(n) = A059975(n/p) + (p-1). The natural start for the induction is A059975(1) = a(2) = 0 (one place before the currently listed sequences start).

Links

Table of n, a(n) for n=3..84.

Formula

If p is prime a(p+1)=p-1; it appears that a(n)=(n-1)/2 iff n is in A079148 or in A053177.

Example

6 -> (6+1)/(1+1) = 7/2 -> (7+1)/(2+1) = 8/3 -> (8+1)/(3+1) = 9/4 -> (9+1)/(4+1) = 2/1 and 2-1 = 1 hence a(6) = 4.

Prog

(PARI) a(x)=if(x<0, 0, c=0; while(abs(numerator(x)-denominator(x)-1)>0, x=(numerator(x)+1)/(denominator(x)+1); c++); c)

Crossrefs

Same as A059975 apart from offset.

Sequence in context: A257010 A156864 A059975 * A122811 A089173 A126090

Adjacent sequences: A087653 A087654 A087655 * A087657 A087658 A087659

Keyword

nonn

Author

Benoit Cloitre, Oct 04 2003

Status

approved