A137605 Consider the sequence: b(0) = n, and for k >= 1, b(k) = b(k-1)/2 if b(k-1) is even, otherwise b(k) = n - (b(k-1)+1)/2. Then a(n) = m, where m is the smallest index such that b(m) = 1.

0, 1, 1, 2, 2, 4, 5, 3, 3, 8, 5, 10, 9, 8, 13, 4, 4, 11, 17, 11, 9, 6, 11, 22, 20, 7, 25, 19, 8, 28, 29, 5, 5, 32, 21, 34, 8, 19, 29, 38, 26, 40, 7, 27, 10, 11, 9, 35, 23, 14, 49, 50, 11, 52, 17, 35, 13, 43, 11, 23, 54, 19, 49, 6, 6, 64, 17, 35, 33, 68, 45, 59, 13, 41, 73, 14, 23, 19, 25

Offset: 1

Author

Yasutoshi Kohmoto, Apr 23 2008

Keywords

• nonn

Comments

The first occurrence of the numbers 0, 1, 2, 3, 4, ... is at indices 1, 2, 4, 8, 6, 7, 22, 26, 10, 13, 12, 18, 1366, 15, 50, 386, ... - Robert G. Wilson v, May 15 2008

Examples

			6->3->4->2->1. So a(6)=4.
		

Links

• Robert G. Wilson v, Table of n, a(n) for n = 1..10000.
• Wikipedia, Faro shuffle.

Crossrefs

Cf. A002326, A003558, A137604.

Programs

Mathematica

f[n_] := Block[{lst = {n}, a}, While[a = lst[[ -1]]; a != 1, If[EvenQ@a, AppendTo[lst, a/2], AppendTo[lst, lst[[1]] - (a + 1)/2]]]; Length@ lst - 1]; Array[f, 79] (* Robert G. Wilson v, May 15 2008 *)

Formula

For n>2, if 2n-1 is in A014657, then a(n) = A002326(n-1)/2 - 1, otherwise a(n) = A002326(n-1) - 1. In particular, if A002326(n-1) is odd, then a(n) = A002326(n-1) - 1. - Max Alekseyev, May 21 2008, Dec 09 2017

For n>2, a(n) = A003558(n-1) - 1. - Joerg Arndt, Sep 12 2013

Extensions

More terms from Robert G. Wilson v, May 15 2008

Edited by Max Alekseyev, Dec 09 2017