A377279 Number of fixed points of f(k) = floor(k^2 / n) mod n^2.

1, 2, 3, 2, 3, 4, 3, 3, 4, 4, 3, 4, 3, 4, 5, 3, 4, 5, 2

Offset

1,2

Comments

The classic base-B "middle square" technique for generating pseudorandom numbers is to square a seed less than B^2, express it in base B, and extract the middle two digits for the next iterate.

This is a very bad technique: it has many short trajectories ending in fixed points or short cycles. This sequence records the number of fixed points.

Links

Table of n, a(n) for n=1..19.

Brian Hayes, The Middle of the Square, 2022.

Example

For n = 7, 30^2 = 900. Integer-divide this by 7 to get 128, which is 30 mod 49 (7^2). So 30 is a fixed point. Two other fixed points are 0 and 7, so A(7) = 3.

Prog

(Python)
def f(b):
    count = 0
    for n in range(b*b):
        val = ((n*n) // b) % (b*b)
        if n == val:
            count += 1
    return count

Crossrefs

Sequence in context: A325811 A324380 A123182 * A069464 A379017 A156723

Adjacent sequences: A377276 A377277 A377278 * A377280 A377281 A377282

Keyword

nonn

Author

Allan C. Wechsler, Oct 22 2024

Status

approved