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

Author

Allan C. Wechsler, Oct 22 2024

Keywords

• nonn

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.

Examples

			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.
		

Links

• Brian Hayes, The Middle of the Square, 2022.

Programs

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