They recorded the whole response. "...and the second one simply writes down the response packets received." They also randomized the order in which they scanned so they might have needed to keep track of already scanned addresses. "Although we have sent just a single packet per IP, we messed the scans to prevent a network receiving a high number of consecutive packets."

You can use a LFSR[0] to efficiently (it is deterministic, minimal state) convert a sequential power of two range [0, 2^n-1] into one that appears to "randomly" walk around.

[0]: http://en.wikipedia.org/wiki/Linear_feedback_shift_register

Or just reverse the bits in the address.

Yeah, I could think of a handful of ways to do this easily without as much resources as stated...