A377279 - OEIS

%I #17 Nov 08 2025 17:51:37

%S 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,

%T 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,

%U 5,10,4,6,3,4,4,5,5,9,5,5,2,4,2,8,4,4,4,5,6,8

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

%C 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.

%C 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.

%H Andrew Howroyd, <a href="/A377279/b377279.txt">Table of n, a(n) for n = 1..5000</a>

%H Brian Hayes, <a href="http://bit-player.org/2022/the-middle-of-the-square">The Middle of the Square</a>, 2022.

%e 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.

%o (Python)

%o def a(b):

%o     count = 0

%o     for n in range(b*b):

%o         val = ((n*n) // b) % (b*b)

%o         if n == val:

%o             count += 1

%o     return count

%o print([a(n) for n in range(1,91)])

%o (PARI) a(n) = sum(k=0, n^2-1, k^2\n % n^2 == k) \\ _Andrew Howroyd_, Nov 08 2025

%K nonn

%O 1,2

%A _Allan C. Wechsler_, Oct 22 2024

%E a(20) onward from _Andrew Howroyd_, Nov 08 2025