Is A001935 Number of partitions with no even part repeated efficiently computable $\mod 4$?
I am interested because of this relation with sum of divisors of $8n+1$.
$\sigma(8n+1) \equiv A001935(n) \pmod 4$
Gjergji Zaimi's proof of the above
Do S. Ahlgren & K. Ono congruences for the partition function shed some light?
The generating function is $\prod_{k \geq 1}\frac{1-x^{4k}}{1-x^k}$
Let $a(n)=A001935(n) \mod 4$.
Up to $10^7$ these hold: $$a(9n+4)=0$$ $$a(9n+7)=0$$
Update
Related sequence is A001936 Expansion of q^(-1/4) (eta(q^4) / eta(q))^2 in powers of q
Gjiergji proved:
$$\sigma(4n+1) \equiv A001936(n) \pmod 4$$
A001936 mod 4 is zero for n = 9m+5 or 9m+8 up to $10^7$.
Let $a(n)=A001936(n) \mod 4$. Up to $10^7$:
$$a(n)=a(9n+2)$$
EDITED version by David Speyer:
The question is:
Given an integer $m$ which is $1 \mod 8$, is there an algorithm which computes $\sigma(m) \mod 4$ in time polynomial in $\log m$?
Reason we might think no: If there were such an algorithm, there would be an efficient algorithm for the following question: Given an integer $m$ which is $1 \mod 8$, and a promise that $m$ is either of the form $pq$ or $p^2 q$ with $p$ and $q$ prime, determine which once holds. The method is simply to note that $\sigma(pq) \equiv 0 \mod 4$ and $\sigma(p q^2) \equiv 2 \mod 4$.
I have a heuristic that there are only two easy problems in prime factorization: Determining whether a number is prime (by AKS) and determining whether a number is a perfect power. So I expect that this problem is not easy and, thus, $\sigma(m) \mod 4$ is hard to compute. But I (David) am not an expert on factorization, so this argument should not be taken very seriously.
Reasons we might think yes: As explained in a
previous answer of Gjergji Zaimi, $\sigma(8n+1)$ is given by an infinite product similar to that for the partition function and $\sigma(8n+1) \mod 4$ can be described as the number of partitions of a certain sort.
Recent work of Folsom, Kent and Ono provides a very general method for writing $\ell$-adically convergent power series for the coefficients of modular forms resembling the partition generating function. (The original version of this question links to earlier work of Ahlgren and Ono but I might as well link to the most powerful result.)
If those results apply in this case, with $\ell=2$, we could presumably look at the lowest two bits of the sum. If this sum converges at all rapidly, this should be an efficient algorithm. Note that the complexity of finding this $2$-adic expansion is irrelevant because that is a one time cost; the only question is, once the expression is found, how fast does it converge and how hard are the individual terms to compute?
As I (David) haven't read Ono's work, this argument also shouldn't be taken very seriously. But the conflict of these two arguments against each other makes it seem like an interesting question.