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,1

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.

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

Table of n, a(n) for n=0..56.

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

Example

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.

Crossrefs

Sequence in context: A201072 A200935 A097182 * A219036 A063469 A155131

Adjacent sequences: A058522 A058523 A058524 * A058526 A058527 A058528

Keyword

nonn

Author

Philip Newton, Dec 22 2000

Extensions

Name corrected by Boon Suan Ho, Feb 27 2023

Status

approved