A384197 The Barret reducer reciprocal mod n.

4, 8, 5, 16, 12, 10, 9, 32, 28, 25, 23, 21, 19, 18, 17, 64, 60, 56, 53, 51, 48, 46, 44, 42, 40, 39, 37, 36, 35, 34, 33, 128, 124, 120, 117, 113, 110, 107, 105, 102, 99, 97, 95, 93, 91, 89, 87, 85, 83, 81, 80, 78, 77, 75, 74, 73, 71, 70, 69, 68, 67, 66, 65, 256

Offset: 1

Author

Darío Clavijo, May 21 2025

Keywords

• nonn
• easy

Comments

The aim of the Barret reducer is to compute x_i mod n for multiple i in an efficient manner in commodity hardware.

The reciprocal is a(n) = floor(4^k / n), with k = floor(log_2(n))+1 such that for any x_i where q_i = (x_i * a(n)) >> (2 * k) and x_i - q_i * k is congruent to x_i mod n.

This sequence contains no fixed points.

Examples

			For n = 97, a(97) = 168 because: k = floor(log_2(97))+1 = 6, so  a(97) = floor((4^6) / 97) = 168.
As an example application, let some x=65537 and q = (x * a(n)) >> (2 * 6) = (65537 * 168) >> (2 * 6) = 353, then 353 % 97 = 65537 % 97, where ">>" denotes right shift.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..8191
• Wikipedia, Barret reduction.

Crossrefs

Cf. A070939, A143096.

Programs

Mathematica

A384197[n_] := Floor[4^BitLength[n]/n]; Array[A384197, 100] (* Paolo Xausa, Jun 05 2025 *)

Python

a = lambda n: (1 << (n.bit_length() << 1)) // n
print([a(n) for n in range(1,65)])

Formula

a(n) = floor(4^k / n) where k = floor(log_2(n))+1.

a(2^j) = 2^(j+2).

a(2^j-1) = A143096(j+1).