I am currently writing my master's thesis at Cal Poly Pomona, and am currently investigating the ruler sequence for a prime base.
The ruler sequence for base $2$ is : $0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,...$ that is the power of 2 which strictly divides a positive integer $n$. Since my research involves a more general form (usually prime base) we can make the appropriate generalization:
$$p^{r_p(n)}||n$$
The first thing to note is that $r_p(n)=ord_p(n)$ where $ord_p(n)$ is the the p-adic oridinal or valuation of $n$ (Since I am also considering the order of $n$ modulo $p^k$, I want to stay away from the latter notation).
Now I am currently using a rather inefficient method to calculate $r_2(n)$, but it is concise; meaning that I can use a spread sheet program to rapidly output tables for analysis. The formula is as follows: $$r_p(n)=\log_p(\gcd(n,p^{\lfloor\log_p(n)\rfloor})),$$
The above is efficient enough to find values for small $n$, but in examining $r_p(n^a-1)$ I run into issues involving the efficiency of my formula. Note: $a$ is a positive integer and $n>1$.
I was wondering if anyone knew of, or could point me in the direction of, a more efficient, and ideally direct, method to compute the p-adic ordinal of $n^a-1$ for relatively small values of $n$.
The following method is probably pretty well known. I’ll use the notation $v_p(n)$ instead of your $\text{ord}_p(n)$.
Of course you know that if $p|n$ then $v_p(n^\alpha-1)=0$ for all positive $\alpha$, so we don’t need to worry about numbers $n$ divisible by $p$. For a number $n$ prime to $p$, though, I’ll call $\omega_p(n)$ the smallest positive power of $n$ for which $n^\omega\equiv1\pmod p$. It’s a divisor of $p-1$, and all divisors of $p-1$ occur. Now you see that if $\omega_p(n)$ does not divide $\alpha$, then $v_p(n^\alpha-1)=0$. So we need only look at multiples of $\omega_p(n)$.
Next fact, easily shown for $p\ne2$, and necessarily modified for $p=2$, is that if $v_p(N-1)\ge1$, then $v_p(N^p-1)=1+v_p(N-1)$.
And the final fact is that if $m$ is prime to $p$ and $v_p(N-1)\ge1$, then $v_p(N^m-1)=v_p(N-1)$.
Let’s do an example, $n=7$ and $p=5$. In this case, $\omega_5(7)=4$, and since $7^4=2401$, we have $v_5(7^4-1)=2$. Now we need only ask for $v_5(7^{4\beta}-1)$, that is for values of $\alpha=4\beta$. Now write $\beta=5^tu$, and see that $v_5(7^{4\beta}-1)=2+t$.