cp's OEIS Frontend

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

%I A377279 #12 Feb 06 2025 23:47:00
%S A377279 1,2,3,2,3,4,3,3,4,4,3,4,3,4,5,3,4,5,2
%N A377279 Number of fixed points of f(k) = floor(k^2 / n) mod n^2.
%C A377279 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 A377279 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 A377279 Brian Hayes, <a href="http://bit-player.org/2022/the-middle-of-the-square">The Middle of the Square</a>, 2022.
%e A377279 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 A377279 (Python)
%o A377279 def f(b):
%o A377279     count = 0
%o A377279     for n in range(b*b):
%o A377279         val = ((n*n) // b) % (b*b)
%o A377279         if n == val:
%o A377279             count += 1
%o A377279     return count
%K A377279 nonn
%O A377279 1,2
%A A377279 _Allan C. Wechsler_, Oct 22 2024