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,4

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

Links

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

Wikipedia, Faro shuffle.

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

Example

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

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

Crossrefs

Cf. A002326, A003558, A137604.

Sequence in context: A057899 A210200 A119989 * A375570 A328728 A242348

Adjacent sequences: A137602 A137603 A137604 * A137606 A137607 A137608

Keyword

nonn

Author

Yasutoshi Kohmoto, Apr 23 2008

Extensions

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

Edited by Max Alekseyev, Dec 09 2017

Status

approved