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, 4, 4, 4, 2, 4, 4, 6, 2, 4, 2, 10, 2, 3, 5, 7, 5, 4, 2, 4, 5, 4, 2, 8, 3, 5, 4, 5, 2, 4, 2, 5, 4, 5, 3, 4, 6, 4, 4, 5, 3, 8, 5, 6, 4, 4, 5, 8, 4, 4, 5, 10, 4, 6, 3, 4, 4, 5, 5, 9, 5, 5, 2, 4, 2, 8, 4, 4, 4, 5, 6, 8

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

Andrew Howroyd, Table of n, a(n) for n = 1..5000

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 a(b):
    count = 0
    for n in range(b*b):
        val = ((n*n) // b) % (b*b)
        if n == val:
            count += 1
    return count
print([a(n) for n in range(1, 91)])
(PARI) a(n) = sum(k=0, n^2-1, k^2\n % n^2 == k) \\ Andrew Howroyd, Nov 08 2025

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

Extensions

a(20) onward from Andrew Howroyd, Nov 08 2025

Status

approved