You are describing "generalization". Lookup Tables (LUT) can still be a valid technique if the problem space is small enough.

If you use a table for trigonometry functions then interpolation is generally used... So it doesn't have to be all-or-nothing.

Compression generally works by removing redundancy via some means or another according to some scheme... But compressed data can take up more space if it goes against the grain (i.e. RLE when the repeated byte is the same as escape byte). Randon number generators with simple seeds (not a hidden entropy pool) can be thought of as disrupting simple patterns in a sequence.

EDIT: just thought of this. http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html