A324495 Average number of steps t(n) required to get n by repeatedly toggling one of the ceiling(log_2(n)) bits of the binary result of the previous step at a random position with equal probability of the bit positions, starting with all bits 0. The fractional part of t is given separately, i.e., t(n) = a(n) + A324496(n)/A324497(n).
1, 3, 4, 7, 9, 9, 10, 15, 18, 18, 20, 18, 20, 20, 21, 31, 37, 37, 40, 37, 40, 40, 41, 37, 40, 40, 41, 40, 41, 41, 42, 63, 74, 74, 78, 74, 78, 78, 80, 74, 78, 78, 80, 78, 80, 80, 82, 74, 78, 78, 80, 78, 80, 80, 82, 78, 80, 80, 82, 80, 82, 82, 83, 127, 147, 147, 153
Offset: 1
Keywords
Examples
a(5) = 9 is given by the sum of occurrence probabilities of toggle chains of even lengths 2*k, multiplied by the lengths.
a(5) = Sum_{k>=1} 4*k*7^(k-1) / 3^(2*k) = 9.
The corresponding simulation results for 10^10 toggle chains are
2*k Probability P 2*k*P Cumulated
2 0.22222334 0.44444668 0.444447
4 0.17284183 0.69136731 1.135814
6 0.13442963 0.80657780 1.942392
8 0.10455718 0.83645746 2.778849
10 0.08131600 0.81315998 3.592009
...
196 0.00000000 0.00000002 9.000068
.
a(7) = Sum_{k>=1} 2*(2*k+1)*7^(k-1) / 3^(2*k) = 10.
Links
- Hugo Pfoertner, Table of n, a(n) for n = 1..4096
- P. Diaconis, R. L. Graham, J. A. Morrison, Asymptotic Analysis of a Random Walk on a Hypercube with Many Dimensions, Technical Report EFS NFS 307, Department of Statistics, Stanford University, December 1988.
- Persi Diaconis, R. L. Graham, J. A. Morrison, Asymptotic analysis of a random walk on a hypercube with many dimensions", Random Structures & Algorithms, Volume 1, Issue 1, Pages 51-72, Spring 1990.
- IBM Research, Ponder This April 2006 - Challenge, Random walks on an n-dimensional hypercube.
- IBM Research, Ponder This April 2006 - Challenge, Solution.
Comments