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

Author

Benoit Cloitre, Oct 04 2003

Keywords

• nonn

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).

Examples

			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.
		

Crossrefs

Same as A059975 apart from offset.

Programs

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)

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.