Compute my Sacred Geometry

Question

In the tabletop RPG named Pathfinder, there is a feat that characters can take called Sacred Geometry, which allows a character who has it to buff their spells in exchange for doing some math: to use it, the character rolls a number of six-sided dice equal to their ranks in a particular skill, consults a table based on their spell level to determine which three prime numbers are the "Prime Constants" for that spell level, then calculates whether or not it's possible to produce one of the Prime Constants by performing some combination of addition, subtraction, multiplication, and division and parenthetical grouping on all the numbers rolled.

The table of Prime Constants by Spell Level are as follows:

+-------------+-----------------+
| Spell Level | Prime Constants |
+-------------+-----------------+
| 1st         | 3, 5, 7         |
| 2nd         | 11, 13, 17      |
| 3rd         | 19, 23, 29      |
| 4th         | 31, 37, 41      |
| 5th         | 43, 47, 53      |
| 6th         | 59, 61, 67      |
| 7th         | 71, 73, 79      |
| 8th         | 83, 89, 97      |
| 9th         | 101, 103, 107   |
+-------------+-----------------+

So, for instance, if a character has 5 skill ranks and they're casting a 4th level spell, they would roll five six-sided dice and would need to be able to calculate a value of 31, 37, or 41. If they rolled a 6, 6, 4, 3 and 1, then they could produce a value of 37 by performing the following computation: (6 × 6) + (4 – 3) × 1 = 37, or they could produce a value of 41 by doing ([6 + 6] × 3) + 4 + 1 = 41. As a result, their casting of the spell would succeed.

For this programming puzzle, your job is to write a function with two input parameters, Spell Level and Skill Ranks, roll a number of six-sided dice equal to the Skill Ranks parameter, then compute if you can produce (at least) one of the Prime Constants associated with the Spell Level parameter, then output a Boolean value.

Answers would be ranked primarily by the efficiency of their algorithm (I'm pretty sure that a brute force algorithm would scale very quickly as the Skill Ranks parameter increases), and then by the size of the submitted source code in bytes.

Answer 1

Python 2.7, 285 bytes

from itertools import*
from random import*
def f(s,r):
 p=[];n=1;k=1;P=1;d=choices('123456',k=r);D=permutations(d,r);O=product('+-*/',repeat=r-1)
 while-~s*3>n:p+=P%k*[k];n,k,P=n+P%k,k+1,P*k*k
 return any(n in{eval('int(%s)'%'%s'.join(i)%o)for i in D for o in O}for n in p[-4:-1])

Technically conforms to the specifications of the challenge. Only returns True/False, does not expose the dice rolls used or the expression used to caller.

Also, this algorithm ignores grouping, since we can perform the same operations without grouping by using ordering instead. (This would not be true if exponentiation was one of the possible operations, for example.)

Exponential runtime, since it generates all possibilities and then checks if at least one solution exists.