The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A058525 Numbers z by which not all integers y, 0 <= y < 2^64, can be divided using "high multiplication" followed by a right shift. 0
 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 (list; graph; refs; listen; history; text; internal format)
 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 Knuth, Donald Ervin, 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 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 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 15 10:51 EDT 2020. Contains 336492 sequences. (Running on oeis4.)