Consider primes of the form
$$\frac{a^n + 1}{a+1}$$
for integer $a>1$ and integer $n>1$.
Conjecture :
(for any fixed $a$)
The smallest prime of the form $\frac{a^n + 1}{a+1}$ has $ 1 < n < a^2$.
This true for $a=2$ or small $a$ and it seems to hold even for large $a$.
For instance the primes
$$521 = \frac{5^5 + 1}{6}$$
$$1824841 = \frac{37^5 + 1}{38}$$
$$530713 = \frac{729^3 + 1}{730}$$
Now this might be hard to prove ofcourse considering the open conjectures surrounding these numbers and assuming I did not miss a trivial thing like modular arithmetic.
So my main question is rather : how much can the conjecture be sharpened ?
Can we say
The smallest prime of the form $\frac{a^n + 1}{a+1}$ has $ 1 < n < a + 2$ or
The smallest prime of the form $\frac{a^n + 1}{a+1}$ has $ 1 < n < p(a)$ where $p(a)$ is the $a$ th prime.
or such ?
Let us denote $f(a)$ for the lowest bound.
From the example above I got $f(a) = a$ (the case with $a = 5$) for $a>2$ and $f(2) = 3$
I ran a check for $a$ from $2$ to $100$ and here are some cases of interest. Note that I only checked for $n<1000$ (some extended to $n<2000$). Also, note that $n$ must be odd for $x=(a^n+1)/(a+1)$ to be an integer. It must also be prime, otherwise $x$ will be composite as $a^p+1$ divides $a^n+1$ if $p|n$, and so $(a^p+1)/(a+1)$ is a nontrivial factor.
If $a=r^k$ for some odd $k$, we can factor $a^n+1=(r^n+1)(r^{(k-1)n}-\cdots-r^n+1)$. For $n>k$, both terms of the product are greater than $a+1$, and so $x=(r^{kn}+1)/(r^k+1)$ must be composite, as Aurel-BG and Calvin Lin have both pointed out. However, there may be solutions for $a=r^p$ for which $n=p$ is the only possible solution: see addition at the end.
Apart from the odd powers $a=8,27,32,64$, I found no prime for $a=53,97$, but Aurel-BG found $(53^{21943}+1)/54$ to be the smallest for $a=53$, and my guess is that there will exist one for $a=97$ as well.
In most cases, a prime is found for low $n$, but there are some notable exceptions for which $n>a$: $(a,n)=(30,139)$, $(31,109)$, $(40,53)$, $(45,103)$, $(50,1153)$, $(53,21943)$, $(68,757)$, $(82,293)$, $(87,167)$, $(88,709)$.
The prime density around numbers of size $x$ is $\sim 1/\ln x$, which for $x=(a^n+1)/(a+1)$ is $\sim 1/n\ln a$. Summing this expected prime density over all odd $n$ gives an infinite sum which is an argument in favour of there being infinitely many primes on that form, but also that if none is found for low $n$ the first $n$ may be very high. This is true even if you add the constraint that $n$ be prime.
I checked for solutions on the form $a=r^p$ for prime $p$. For $x$ to be prime, the only option is $n=p$. However, there seems to be lots of such cases. The poster already had $a=729=9^3$ included, and from computational test I find a lot and would not be surprised if there are an infinite number of them.
I started a search, the first hit being $a=6^3, n=3$, and the largest found so far being $a=601^{29}, n=29$.