Up to $10^6$: $\sigma(8n+1) \mod 4 = OEIS A001935(n) \mod 4$ (Number of partitions with no even part repeated ) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T23:28:41Z http://mathoverflow.net/feeds/question/59178 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59178/up-to-106-sigma8n1-mod-4-oeis-a001935n-mod-4-number-of-partition Up to $10^6$: $\sigma(8n+1) \mod 4 = OEIS A001935(n) \mod 4$ (Number of partitions with no even part repeated ) joro 2011-03-22T12:13:22Z 2011-03-23T13:31:07Z <p>Up to $10^6$: </p> <p>$\sigma(8n+1) \mod 4 = OEIS A001935(n) \mod 4$ </p> <p><a href="https://oeis.org/A001935" rel="nofollow">A001935 Number of partitions with no even part repeated</a></p> <p>Is this true in general?</p> <p>It would mean relation between restricted partitions of $n$ and divisors of $8n+1$.</p> <p>Another one up to $10^6$ is:</p> <p>$\sigma(4n+1) \mod 4 = A001936(n) \mod 4$</p> <p><a href="https://oeis.org/A001936" rel="nofollow">A001936 Expansion of q^(-1/4) (eta(q^4) / eta(q))^2 in powers of q</a></p> <p>$\sigma(n)$ is sum of divisors of $n$.</p> <blockquote> <p>sigma(8n+1) mod 4 starts: 1, 1, 2, 3, 0, 2, 1, 0, 0, 2, 1, 2, 2, 0, 2, 1, 0, 2, 0, 2, 0, 3, 0, 0, 2, 0, 0, 0, 3, 2</p> <p>sigma(4n+1) mod 4 starts: 1, 2, 1, 2, 2, 0, 3, 2, 0, 2, 2, 2, 1, 2, 0, 2, 0, 0, 2, 0, 1, 0, 2, 0, 2, 2</p> </blockquote> <p><strong>Update</strong></p> <p>Up to 10^7</p> <p>A001935 mod 4 is zero for n = 9m+4 or 9m+7</p> <p>A001936 mod 4 is zero for n = 9m+5 or 9m+8</p> <p><a href="http://mathoverflow.net/questions/59192/is-oeis-a001935-number-of-partitions-with-no-even-part-repeated-efficiently-com" rel="nofollow">Question about computability</a></p> http://mathoverflow.net/questions/59178/up-to-106-sigma8n1-mod-4-oeis-a001935n-mod-4-number-of-partition/59185#59185 Answer by Gjergji Zaimi for Up to $10^6$: $\sigma(8n+1) \mod 4 = OEIS A001935(n) \mod 4$ (Number of partitions with no even part repeated ) Gjergji Zaimi 2011-03-22T14:00:00Z 2011-03-22T16:14:18Z <p>Let's call A001936(n) by $a(n)$. Here is a sketch of why $$a(n)\equiv \sigma(4n+1)\pmod{4}$$ Firs note that the generating function of $a(n)$ is $$A(x)=\sum_{n\geq 0}a(k)x^n=\prod_{k\geq 1}\left(\frac{1-x^{4k}}{1-x^k}\right)^2$$ for $\sigma(2n+1)$ the generating function is $$B(x)=\sum_{k\geq 0}\sigma(2k+1)x^k=\prod_{k\geq 0}(1-x^k)^4(1+x^k)^8$$ So $$B(x)\equiv \prod_{k\geq 1}(1+x^{2k})^2(1+x^{4k})^2\equiv \prod_{k\geq 1}(\frac{1-x^{8k}}{1-x^{2k}})^2\equiv A(x^2)\pmod{4}$$ Now the proof is complete once we know that $$B(x)\equiv \sum_{k\geq 0} \sigma(4n+1)x^{2n}\pmod{4}$$ this is an other way of saying $\sigma(4n-1)$ is divisible by $4$, which can be shown by pairing up the divisors $d+\frac{4n-1}{d}\equiv 0\pmod{4}$.</p> <p>The proof for the other congruence is similar, but slightly longer, I might update this post later to include it. </p> <hr> <p>Let's prove that $\sigma(8n+1)\equiv q(n)\pmod{4}$, where $q(n)$ is the number of partitions with no even part repeated. The generating function is $$Q(x)=\sum_{n\geq 0}q(n)x^n=\prod_{k\geq 1}\frac{1-x^{4k}}{1-x^k}$$ Since we know from above that $$\sum_{n\geq 0}\sigma(4n+1)x^{2n}\equiv \prod_{k\geq 1}(1+x^{2k})^2(1+x^{4k})^2 \pmod{4}$$ we conclude that $$L(x)=\sum_{n\geq 0}\sigma(4n+1)x^n\equiv Q(x)^2 \pmod{4}$$ so that $$\sum_{n\geq 0} \sigma(8n+1)x^{2n}\equiv \frac{L(x)+L(-x)}{2}\pmod{4}$$ So to finish off the proof we need the following $$\frac{Q(x)^2+Q(-x)^2}{2}\equiv Q(x^2)\pmod{4}$$ <s>which I will leave as an exercise</s> Actually let me write the proof, just to make sure I didn't mess up calculations. This reduces to proving $$\frac{\prod_{k\geq 1}(1+x^{2k})^4(1+x^{2k-1})^2+\prod_{k\geq 1}(1+x^{2k})^4(1-x^{2k-1})^2}{2}$$ $$\equiv \prod_{k\geq 1}(1+x^{4k-2})(1+x^{4k})^2 \pmod{4}$$ and since $$(1+x^{2k})^4\equiv (1+x^{4k})^2 \pmod{4}$$ this reduces to $$\frac{\prod_{k\geq 1}(1+x^{2k-1})^2+\prod_{k\geq 1}(1-x^{2k-1})^2}{2}\equiv \prod_{k\geq 1} (1+x^{4k-2})\pmod{4}$$ but we can write $$\prod_{k\geq 1}(1-x^{2k-1})^2\equiv \left(\prod_{k\ geq 1}(1+x^{2k-1})^2\right) \left(1-4\sum_{k\geq 1}\frac{x^{2k-1}}{(1+x^{2k-1})^2}\right)\pmod{8}$$ therefore now we have to show $$\prod_{k\geq 1}(1+x^{2k-1})^2\left(1-2\sum_{k\geq 1}\frac{x^{2k-1}}{(1+x^{2k-1})^2}\right)\equiv \prod_{k\geq 1}(1+x^{4k-2})\pmod{4}$$ Now everything is clear since $$\prod_{k\geq 1}(1+x^{2k-1})^2\equiv \prod_{k\geq 1}(1+x^{4k-2})\left(1+2\sum_{k\geq 1}\frac{x^{2k-1}}{(1+x^{2k-1})^2}\right)\pmod{4}$$</p>