cp's OEIS Frontend

A072203 (Number of oddly factored numbers <= n) - (number of evenly factored numbers <= n).

%I A072203 #41 Aug 02 2025 17:03:22
%S A072203 0,1,2,1,2,1,2,3,2,1,2,3,4,3,2,1,2,3,4,5,4,3,4,3,2,1,2,3,4,5,6,7,6,5,
%T A072203 4,3,4,3,2,1,2,3,4,5,6,5,6,7,6,7,6,7,8,7,6,5,4,3,4,3,4,3,4,3,2,3,4,5,
%U A072203 4,5,6,7,8,7,8,9,8,9,10,11,10,9,10,9,8,7,6,5,6,5,4,5,4,3,2,1,2,3,4,3,4,5,6
%N A072203 (Number of oddly factored numbers <= n) - (number of evenly factored numbers <= n).
%C A072203 A number m is oddly or evenly factored depending on whether m has an odd or even number of prime factors, e.g., 12 = 2*2*3 has 3 factors so is oddly factored.
%C A072203 Polya conjectured that a(n) >= 0 for all n, but this was disproved by Haselgrove. Lehman gave the first explicit counterexample, a(906180359) = -1; the first counterexample is at 906150257 (Tanaka).
%D A072203 G. Polya, Mathematics and Plausible Reasoning, S.8.16.
%H A072203 T. D. Noe, <a href="/A072203/b072203.txt">Table of n, a(n) for n = 1..10000</a>
%H A072203 C. B. Haselgrove, <a href="http://dx.doi.org/10.1112/S0025579300001480">A disproof of a conjecture of Polya</a>, Mathematika 5 (1958), pp. 141-145.
%H A072203 R. S. Lehman, <a href="http://dx.doi.org/10.1090/S0025-5718-1960-0120198-5">On Liouville's function</a>, Math. Comp., 14 (1960), 311-320.
%H A072203 Kyle Sturgill-Simon, <a href="http://www.carroll.edu/library/thesisArchive/Sturgill-Simon_2012final.pdf">An interesting opportunity: the Gilbreath conjecture</a>, Honors Thesis, Mathematics Dept., Carroll College, 2012.
%H A072203 M. Tanaka, <a href="http://dx.doi.org/10.3836/tjm/1270216093">A Numerical Investigation on Cumulative Sum of the Liouville Function</a>, Tokyo J. Math. 3:1, 187-189, 1980.
%F A072203 a(n) = 1 - A002819(n). - _T. D. Noe_, Feb 06 2007
%t A072203 f[n_Integer] := Length[Flatten[Table[ #[[1]], {#[[2]]}] & /@ FactorInteger[n]]]; g[n_] := g[n] = g[n - 1] + If[ EvenQ[ f[n]], -1, 1]; g[1] = 0; Table[g[n], {n, 1, 103}]
%t A072203 Join[{0},Accumulate[Rest[Table[If[OddQ[PrimeOmega[n]],1,-1],{n,110}]]]] (* _Harvey P. Dale_, Mar 10 2013 *)
%t A072203 Table[1 - Sum[(-1)^PrimeOmega[i], {i, 1, n}], {n, 1, 100}] (* _Indranil Ghosh_, Mar 17 2017 *)
%o A072203 (Haskell)
%o A072203 a072203 n = a072203_list !! (n-1)
%o A072203 a072203_list = scanl1 (\x y -> x + 2*y - 1) a066829_list
%o A072203 -- _Reinhard Zumkeller_, Nov 19 2011
%o A072203 (PARI) a(n) = 1 - sum(i=1, n, (-1)^bigomega(i));
%o A072203 for(n=1, 100, print1(a(n),", ")) \\ _Indranil Ghosh_, Mar 17 2017
%o A072203 (Python)
%o A072203 from functools import reduce
%o A072203 from operator import ixor
%o A072203 from sympy import factorint
%o A072203 def A072203(n): return 1+sum(1 if reduce(ixor, factorint(i).values(),0)&1 else -1 for i in range(1,n+1)) # _Chai Wah Wu_, Dec 20 2022
%Y A072203 Cf. A028488, A002819, A051470, A066829.
%K A072203 sign,nice,easy,look
%O A072203 1,3
%A A072203 Bill Dubuque (wgd(AT)zurich.ai.mit.edu), Jul 03 2002
%E A072203 Edited and extended by _Robert G. Wilson v_, Jul 13 2002
%E A072203 Comment corrected by _Charles R Greathouse IV_, Mar 08 2010