A058525 Odd numbers z by which not all integers y, 0 <= y < 2^64, can be divided using "high multiplication" followed by a right shift.

7, 21, 23, 25, 29, 31, 39, 47, 49, 53, 55, 61, 63, 71, 81, 89, 91, 93, 95, 97, 99, 101, 103, 107, 111, 115, 119, 121, 123, 125, 127, 137, 147, 161, 169, 181, 183, 199, 201, 207, 213, 223, 225, 233, 235, 237, 239, 243, 251, 253, 259, 273, 281, 285, 313, 315, 323

Offset: 0

Author

Philip Newton, Dec 22 2000

Keywords

• nonn

Comments

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).

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).

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.

Examples

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

References

• 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.

Links

• Donald E. Knuth, The fascicle as a compressed PostScript file

Extensions

Name corrected by Boon Suan Ho, Feb 27 2023