|
%I #16 Feb 27 2023 13:37:42
%S 7,21,23,25,29,31,39,47,49,53,55,61,63,71,81,89,91,93,95,97,99,101,
%T 103,107,111,115,119,121,123,125,127,137,147,161,169,181,183,199,201,
%U 207,213,223,225,233,235,237,239,243,251,253,259,273,281,285,313,315,323
%N Odd numbers z by which not all integers y, 0 <= y < 2^64, can be divided using "high multiplication" followed by a right shift.
%C For many odd numbers z, it is possible to compute the integer division of y / z for 0 <= y < 2^64 (that is, floor(y/z)) by multiplying by a suitable constant a and shifting right: floor((a*y)/(2^(64+e))). a is computed as a = ceiling((2^(64+e))/z), where e is such that 2^e < z < 2^(e+1).
%C Knuth showed that the formula floor((a*y)/(2^(64+e))) = floor(y/z) holds for all y, 0 <= y < 2^64, if and only if it holds for the single value y = 2^64 - 1 - (2^64 mod z).
%C There are 189 odd divisors z less than 1000 for which this method cannot be used to find the division result for all y, 0 <= y < 2^64.
%D Donald Ervin Knuth, The Art of Computer Programming, fascicle 1, _MMIX_. Addison Wesley Longman, 1999. Zeroth printing (revision 8), 24 December 1999. Exercise 19 in section 1.3.1', page 25 and the answer on page 95.
%H Donald E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/fasc1.ps.gz">The fascicle as a compressed PostScript file</a>
%e For the first term in the sequence, 7, floor(ay/(2^(64+e))) = 2635249153387078802 for y = 2^64 - 1 - (2^64 mod z) = 18446744073709551613, while floor(y/z) = 2635249153387078801.
%e Example for a term not in the sequence: for 9, both floor(ay/(2^(64+e))) and floor(y/z) are 2049638230412172400 for y = 2^64 - 1 - (2^64 mod z) = 18446744073709551608.
%K nonn
%O 0,1
%A _Philip Newton_, Dec 22 2000
%E Name corrected by _Boon Suan Ho_, Feb 27 2023
|
