I am not familiar with newforms, so this may not make any sense.


OEIS sequence [A116418](https://oeis.org/A116418) is Expansion of a newform level 18 weight 3 and character [3]


Numerical evidence suggest that up to $10^5$
$$ \text{A116418}[n] \equiv \sigma(3n+1) \pmod 3$$



> 
> What is the complexity of computing A116418[n], possibly assuming $n$ is factored (for modular form coefficients after $n$ is factored the coefficient is efficiently computable).
> 
> 
> 


Gjergji Zaimi [proved](https://mathoverflow.net/questions/59178/up-to-106-sigma8n1-mod-4-oeis-a001935n-mod-4-number-of-partition) a similar congruence involving eta and A116418 is expansion of an eta formula.


*Added* My main interest is computing $\sigma(3n+1) \mod 3$ and a comment by Dror Speiser suggests the coefficient of the newform is computable in polynomial time assuming $n$ is factored.


The factorization of $n$ is not related related to the factorization of $3n+1$ and for numbers of form $3 \cdot 2^n + 1$ the factorization is trivial.



> 
> Is A116418 really the expansion of the newform or is it a typo in OEIS?
> 
> 
> Is the congruence $ \text{A116418}[n] \equiv \sigma(3n+1) \pmod 3$ identity or just coincidence for the the first $10^5$ terms?
> 
> 
> 



Complexity of computing expansion of a newform level 18 weight 3 and character [3] - OEIS A116418
[More a comment than an answer, but too long for the comment space]


Call this form
$$
\varphi := \frac{\eta(q^3)^2 \eta(q^6)^3 \eta(q^9)^2}{\eta(q^{18})}
= q - 2q^4 - 4q^7 + 6q^{10} + 8q^{13} \cdots.
$$
The listing of coefficients in the OEIS is correct as far as it goes (checked
with copy-and-paste to **gp**). The form is not CM: the coefficients are
supported on $q^n$ with $n \equiv 1 \bmod 3$ but do not vanish even for $n$
such as $10$ and $22$ that are $1 \bmod 3$ but not norms from ${\bf
Q}(\sqrt{-3})$. In particular the coefficients aren't multiplicative, so
$\varphi$ isn't quite an eigenform. It seems that the relevant eigenforms are
obtained as follows. Apply $w\_{18}$ to get (within a multiplicative factor)
$$
\phi := \frac{\eta(q^6)^2 \eta(q^3)^3 \eta(q^2)^2}{\eta(q)} = q + q^2 - 2q^4 -
3q^5 - 4q^7 - 2q^8 + 6q^{10} + 12q^{11} + 8q^{13} - 4q^{14} \cdots,
$$
whose $q^n$ coefficient is 0 if $n \equiv 0 \bmod 3$, and coincides with the
$q^n$ coefficient of $\varphi$ also when $n \equiv 1 \bmod 3$, but need not
vanish for $n \equiv 2 \bmod 3$. Then "experimentally" if $m,n$ are relatively
prime then the $q^{mn}$ coefficient of $\phi$ equals the product of the $q^m$
and $q^n$ coefficients, *unless* both $m$ and $n$ are $2 \bmod 3$, when the
$q^{mn}$ coefficient is $-2$ times that product. Hence we obtain an eigenform
by choosing a square root of $-2$ and multiplying the $q^n$ coefficient of
$\phi$ by that square root for each $n \equiv 2 \bmod 3$.


As Dror Speiser notes, the Edixhoven program promises to compute the $q^n$
coefficient of such a form in time $\log^{O(1)}n$ for $n$ prime, and thus for
all $n$ given the factorization of $n$; but I don't think this has been
implemented yet to the point that one could actually carry out the computation
this way. For specific forms there can be shortcuts that make a $\log^{O(1)}n$
computation practical (still assuming $n$ is factored), but here I've tried a
few things and not yet(?) found such a shortcut.


*[added later]* Curiously the images of $\phi$ under the other two $w$
operators are in the linear span of $\varphi$ and $\phi$: if we write
$$
\psi = \frac{\eta(q^3)^3 \eta(q^6)^2 \eta(q^{18})^2}{\eta(q^9)}
 = q^2 - 3q^5 - 2q^8 + 12q^{11} - 4q^{14} \cdots
$$
for (a multiple of) the $w\_2$ image, then $\phi = \varphi + \psi$, while
$\varphi - 2 \psi$ is the multiple
$$
\frac{\eta(q)^2 \eta(q^3)^2 \eta(q^6)^3}{\eta(q^2)}
= q - 2q^2 - 2q^4 + 6q^5 - 4q^7 + 4q^8 + 6q^{10} - 24q^{11} + 8q^{13} + 8q^{14} 
\ldots
$$
of the $w\_9$ image.


