When I mentioned variance in the power supply I meant as a load was applied the voltage will drop.
From figure 8 in the Motorola LM317T datasheet it looks like there's almost a 2 volt drop between Vin and Vout at room temperature. That's in addition to the 1.25V drop across the current setting resistor. (I knew there was some reason why I don't use an LM317T for battery powered stuff.) So IMHO you should go with at least the 18V power supply.
Actually IMHO you'd be just as well off using a single resistor for each series of LEDs. It's cheaper, easier to put together, smaller, and just as efficient, since you want to drop just as many volts, one way or another, and your source voltage isn't going to steadily drop over time because it's not a battery.
FWIW the only way to get better efficiency would be to use pulse width modulation, but even then, if you were pulsing them at a current at which the LEDs don't make light efficiently, it's a lot of hassle and cost for no good return.
How long is a piece of string? How cool do you want them to run? How much do you want to spend on them? How big do you want them to be? I strongly endorse the KISS principle, hence using resistors.