This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A384197 #11 Jun 06 2025 14:46:18 %S A384197 4,8,5,16,12,10,9,32,28,25,23,21,19,18,17,64,60,56,53,51,48,46,44,42, %T A384197 40,39,37,36,35,34,33,128,124,120,117,113,110,107,105,102,99,97,95,93, %U A384197 91,89,87,85,83,81,80,78,77,75,74,73,71,70,69,68,67,66,65,256 %N A384197 The Barret reducer reciprocal mod n. %C A384197 The aim of the Barret reducer is to compute x_i mod n for multiple i in an efficient manner in commodity hardware. %C A384197 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. %C A384197 This sequence contains no fixed points. %H A384197 Paolo Xausa, <a href="/A384197/b384197.txt">Table of n, a(n) for n = 1..8191</a> %H A384197 Wikipedia, <a href="https://en.wikipedia.org/wiki/Barrett_reduction">Barret reduction</a>. %F A384197 a(n) = floor(4^k / n) where k = floor(log_2(n))+1. %F A384197 a(2^j) = 2^(j+2). %F A384197 a(2^j-1) = A143096(j+1). %e A384197 For n = 97, a(97) = 168 because: k = floor(log_2(97))+1 = 6, so a(97) = floor((4^6) / 97) = 168. %e A384197 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. %t A384197 A384197[n_] := Floor[4^BitLength[n]/n]; Array[A384197, 100] (* _Paolo Xausa_, Jun 05 2025 *) %o A384197 (Python) %o A384197 a = lambda n: (1 << (n.bit_length() << 1)) // n %o A384197 print([a(n) for n in range(1,65)]) %Y A384197 Cf. A070939, A143096. %K A384197 nonn,easy %O A384197 1,1 %A A384197 _Darío Clavijo_, May 21 2025