cp's OEIS Frontend

A040051 Parity of partition function A000041.

%I A040051 #73 Jan 24 2018 01:43:17
%S A040051 1,1,0,1,1,1,1,1,0,0,0,0,1,1,1,0,1,1,1,0,1,0,0,1,1,0,0,0,0,1,0,0,1,1,
%T A040051 0,1,1,1,1,1,0,1,0,1,1,0,0,0,1,1,0,1,1,1,1,0,1,0,0,0,1,1,0,1,0,0,0,1,
%U A040051 1,1,0,1,1,1,0,0,1,1,0,0,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0,1,0,1
%N A040051 Parity of partition function A000041.
%C A040051 From M. V. Subbarao (m.v.subbarao(AT)ualberta.ca), Sep 05 2003: (Start)
%C A040051 Essentially this same question was raised by Ramanujan in a letter to P. A. MacMahon around 1920 (see page 1087, MacMahon's Collected Papers). With the help of Jacobi's triple product identity, MacMahon showed that p(1000) is odd (as he says, with five minutes work - there were no computers those days).
%C A040051 Now we know that among the first ten million values of p(n) 5002137 of them are odd. It is conjectured (T. R. Parkin and D. Shanks) that p(n) is equally often even and odd. Lower bound estimates for the number of times p(n) is even among the first N values of p(n) for any given N are known (Scott Ahlgren; and Nicolas, Rusza and Sárközy among others).
%C A040051 Earlier this year a remarkable result was proved by Boylan and Ahlgren (AMS ABSTRACT # 987-11-82) which says that beyond the three eighty-year old Ramanujan congruences - namely, p(5n+4), p(7n+5) and p(11n +6) being divisible respectively by 5,7 and 11 - there are no other simple congruences of this kind.
%C A040051 My 1966 conjecture that in every arithmetic progression r (mod s) for arbitrary integral r and s, there are infinitely many integers n for which p(n) is odd - with a similar statement for p(n) even - was proved for the even case by Ken Ono (1996) and for the odd case for all s up to 10^5 and for all s which are powers of 2 by Bolyan and Ono, 2002.
%C A040051 (End)
%C A040051 a(n) is also the parity of the trace Tr(n) = A183011(n), the numerator of the Bruinier-Ono formula for the partition function, if n >= 1. - _Omar E. Pol_, Mar 14 2012
%C A040051 Consider the diagram of the regions of n (see A206437). Then, in each odd-indexed region of n, fill each part of size k with k 1's. Then, in each even-indexed region of n, fill each part of size k with k 0's. The successive digits of row 1 of the diagram give the first n elements of this sequence, if n >= 1. - _Omar E. Pol_, May 02 2012
%D A040051 H. Gupta, A note on the parity of p(n), J. Indian Math. Soc. (N.S.) 10, (1946). 32-33. MR0020588 (8,566g)
%D A040051 K. M. Majumdar, On the parity of the partition function p(n), J. Indian Math. Soc. (N.S.) 13, (1949). 23-24. MR0030553 (11,13d)
%D A040051 M. V. Subbarao, A note on the parity of p(n), Indian J. Math. 14 (1972), 147-148. MR0357355 (50 #9823)
%H A040051 T. D. Noe, <a href="/A040051/b040051.txt">Table of n, a(n) for n = 0..1000</a>
%H A040051 R. Blecksmith; J. Brillhart; I. Gerst, <a href="http://dx.doi.org/10.1090/S0025-5718-1987-0866096-X">Parity results for certain partition functions and identities similar to theta function identities</a>, Math. Comp. 48 (1987), no. 177, 29-38. MR0866096 (87k:11113).
%H A040051 Nicholas Eriksson, <a href="http://ftp.fi.muni.cz/pub/muni.cz/EMIS/journals/IJMMS/volume-22/S0161171299220558.pdf?N=A">q-series, elliptic curves and odd values of the partition function</a>, Int. J. Math. Math. Sci. 22 (1999), 55-65; MR 2001a:11175.
%H A040051 M. D. Hirschhorn, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa38/aa3823.pdf">On the residue mod 2 and mod 4 of p(n)</a>, Acta Arith. 38 (1980/81), no. 2, 105-109. MR0604226 (82d:10025)
%H A040051 M. D. Hirschhorn, <a href="http://dx.doi.org/10.1016/0097-3165(93)90075-J">On the parity of p(n), II</a>, J. Combin. Theory Ser. A 62 (1993), no. 1, 128-138.
%H A040051 M. D. Hirschhorn and M. V. Subbarao, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa50/aa5044.pdf">On the parity of p(n)</a>, Acta Arith. 50 (1988), no. 4, 355-356.
%H A040051 O. Kolberg, <a href="http://www.mscand.dk/article/view/10584/8605">Note on the parity of the partition function</a>, Math. Scand. 7 1959 377-378. MR0117213 (22 #7995).
%H A040051 P. A. MacMahon, <a href="http://jlms.oxfordjournals.org/content/s1-1/4/225.2.extract">The parity of p(n), the number of partitions of n, when n <= 1000</a>, J. London Math. Soc., 1 (1926), 225-226.
%H A040051 Mircea Merca, <a href="http://journals.tubitak.gov.tr/math/issues/mat-17-41-5/mat-41-5-10-1604-124.pdf">New recurrences for Euler's partition function</a>, Turkish J. Math. 41:5 (2017), pp. 1184-1190.
%H A040051 M. Newman, <a href="http://dx.doi.org/10.1090/S0002-9947-1960-0115981-2">Periodicity modulo m and divisibility properties of the partition function</a>, Trans. Amer. Math. Soc. 97 (1960), 225-236. MR0115981 (22 #6778)
%H A040051 M. Newman, <a href="http://projecteuclid.org/euclid.ijm/1255631806">Congruences for the partition function to composite moduli</a>, Illinois J. Math. 6 1962 59-63. MR0140472 (25 #3892)
%H A040051 K. Ono, <a href="http://www.ams.org/era/1995-01-01/S1079-6762-95-01005-5/S1079-6762-95-01005-5.pdf">Parity of the partition function</a>, Electron. Res. Announc. AMS, Vol. 1, 1995, pp. 35-42; MR 96d:11108.
%H A040051 Ivars Peterson, <a href="http://www.maa.org/mathland/mathland_3_24.html">Ken Ono's and Nicholas Eriksson's work</a>
%F A040051 a(n) = pp(n, 1), with Boolean pp(n, k) = if k<n then pp(n-k, k) XOR pp(n, k+1) else (k=n). - _Reinhard Zumkeller_, Sep 04 2003
%F A040051 a(n) = Pm(n,1) with Pm(n,k) = if k<n then (Pm(n-k,k) + Pm(n,k+1)) mod 2 else 0^(n*(k-n)). - _Reinhard Zumkeller_, Jun 09 2009
%F A040051 a(n) = A000035(A000041(n)). - _Omar E. Pol_, Aug 05 2013
%F A040051 a(n) = A000035(A000025(n)). - _John M. Campbell_, Jun 29 2016
%t A040051 Table[ Mod[ PartitionsP@ n, 2], {n, 105}] (* _Robert G. Wilson v_, Mar 25 2011 *)
%o A040051 (PARI) a(n)=if(n<0, 0, numbpart(n)%2)
%o A040051 (PARI) a(n)=if(n<0, 0, polcoeff(1/eta(x+x*O(x^n)), n)%2)
%o A040051 (PARI) a(n)=if(n<10^9, return(numbpart(n)%2)); my(r=n%4, u=select(k->k^2%32==8*r+1,[1..31]), st=u[1], m=n\4, s); u=[u[2]-u[1],u[3]-u[2],u[4]-u[3],u[1]+32-u[4]]; forstep(t=[1,3,7,5][r+1], sqrtint(32*m-1), u, k=t^2>>5; if(a(m-k), s++)); s%2 \\ Merca's algorithm, switching to direct computation for n less than 10^9. Very time-consuming but low memory use. - _Charles R Greathouse IV_, Jan 24 2018
%o A040051 (Haskell)
%o A040051 import Data.Bits (xor)
%o A040051 a040051 n = p 1 n :: Int where
%o A040051    p _ 0 = 1
%o A040051    p k m | k <= m = p k (m - k) `xor` p (k+1) m | k > m  = 0
%o A040051 -- _Reinhard Zumkeller_, Nov 15 2011
%o A040051 (Python)
%o A040051 from sympy import npartitions
%o A040051 def a(n): return npartitions(n)%2 # _Indranil Ghosh_, May 25 2017
%Y A040051 Cf. A000041, A071640, A086144, A190938.
%K A040051 nonn,easy,nice
%O A040051 0,1
%A A040051 _N. J. A. Sloane_