The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1<m<n$. Now compute $c\equiv m^d \pmod n$.

Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$.
$m \equiv c^3 \pmod n$<br>
$m \equiv c^{17} \pmod n$<br>
$m \equiv c^{65537} \pmod n$

If none of the above equations held you have two choices, based on the effort you're willing to spend and the probability that $e$ is rather small.

**If you suspect $e<\frac{1}{3}N^{\frac{1}{4}}$, then you should use Wiener's attack on small decryption exponent RSA with the lost public exponent taking the role of the decryption exponent to find. [Wikipedia explains the basics][1] and [Wiener's original attack.][2]**<br>
As Maarten points out in the comments below this attack is *very* fast and consumes moderate amounts of memory.

If you think / know that $e<2^{40}$ and/or you're not willing to implement Wiener's attack you can use the following approach, as you can always come back to Wiener's attack in case you think that you've tried long enough.<br>
The brute-force approach would work as follows ($i=3$, optimized using fgrieu's comment):

 1. Set $c_m \gets (c * c) \bmod n$,
 2. Check if $c \equiv m \pmod n$ or $c_m \equiv m \pmod n$, if the first holds, output 1, if the second holds, output 2.
 3. Set $c_3 \gets (c * c_m) \bmod n$
 4. Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
 5. Set $c_{i+2}\gets (c_i*c_m) \bmod n$, goto step 3

If you can not apply Wiener's attack and you consider brute-force "way too inefficient" there are still two methods left:

 1. Use your favorite factorization algorithm to factor $n$ and deduce $e$ from $(d,p,q)$
 2. Use your favorite discrete logarithm algorithm to solve $c^e \equiv m \pmod n$ for $e$.

  [1]: https://en.wikipedia.org/wiki/Wiener%27s_attack
  [2]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.5261&rep=rep1&type=pdf