

A072203


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


4



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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.
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).


REFERENCES

G. Polya, Mathematics and Plausible Reasoning, S.8.16.


LINKS



FORMULA



MATHEMATICA

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}]
Join[{0}, Accumulate[Rest[Table[If[OddQ[PrimeOmega[n]], 1, 1], {n, 110}]]]] (* Harvey P. Dale, Mar 10 2013 *)
Table[1  Sum[(1)^PrimeOmega[i], {i, 1, n}], {n, 1, 100}] (* Indranil Ghosh, Mar 17 2017 *)


PROG

(Haskell)
a072203 n = a072203_list !! (n1)
a072203_list = scanl1 (\x y > x + 2*y  1) a066829_list
(PARI) a(n) = 1  sum(i=1, n, (1)^bigomega(i));
(Python)
from functools import reduce
from operator import ixor
from sympy import factorint
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


CROSSREFS



KEYWORD



AUTHOR

Bill Dubuque (wgd(AT)zurich.ai.mit.edu), Jul 03 2002


EXTENSIONS



STATUS

approved



