Prime Factorization patterns of $\sum_{i=0}^k{4^i}$

Question

$$ \text { Given the function: }f:\mathcal{N^+} \to \mathcal{N^+} where f \left(k\right) = \sum_{i=0}^k \,4^i. $$

Examining the prime factorizations of f(k) for k= 1...48, many factors appear in a regular pattern.

QUESTION:

1. Is there a proof that these patterns continue for larger values of k?
2. Is there a known use for these patterns in number theory?

Answer 1

I've once "invented" a small notation-scheme for the handy expression of the primefactorization of that function.

1. Let's define $[a:p] = 1 $ if $p$ divides $a$ and $=0$ if not. ($p$ need not a simple primefactor here)
2. Let's define $\{a,p\} = m $ giving the (highest) exponent to which $[a:p^m]=1$

Next

3. let's define $\lambda_{a,p}$ and $\alpha_{a,p}$ implicitely by
   $\lambda_{a,p}$ being the minimal positive exponent in $ \{a^{\lambda_{a,p}} -1,p\}= \alpha_{a,p}$ such that $\alpha_{a,p} \gt 0$ .

(Notes: we know $\lambda_{a,p}$ also as the "order of the cyclic subgroup modulo $p$". Of course there are cases, where $p$ never divides that expression, but we might assign formally $\lambda_{a,p}=\infty$ in that cases.)

For instance, let $a=2,p=7$ then $\lambda_{a,p}=3$ and $\alpha_{a,p}=1$ because $ \{2^3 - 1, 7\}=1$, or let $a=3,p=11$ then $\lambda_{a,p}=5$ and $\alpha_{a,p}=2$ because $ \{3^5 - 1, 11\}=2$.

With this it is possible to formulate algebraically manipulatable formulae for the primefactorization of expressions $f(n)=a^n-1 $ as well as of $f(n)=a^n-b^n$.

For your example $a=4$ we get $$f(n) = 4^n-1 = 3^{e3} \cdot 5^{e5} \cdot 7^{e7} \cdot 11^{e11} \cdot \ldots $$where $$ \begin{array}{} e_3 &=& [n:1](1 + \{n,3\}) \\ e_5 &=& [n:2](1 + \{n,5\}) \\ e_7 &=& [n:3](1 + \{n,7\}) \\ e_{11} &=& [n:5](1 + \{n,11\}) \\ e_{13} &=& [n:6](1 + \{n,13\}) \\ \vdots &=& \vdots \\ e_{1093} &=& [n:182](2 + \{n,1093\}) \\ \vdots &=& \vdots \\ e_{3511} &=& [n:1755](2 + \{n,3511\}) \\ \vdots &=& \vdots \end{array}$$ where I inserted also the two known Wieferich primes $1093,3511$ which show that the $\alpha_{a,p}$ can sometimes be bigger than 1. The formula for one primefactor $p$ is in general $ \{a^n-1,p\} = [n:\lambda](\alpha + \{n,p\}) $ (plus special handling for the primefactor 2, but it does not occur here)

Unfortunately, the $\lambda$ as well as the $\alpha$ must be determined "empirically" for each pair of (base,primefactor), but where it is of help that $\lambda_{a,p}$ is either equal to the Euler's-totient function $\phi(p)$ or a true divisor of it. But after those two values are determined, we can work algebraically with varying $n$, products, quotients even of different bases and so on.
For instance we can easily derive the primefactorization for the related expression $g(n)=4^n+1$ because $g(n) = f(2n)/f(n)$ and we find the primefactorization for $g(n)$ for instance for the primefactor $5$ by $$ \begin{array}{rrlll} \{g(n),5\}&=& \{f(2n),5\} &- \{f(n),5\} \\ &=& [2n:2](1+\{2n,5\}) &-[n:2](1+\{n,5\}) \\ &=& 1 \cdot (1+\{2n,5\}) &-[n:2](1+\{n,5\}) \\ &=& 1 \cdot (1+\{n,5\}) &-[n:2](1+\{n,5\}) \\ &=& (1 -[n:2])(1+\{n,5\}) \\ \end{array}$$ which means, the primefactor $5$ occurs only if $n$ is odd (=not divisible by 2) ; its exponents is 1 at $n=1$ (of course $4^1+1$ is divisible by $5$) and increases as far as $n$ contains itself powers of $5$, so we should have $$ \{g(5),5\} = 1 \cdot (1+\{5,5\}) = 1+1 =2 $$ and indeed $4^5+1 = 1025$ is divisible by $5^2=25$.

Of course, because you have defined your function $F(k)$ such that it is $$ F(k) = f(k+1)/3 = f(n+1)/f(1) $$ as Prof. Israel has already pointed out, we have to remove the constant summand $1$ in the display of $e_3$ and also correct our result for replacing $n$ by $n+1$ - but I think that does not affect the understandability and intuitivity of the whole scheme as given in the examples.

I've done the proof for this "algebraicity" of the exponents of the primefactors in a small treatize of mine, but it seems it has made its way independentenly into the wider open under the name "lemma of the $LTE$ (lifting the exponents)" and I've sometimes seen even answers here in MSE which relate to this (and where I expect they point to the required proofs - but which are simple and elementary and can be done by yourself).

Answer 2

We have $f(k) = \frac{1}{3} (4^{k+1}-1)$.

Let $p\neq 2,3$ be prime. By Fermat's Little Theorem, if $p \mid f(k)$, then $p\mid f(k+p-1)$. So there should be lots of patterns among divisors of the $f(k)$.

For example, we have $5\mid f(1+4k)$ for $k=0,1,2,\ldots$

Answer 3

$$f(k) = \sum_{i=0}^k 4^i = \dfrac{4^{k+1}-1}{3}$$ If $d$ is coprime to $2$ and $3$, then $d$ divides $f(k)$ if and only if $4^{k+1} \equiv 1 \mod d$, i.e. iff $k+1$ is a multiple of the order of $4$ in the multiplicative group $U_d$ of units in $\mathbb Z/d\mathbb Z$. For example, the order of $4$ in $U_7$ is $3$ (i.e. $4^3 = 64 \equiv 1 \mod 7$ but $4^1$ and $4^2 \not\equiv 1 \mod 7$, so $f(k)$ is divisible by $7$ whenever $k-1$ is divisible by $3$.