login
This site is supported by donations to The OEIS Foundation.

 

Logo


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 = ceil((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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 17 15:19 EST 2019. Contains 320220 sequences. (Running on oeis4.)