cp's OEIS Frontend

Slabs on the sidewalk are numbered n = 0, 1, 2,... and each has a label L(n) = 1, 1, 2, 2, 3, 3,...

At a given slab, a jump can be taken forward or backward by L(n) places (but not back before slab 0).

.

For every n >= 0,

let L(n) = 1 + floor(n/2) -- the label on slab n,

let forward(n) = n + L(n) -- jumping forward,

if n > 0, let backward(n) = n - L(n) -- jumping backward,

let lambda(n) = floor((2/3)*n),

let mu(n) = 1 + 2*n,

let nu(n) = 2 + 2*n.

Observe that given n >= 0, there are exactly two ways of landing onto slab n with a direct jump backwards:

backward-jumping from mu(n) to n, and

backward-jumping from nu(n) to n.

If n is a multiple of 3, there is no other ways of jumping onto slab n. But if n is not a multiple of 3, there is one additional way:

forward-jumping from lambda(n) to n.

(Note that L is A008619, forward(n) == A006999(n+1), lambda is A004523, mu is A005408, nu is A299174.)

.

Every slab n > 0 is reachable from slab 0, since there always exists some slab s < n which reaches n by one or more jumps:

if n != 0 (mod 3), then s = lambda(n) = floor((2/3)*n) takes one forward jump to n,

if n == 0 (mod 3) but n != 0 (mod 9), then s = lambda o lambda o mu(n) = floor((8/9)*n) takes two forward jumps and one backward jump to n,

if n == 0 (mod 9), then s = lambda o lambda o nu(n) = floor((8/9)*n + 6/9) takes two forward jumps and one backward jump to n.

This demonstrates that the sequence never stops.

This also gives the following bounds:

a(n) <= 1 + (4/3)*n,

a(n) <= 6*log(n)/log(9/8).

.

The sequence is a surjective mapping N -> N, since given any n >= 0:

a(forward^n(0)) == n.

For n a nonnegative integer, a(n) is the smallest nonnegative integer i such that A359005(i) == n.

In fact, if a(n) exists, it is actually the unique nonnegative integer i such that A359005(i) == n. ({A359005(n)} is demonstrably an injective mapping from the nonnegative integers onto themselves.)

It is conjectured that a(n) exists for all nonnegative n. This has been verified true with a computer for all n < 7884654. This would make {a(n)} a one-to-one mapping from the nonnegative integers onto themselves.

The Jane Street greedy walk is obtained by starting on slab 0 of Jane Street's infinite sidewalk (see A358838) and always jumping backwards preferably than forwards. Also, it is forbidden to visit a slab more than once.

The sequence is well defined. It demonstrably never ends and never repeats.

It is conjectured that the sequence actually visits all nonnegative integers. This is related to the conjecture that given any positive integer n, there exists a minimal Jane Street's path (i.e., with minimal number of jumps) going from slab 0 to slab n, and ending either in "forwards" or in "forwards-forwards-backwards". This would make the sequence a one-to-one mapping of the nonnegative numbers onto themselves. See also A359008.

The Tiefenbruck sequence represents a strategy for the game of countably infinitely many hats. This strategy is conjectured to be one of several optimal strategies.

The rules of the game are as follows: two players each have countably infinitely many hats put on their heads. Each hat is either black or white with equal probability; furthermore, the players are only able to see the hats on the other player's head; simultaneously both players guess and point to a hat on their own head; they win if both pick out a white hat.

One would think that the maximum probability of winning the game is 1/4 -- and indeed the probability of winning is 25% if both players (e.g.) always choose the first hat on their own head. However, better results can be achieved if the players agree on a common strategy.

For example, if both players choose the position of the first black hat on the other player's head, then the probability of success is 1/3. Loosely speaking, this "first black hat" strategy corresponds to A007814 -- in a sense that will be made clearer later on.

Interestingly, choosing the position of the first white hat on the other player's head also results in a probability of success of 1/3. Loosely speaking, this "first white hat" strategy corresponds to A007814, with an added leading -1.

Actually it is possible to achieve a probability of success of 7/20 (35%) using the Tiefenbruck strategy described here, the Carter and Reyes strategy described in A345255, or variations thereof. Also it is an open problem whether strategies can achieve results better than 7/20.

The Tiefenbruck strategy is defined using a cellular automaton specified in the link "Infinitely Many Hats" below. The cellular automaton is fed with the sequence of hats on the other player's head, identifying each black hat with digit 0 and each white hat with digit 1. When (if) it completes, the automaton outputs the position of the hat the player should point to on their own head. Assuming a Baire/Borel measure for the universe of possible hat configurations, then the automaton almost always completes and the probability of success is indeed 7/20.

Now a(n) is defined as the output of the Tiefenbruck cellular automaton when fed with index n -- n being interpreted as the infinite stream of zeros and ones of its binary representation, starting from the least significant bit -- or as -1 if the automaton does not complete with the given infinite stream.

The "Towers of hats" and "Infinitely Many Hats" links below provide a formal exposition of the game of hats and a calculation of the probability of success.

The Carter and Reyes sequence represents a strategy for the game of countably infinitely many hats. This strategy is conjectured to be one of several optimal strategies.

The rules of the game are as follows: two players each have countably infinitely many hats put on their heads. Each hat is either black or white with equal probability; furthermore, the players are only able to see the hats on the other player's head; simultaneously both players guess and point to a hat on their own head; they win if both pick out a white hat.

One would think that the maximum probability of winning the game is 1/4 -- and indeed the probability of winning is 25% if both players (e.g.) always choose the first hat on their own head. However, better results can be achieved if the players agree on a common strategy.

For example, if both players choose the position of the first black hat on the other player's head, then the probability of success is 1/3. Loosely speaking, this "first black hat" strategy corresponds to A007814 -- in a sense that will be made clearer later on.

Interestingly, choosing the position of the first white hat on the other player's head also results in a probability of success of 1/3. Loosely speaking, this "first white hat" strategy corresponds to A007814, with an added leading -1.

Actually it is possible to achieve a probability of success of 7/20 (35%) using the Carter and Reyes strategy described here, the Tiefenbruck strategy described in A345257, or variations thereof. Also it is an open problem whether strategies can achieve results better than 7/20.

The Carter and Reyes strategy is defined using the cellular automaton specified in the link "Infinitely Many Hats" below. The cellular automaton is fed with the sequence of hats on the other player's head, identifying each black hat with digit 0 and each white hat with digit 1. When (if) it completes, the automaton outputs the position of the hat the player should point to on their own head. Assuming a Baire/Borel measure for the universe of possible hat configurations, then the automaton almost always completes and the probability of success is indeed 7/20.

Now a(n) is defined as the output of the Carter and Reyes cellular automaton when fed with index n -- n being interpreted as the infinite stream of zeros and ones of its binary representation, starting from the least significant bit -- or as -1 if the automaton does not complete with the given infinite stream.

The "Towers of hats" and "Infinitely Many Hats" links below provide a formal exposition of the game of hats and a calculation of the probability of success.