Lewis Chen - cp's OEIS frontend

A377322 Number of cells that are a distance of n away in an order-5 hyperbolic square tiling.

1, 4, 12, 28, 64, 148, 340, 780, 1792, 4116, 9452, 21708, 49856, 114500, 262964, 603932, 1387008, 3185444, 7315788, 16801660, 38587200, 88620532, 203528596, 467429932, 1073513728, 2465464116, 5662259500, 13004116524, 29865647552, 68590349988, 157526673524

Offset: 0

Lewis Chen, Oct 24 2024

Also known as a {4,5} tiling.

The formula given in the MathOverflow answer (4 * A033303) is erroneous after n=3.

M. Lavrov, Description of the order-5 square tiling of the hyperbolic plane as a graph, MathOverflow
EC Puzzle Hunt, Solution: Tower Navigation
Index entries for coordination sequences.
Index entries for linear recurrences with constant coefficients, signature (2,0,2,-1).

Cf. A008574, A054888 (dual).

Vec((1 + 2*x + 4*x^2 + 2*x^3 + x^4)/(1 - 2*x - 2*x^3 + x^4) + O(x^31)) \\ Andrew Howroyd, Feb 12 2025

G.f.: (1 + 2*x + 4*x^2 + 2*x^3 + x^4)/(1 - 2*x - 2*x^3 + x^4). - Andrew Howroyd, Feb 12 2025

a(20) onwards from Andrew Howroyd, Feb 12 2025

A307909 Number of binary strings of length n whose only palindromic prefixes are "1" and "11".

Original entry on oeis.org

1, 1, 2, 3, 5, 8, 15, 27, 52, 99, 195, 382, 757, 1499, 2986, 5945, 11865, 23678, 47309, 94519, 188942, 377689, 755191, 1510000, 3019625, 6038493, 12076244, 24150989, 48300491, 96597996, 193193033, 386380121, 772754322, 1545496779, 3090981745, 6181939812

Offset: 2

Lewis Chen, May 04 2019

Obviously, any 1-length prefix will be palindromic. Without the 2-length prefix condition, there is only one such string for every length: 10, 100, 1000, etc. (A000012).

			a(5) = 3 because there are three such strings: 11000, 11001, and 11010. For example, 11100 is not such a string, because a prefix (111) is palindromic.

Cf. A000012, A006995.

a(2) = 1, a(3) = 1, a(2*k) = 2*a(2*k-1)-a(k+1)+a(k), a(2*k+1) = 2*a(2*k)-a(k+1)

A288533 Parse A004736 into distinct phrases [1], [2], [1,3], [2,1], [4], [3], [2,1,5], [4,3], [2,1,6], ...; a(n) is the length of the n-th phrase.

Original entry on oeis.org

1, 1, 2, 2, 1, 1, 3, 2, 3, 1, 3, 2, 1, 2, 2, 2, 1, 2, 4, 1, 1, 2, 3, 3, 2, 3, 5, 1, 3, 3, 3, 1, 1, 2, 2, 4, 3, 2, 3, 4, 4, 1, 3, 4, 4, 2, 1, 2, 2, 5, 5, 1, 2, 4, 3, 5, 1, 1, 2, 3, 4, 5, 2, 2, 3, 5, 5, 3, 1, 3, 3, 3, 4, 5, 1, 2, 2, 4, 5, 6, 1, 2, 4, 4, 6, 4, 1, 2, 3, 4, 4, 6, 2, 1, 2, 3, 3, 5, 5, 4, 1, 2, 3, 5, 6, 6, 1, 1, 2, 3, 4, 5, 7, 3, 2, 3, 4, 4, 7, 6, 1, 3, 3, 4, 5, 6, 5, 1, 2, 2

Offset: 1

Lewis Chen, Jun 11 2017

nonn

The phrases are formed by the Ziv-Lempel encoding described in A106182. - Neal Gersh Tolunsky, Nov 30 2023

			Consider the infinite sequence [1,2,1,3,2,1,4,3,2,1,5,4,3,2,1,...], i.e., A004736. We can first take [1] since we've never used it before. Then [2]. For the third term, we've already used [1], so we must instead take [1,3].

Neal Gersh Tolunsky, Table of n, a(n) for n = 1..10000

Cf. A109337, A106182, A187180, A187181, A187182, A187183, A187184, A187185, A187186, A187187, A187188, A187199, A187200.

# you should use program from internal format
a = set()
i = 2
s = "1"
seq = ""
while i < 100:
    j = i
    while j > 0:
        if s not in a:
            seq = seq + "," + str(len(s)-len(s.replace(",",""))+1)
            a.add(s)
            s = str(j)
        else:
            s = s + "," + str(j)
        j -= 1
    i += 1
print(seq[1:])

A286676 Numerators of the Nash equilibrium of guesses for the number guessing game for n numbers.

Original entry on oeis.org

1, 3, 9, 2, 20, 12, 23, 27, 31, 35, 187, 1461, 485, 105, 64, 69, 67, 18, 11, 41, 87, 23, 97, 828, 251175, 497650, 1582733, 480083, 3070955, 139927, 1253, 1301, 160, 83, 172, 89, 184, 181, 187, 193, 199, 205, 211, 217, 223, 229, 235, 241, 247, 253, 259, 265

Offset: 1

Lewis Chen, May 12 2017

Consider two players: one player picks a number between 1 and n, and another player guesses numbers, receiving feedback "too high" or "too low". The number picker is trying to maximize the expected number of guesses, whereas the number guesser is trying to minimize the expected number of guesses. While a binary search would in expectation be the optimal strategy if the number were chosen randomly, it is not the case if the number is chosen adversarially.

			a(n)/A286677(n): 1, 3/2, 9/5, 2, 20/9, 12/5, 23/9, 27/10, 31/11, 35/12, 187/62, 1461/470, 485/152, 105/32, 64/19, 69/20, 67/19, 18/5, 11/3, 41/11, 87/23, ...
For n=3, the Nash equilibrium of guesses is 9/5. This is attained when the number picker chooses 1 with 2/5 probability, 2 with 1/5 probability, and 3 with 2/5 probability. The number guesser guesses the numbers 0,2,1 in order with 1/5 probability, 2,0,1 in order with 1/5 probability, and 1,0,2 (i.e., binary search) with 3/5 probability.

R. Fokkink and M. Stassen, An Asymptotic Solution of Dresher's Guessing Game, Decision and Game Theory for Security, 2011, 104-116.
Robert Fokkink and Misha Stassen, Dresher's Guessing Game, conference presentation, 2011.
Michal Forisek, Candy for each guess, p. 15-19, IPSC 2011 booklet.
Michal Forisek, Candy for each guess.

For denominators see A286677.

More terms from Lewis Chen, Oct 29 2019

A286677 Denominators of the Nash equilibrium of guesses for the number guessing game with n numbers.

Original entry on oeis.org

1, 2, 5, 1, 9, 5, 9, 10, 11, 12, 62, 470, 152, 32, 19, 20, 19, 5, 3, 11, 23, 6, 25, 211, 63263, 123921, 389951, 117046, 741068, 33424, 296, 304, 37, 19, 39, 20, 41, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54

Offset: 1

Lewis Chen, May 12 2017

			For an example see A286676.

A286676 gives the numerators.

More terms from Lewis Chen, Oct 29 2019

cp's OEIS Frontend

User: Lewis Chen

A377322 Number of cells that are a distance of n away in an order-5 hyperbolic square tiling.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A307909 Number of binary strings of length n whose only palindromic prefixes are "1" and "11".

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A288533 Parse A004736 into distinct phrases [1], [2], [1,3], [2,1], [4], [3], [2,1,5], [4,3], [2,1,6], ...; a(n) is the length of the n-th phrase.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A286676 Numerators of the Nash equilibrium of guesses for the number guessing game for n numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A286677 Denominators of the Nash equilibrium of guesses for the number guessing game with n numbers.

Views

Author

Keywords

Examples

Crossrefs

Extensions