I noticed what looked like a polynomial-looking lower bound for OEIS sequence A023094:
a(n) is least k such that k and 2k are anagrams in base n (written in base 10)."
I've conjectured that $\forall n > 1,\ A023094(3n - 1) = A000567(n) = 3n^2 - 2n$.
On this domain the following inequalities hold: $$3n - 1 \leq A000567(n) < (3n-1)^3$$ $$3n - 1 \leq A000567(n)\times 2 < (3n-1)^3$$
Therefore both $A000567(n)$ and $2 \times A000567(n)$ are two "digit" numbers in base-$(3n-1)$.
For example:
$$A023094(5) = 8 = 13_5\ (\text{and }16 = 31_5)$$ $$A023094(8) = 21 = 25_8\ (\text{and }42 = 52_8)$$ $$A023094(11) = 40 = 37_{11}\ (\text{and }80 = 73_{11})$$
I'm confident that $A000567(n)$ and $2 \times A000567(n)$ are anagrams in base-$(3n-1)$, but I don't know how to prove if they're minimal anagrams. (Heuristics suggest that they probably are minimal.)
Any ideas on how to prove or disprove this?
Also I'd be curious to hear thoughts on why this pattern appears for numbers of the form $3n - 1$, but not numbers of the form $3n$ or $3n + 1$.
Summary of results in this answer:
The case of $3n-1$
Since $3n^2-2n$ is a two-digit number base $3n-1$, with digits $(n-1),(2n-1)$, you can try to find a snaller two-digit answer:
$$2((3n-1)x+y)=(3n-1)y+x$$
Which gives $(6n-3)x = (3n-3)y$, or $(2n-1)x = (n-1)y$.
Since $n-1$ and $2n-1$ are relatively prime, this means that $x$ must be a multiple of $n-1$ and $y$ must be a multiple of $2n-1$.
So the smallest $2$-digit case is $3n^2-2n=(n-1)(3n-1)+(2n-1)$.
There are no $1$-digit examples.
If you try to solve for $3n$, you get:
$$2(3nx+y)=3ny + x$$ or $(6n-1)x = (3n-2)y$. $6n-1$ and $3n-2$ are relatively prime, so $y$ must be divisible by $6n-1$, which isn't possible.
So the reason $b=3n-1$ is "easy" is that there is a solution to $(2b-1)x=(b-2)y$ with $0\leq x,y<b$. There are never $2$-digit examples in base $b$ except when $b+1$ is divisible by $3$.
The problem gets messier with more than two digits, because you get several different possible permutations, and hence several equations.
Three digit cases
Trying the three-digit case, you get five possible equations, three of which will never have solutions (unless there was a two-digit solution.) So you want:
$$2(xb^2+yb+z)=yb^2+zb+x$$ or $$2(xb^2+yb+z)=zb^2+xb+y$$
So you need $$(2b^2-1)x=(b-2)(by+z)\tag{1}$$ or $$(2b-1)(bx+y)=z(b^2-2)\tag{2}$$
$(2)$ is easier, because, if $2b-1$ and $b^2-2$ are relatively prime, then then $z$ must be a multiple of $2b-1$. But we want $0\leq z\leq b-1$.
But we can show that $b^2-2$ and $2b-1$ can only have $7$ as a common factor, when $b=7n+4$. Then you want $$(2n+1)((7n+4)x+y)=(7n^2+8n+2)z$$
There is always a solution to this $x=n,y=4n+2,z=2n+1$. Since we can show $7n^2+8n+2$ and $2n+1$ are relatively prime, this is the smallest solution.
So we have that $$A023094(7n+4)\leq n(7n+4)^2+(4n+2)(7n+4)+(2n+1)=(7 n + 3) (7 n^2 + 9 n + 3) $$ when $n\geq 1$. (When $n=0,b=4$, the above gives the solution $2(021)_4=(102)_4$, which might or might not be considered a solution.)
If $n=3k+1$, then $7n+4=21k+11=3(7k+4)-1$, so by your previous observation, we have a two-digit answer.
When $n=2,3$, this bound is the actual value.
For $(1)$ we are going to use a trick, just because it generalizes.
Because the permutation we are current looking is a rotation, we can actually see this in terms of rational numbers in base $b$.
For example, if we have a three digit solution $A=(xyz)_b$ with $2(xyz)_b=(yzx)_b$ then consider the infinite base $b$ representation:
$$\alpha = (0.xyzxyz\overline{xyz})_b=\frac{(xyz)_b}{b^3-1}$$
Then we get that $$b\alpha - x = 2\alpha$$
So $\alpha=\frac{x}{b-2}$. So if $\frac{x}{b-2}=\frac{A}{b^3-1}$ The only time common divisors of $b-2$ and $b^3-1$ are $1$ and $7$.
The the only way for $\frac{x}{b-2}=\frac{A}{b^3-1}$ is if $\frac{x}{b-2}=\frac{x'}{7}$ for some $1\leq x'<7$. This requires $b=7n+2$ for some $n$, and we can always choose $x'=1$ and thus $x=n, \frac{1}{7}=\frac{A}{(7n+2)^3-1}=\frac{A}{7(7n+1)(7n^2 + 5n +1)}$ or $A=(7n+1)(7n^2+5n+1)$.
So for three digit examples, we get polynomial answers for $b=7n+2$ and $b=7n+4$ (when the values are not of the form $3m-1$.)
For four-digit and longer examples, it gets even harder. This rational trick only works for a small subset of the possible permutations. For example, the minimal answer for base $34$ is $n=(24(18)9)_{34}$, then $2n=(492(18))_{34}$ is a non-rotation permutation.
More generally, we can do the rational number trick if there is a solution to $\frac{X}{b^k-2}=\frac{A}{b^n-1}$ with $b^{k-1}\leq X<b^k/2$ then $A$ and $2A$ are $n$-digit anagrams. But that's a very limited type of anagram - a rotation of the digits.This might let us prove that $A000567$ has a value for every $b>2$.
For example, when $k=3,n=4$ we need $b^3-2$ and $b^4-1$ to have a common factor. But $b^4-1-(b^3-2)b=2b-1$, and if $d\mid b^4-1$ and $d\mid 2b-1$ then $d\mid 2^4-1=15$. So if $2b-1$ is divisible by $3$ or $5$, but when $2b-1$ is divisible by $3$ then $b=3n-1$ for some $n$, so we can skip that case. So we need $b=5n+3$. Then $A=\frac{b^4-1}{5}$. For example, when $b=13$ you get an anagram $5712=(27(10)5)_{13}$, which is, according to OEIS, the smallest.
$b=18,23$ are covered by the $7n+4$ and $3n-1$ cases, respectively, but when $b=28$, $A=\frac{28^4-1}{5}=122931$ gives the minimum anagram.
In the case $k=1$, you want $b-2$ and $b^n-1$ to have a common factor, $p$, then $p$ must be a factor of $2^n-1$ and $b-2$. So pick an odd prime factor $p$ of $b-2$ and $n=p-1$. Then $\frac{1}{p}=\frac{A}{b^{p-1}-1}$ gives a solution $A$.
So any $b$ with $b-2$ having an odd prime factor $p$ has an upper bound of $\frac{1}{2}b^{b-3}$.
The case where $b-2$ is a power of $2$ can't be done this way, because $b-2$ and $b^n-1$ are relatively prime in that case, but you can apply the same trick, finding an odd prime factor $p$ of $b^2-2$ less than $b$, which we can do. Then $n=2(p-1)$ and $\frac{1}{p}=\frac{A}{b^n-1}$ gives a solution.
You can get better upper bounds for specific examples. For example, when $b=91$, one of the cases where brute force found no five-digit answers, we see that $b^2-2$ is divisible by $17$ and $2^{8}-1$ is divisible by $17$, so $A=\frac{91^{16}-1}{17}$ is a 16-digit solution.
If $b\equiv 2\pmod{5}$ then $b^4-1$ is divisible by $5$ and $A=\frac{b^4-1}{5}$.
(The case we found above, where $b\equiv 3\pmod 5$ is due to $b^3-2$ is divisible by $5$.)
It's worth noting that $b-1$ is always a divisor of any number such that $n$ and $2n$ are anagrams in base $b$. That's because the anagram property means that $n\equiv 2n\pmod{b-1}$.
Additional cases:
If $b=3n$ then $((n-1)(2n-1)(2n)(n))_b$ is an anagram.
If $b=7n$ then $((n)(2n)(3n-1)(5n-1)(6n-1)(4n))_b$ is an anagram.
If $b=7n-1$ then $((n-1)(4n-1)(2n-1)(5n-1)(3n-1)(6n-1))_b$ is an anagram.
If $b=7n+3$ then $((n)(2n)(4n+1)(6n+2)(5n+2)(3n+1))_b$ is an anagram.
If $b=7n-2$ then $((n-1)(4n-2)(5n-2)(6n-1)(2n-1)(3n-1))_b$ is an anagram.
If $b=15n+4$ then $((n)(2n)(8n+2)(4n+1))_b$ is an anagram.
This means we can quickly find six-digit or smaller examples unless $b\equiv 1\pmod {21}$, and any case with $b\equiv 2,3,4\pmod{5}$.
There is actually a six-digit or smaller anagram if $b\not\equiv 1\pmod{315}$. Might be necessary and sufficient - I haven't found an example for $b=316$ smaller than $7$ digits.