If there’s no memory for that, do multiplication by 9/5 the way it’s done in Bresenham’s line algorithm (https://en.wikipedia.org/wiki/Bresenham's_line_algorithm). If you start at zero Celsius = 32 Fahrenheit, that’s 50 steps, at most. Might not be (much) smaller than a lookup table, though.
Precomputing the steps for each degree Celsius difference and storing each in a single bit (a one degree change in Celsius will increase degrees Fahrenheit by either 1 or 2) might be the most memory-efficient approach. For a 100 degree Celsius range that’s a 50 bits table (starting at the center of the range). Edit: even that may be too large. That table will repeat every 9 bits, so one byte almost is enough. It might be a struggle to make that a net gain, given the more complex conversion code, though.