# Does this function change signs infinitely often?

$$f(n) = \sum_{i = 1}^n (-1)^{\omega(i)}$$

where $\omega(n)$ counts how many distinct prime factors $n$ has.

I don't see any sign changes past $n = 49$, but I've only computed it up to $n = 1{,}000$.

-
I bet you a quarter it does. I've got no mathematical justification for that, though. – Mike Miller Jun 21 '14 at 20:15
@MikeMiller If it does, I bet the proof is very similar to the one for the Mertens function. The big difference is that only squarefree numbers matter for the Mertens function. – Robert Soupe Jun 22 '14 at 17:39

I thought of a good brief summary. Starting with 12,100 and going up to 100,000,000, here are occurrences of multiples of 1000, but not two of the same thing in a row. So, it can be expected that the value wiggles around 0 (and repeats it) for quite a while after each printed occurrence of 0. It does have very long stretches where it is negative, but infinitely many sign changes seems to be the best guess. If this thing can be resolved, the information to be used is in Section 7.4 of Montgomery-Vaughan's Multiplicative Number Theory I. Classical Theory.

       12100      0       12100 = 2^2 * 5^2 * 11^2
152116  -1000      152116 = 2^2 * 17 * 2237
587752  -2000      587752 = 2^3 * 11 * 6679
2033106  -3000     2033106 = 2 * 3 * 338851
6539892  -2000     6539892 = 2^2 * 3 * 181 * 3011
6971926  -3000     6971926 = 2 * 13^2 * 20627
9782250  -2000     9782250 = 2 * 3 * 5^3 * 13043
12410420  -3000    12410420 = 2^2 * 5 * 11 * 19 * 2969
13162096  -2000    13162096 = 2^4 * 822631
13554666  -1000    13554666 = 2 * 3^2 * 151 * 4987
13934776  -2000    13934776 = 2^3 * 199 * 8753
14919204  -1000    14919204 = 2^2 * 3 * 197 * 6311
16952838  -2000    16952838 = 2 * 3 * 7 * 167 * 2417
17212474  -1000    17212474 = 2 * 37 * 163 * 1427
17476380  -2000    17476380 = 2^2 * 3^2 * 5 * 79 * 1229
19594912  -1000    19594912 = 2^5 * 612341
20014108  -2000    20014108 = 2^2 * 113 * 44279
20829864  -1000    20829864 = 2^3 * 3 * 11 * 78901
22395666      0    22395666 = 2 * 3 * 373 * 10007
24367578  -1000    24367578 = 2 * 3 * 4061263
24732038      0    24732038 = 2 * 23 * 223 * 2411
25620716   1000    25620716 = 2^2 * 11 * 113 * 5153
26504736      0    26504736 = 2^5 * 3 * 276091
27691442   1000    27691442 = 2 * 13845721
28007440      0    28007440 = 2^4 * 5 * 350093
29065746   1000    29065746 = 2 * 3 * 239 * 20269
29970968      0    29970968 = 2^3 * 83 * 45137
30266764  -1000    30266764 = 2^2 * 11 * 59 * 89 * 131
31522038      0    31522038 = 2 * 3 * 691 * 7603
33426868  -1000    33426868 = 2^2 * 641 * 13037
33628584      0    33628584 = 2^3 * 3 * 11 * 17 * 59 * 127
34307628   1000    34307628 = 2^2 * 3 * 23 * 124303
34630336   2000    34630336 = 2^6 * 13 * 107 * 389
34981666   3000    34981666 = 2 * 23 * 349 * 2179
35982728   4000    35982728 = 2^3 * 4497841
36090070   3000    36090070 = 2 * 5 * 3609007
38801674   2000    38801674 = 2 * 613 * 31649
39246626   1000    39246626 = 2 * 397 * 49429
39511802      0    39511802 = 2 * 11 * 1795991
40009796   1000    40009796 = 2^2 * 10002449
40870538      0    40870538 = 2 * 883 * 23143
41550862   1000    41550862 = 2 * 20775431
41995314   2000    41995314 = 2 * 3^3 * 263 * 2957
43411288   3000    43411288 = 2^3 * 5426411
44901100   2000    44901100 = 2^2 * 5^2 * 449011
45477614   1000    45477614 = 2 * 7 * 13 * 79 * 3163
47082026   2000    47082026 = 2 * 23541013
48077100   3000    48077100 = 2^2 * 3^2 * 5^2 * 53419
50779700   2000    50779700 = 2^2 * 5^2 * 507797
51318652   3000    51318652 = 2^2 * 7 * 11 * 166619
51643598   2000    51643598 = 2 * 239 * 108041
52943470   3000    52943470 = 2 * 5 * 23 * 230189
54035806   4000    54035806 = 2 * 11 * 47 * 52259
54799050   5000    54799050 = 2 * 3 * 5^2 * 365327
56113098   4000    56113098 = 2 * 3 * 9352183
59774476   5000    59774476 = 2^2 * 14943619
61355402   6000    61355402 = 2 * 30677701
63077442   5000    63077442 = 2 * 3 * 10512907
64605978   6000    64605978 = 2 * 3^3 * 193 * 6199
65196454   7000    65196454 = 2 * 179 * 269 * 677
65570770   6000    65570770 = 2 * 5 * 6557077
66675178   5000    66675178 = 2 * 523 * 63743
67469658   4000    67469658 = 2 * 3 * 11244943
68898250   3000    68898250 = 2 * 5^3 * 275593
69059386   4000    69059386 = 2 * 11 * 23 * 136481
70496450   3000    70496450 = 2 * 5^2 * 17 * 197 * 421
70631848   4000    70631848 = 2^3 * 7 * 41 * 30763
74672720   5000    74672720 = 2^4 * 5 * 23 * 40583
75578644   4000    75578644 = 2^2 * 23 * 821507
75989612   3000    75989612 = 2^2 * 227 * 83689
76389668   4000    76389668 = 2^2 * 19097417
76742446   5000    76742446 = 2 * 11 * 47 * 74219
77643242   6000    77643242 = 2 * 37 * 293 * 3581
77902016   7000    77902016 = 2^6 * 1217219
79257074   8000    79257074 = 2 * 13 * 857 * 3557
80121064   7000    80121064 = 2^3 * 311 * 32203
81852150   6000    81852150 = 2 * 3 * 5^2 * 223 * 2447
83744704   7000    83744704 = 2^6 * 19 * 61 * 1129
84717394   8000    84717394 = 2 * 42358697
86439174   7000    86439174 = 2 * 3 * 14406529
87381720   8000    87381720 = 2^3 * 3^3 * 5 * 80909
88294754   7000    88294754 = 2 * 2659 * 16603
90194346   8000    90194346 = 2 * 3^2 * 11 * 455527
90758004   9000    90758004 = 2^2 * 3 * 2351 * 3217
92003352  10000    92003352 = 2^3 * 3 * 7 * 547639
92741578   9000    92741578 = 2 * 191 * 242779
93256690  10000    93256690 = 2 * 5 * 587 * 15887
94169876   9000    94169876 = 2^2 * 191 * 123259
95318796   8000    95318796 = 2^2 * 3 * 17 * 97 * 4817
95638388   9000    95638388 = 2^2 * 23909597
97508136   8000    97508136 = 2^3 * 3 * 11 * 433 * 853
98790072   9000    98790072 = 2^3 * 3 * 59 * 69767
98953700  10000    98953700 = 2^2 * 5^2 * 907 * 1091
99796982  11000    99796982 = 2 * 49898491
102049092  10000   102049092 = 2^2 * 3^3 * 944899
jagy@phobeusjunior:~$ Just where it is 0. The thing is negative from 12,101 to 22,395,665  2 0 2 = 2 40 0 40 = 2^3 * 5 46 0 46 = 2 * 23 48 0 48 = 2^4 * 3 50 0 50 = 2 * 5^2 7960 0 7960 = 2^3 * 5 * 199 7962 0 7962 = 2 * 3 * 1327 7984 0 7984 = 2^4 * 499 7986 0 7986 = 2 * 3 * 11^3 8808 0 8808 = 2^3 * 3 * 367 8810 0 8810 = 2 * 5 * 881 8812 0 8812 = 2^2 * 2203 8816 0 8816 = 2^4 * 19 * 29 8822 0 8822 = 2 * 11 * 401 8824 0 8824 = 2^3 * 1103 8826 0 8826 = 2 * 3 * 1471 8828 0 8828 = 2^2 * 2207 8830 0 8830 = 2 * 5 * 883 8836 0 8836 = 2^2 * 47^2 8844 0 8844 = 2^2 * 3 * 11 * 67 8846 0 8846 = 2 * 4423 8848 0 8848 = 2^4 * 7 * 79 8850 0 8850 = 2 * 3 * 5^2 * 59 8854 0 8854 = 2 * 19 * 233 8856 0 8856 = 2^3 * 3^3 * 41 8858 0 8858 = 2 * 43 * 103 8860 0 8860 = 2^2 * 5 * 443 8862 0 8862 = 2 * 3 * 7 * 211 8864 0 8864 = 2^5 * 277 8866 0 8866 = 2 * 11 * 13 * 31 8872 0 8872 = 2^3 * 1109 8878 0 8878 = 2 * 23 * 193 8970 0 8970 = 2 * 3 * 5 * 13 * 23 8972 0 8972 = 2^2 * 2243 8974 0 8974 = 2 * 7 * 641 9064 0 9064 = 2^3 * 11 * 103 9078 0 9078 = 2 * 3 * 17 * 89 9080 0 9080 = 2^3 * 5 * 227 9082 0 9082 = 2 * 19 * 239 9084 0 9084 = 2^2 * 3 * 757 9086 0 9086 = 2 * 7 * 11 * 59 9088 0 9088 = 2^7 * 71 9096 0 9096 = 2^3 * 3 * 379 9164 0 9164 = 2^2 * 29 * 79 9220 0 9220 = 2^2 * 5 * 461 9222 0 9222 = 2 * 3 * 29 * 53 9226 0 9226 = 2 * 7 * 659 9230 0 9230 = 2 * 5 * 13 * 71 9232 0 9232 = 2^4 * 577 9234 0 9234 = 2 * 3^5 * 19 9240 0 9240 = 2^3 * 3 * 5 * 7 * 11 9242 0 9242 = 2 * 4621 9244 0 9244 = 2^2 * 2311 9258 0 9258 = 2 * 3 * 1543 9260 0 9260 = 2^2 * 5 * 463 9262 0 9262 = 2 * 11 * 421 9264 0 9264 = 2^4 * 3 * 193 9384 0 9384 = 2^3 * 3 * 17 * 23 9386 0 9386 = 2 * 13 * 19^2 9388 0 9388 = 2^2 * 2347 9398 0 9398 = 2 * 37 * 127 11062 0 11062 = 2 * 5531 11068 0 11068 = 2^2 * 2767 11070 0 11070 = 2 * 3^3 * 5 * 41 11072 0 11072 = 2^6 * 173 11074 0 11074 = 2 * 7^2 * 113 11078 0 11078 = 2 * 29 * 191 11080 0 11080 = 2^3 * 5 * 277 11082 0 11082 = 2 * 3 * 1847 11108 0 11108 = 2^2 * 2777 11110 0 11110 = 2 * 5 * 11 * 101 11112 0 11112 = 2^3 * 3 * 463 11114 0 11114 = 2 * 5557 11116 0 11116 = 2^2 * 7 * 397 11118 0 11118 = 2 * 3 * 17 * 109 11392 0 11392 = 2^7 * 89 11422 0 11422 = 2 * 5711 11424 0 11424 = 2^5 * 3 * 7 * 17 11426 0 11426 = 2 * 29 * 197 11428 0 11428 = 2^2 * 2857 11448 0 11448 = 2^3 * 3^3 * 53 11464 0 11464 = 2^3 * 1433 11468 0 11468 = 2^2 * 47 * 61 11472 0 11472 = 2^4 * 3 * 239 11474 0 11474 = 2 * 5737 11480 0 11480 = 2^3 * 5 * 7 * 41 11482 0 11482 = 2 * 5741 11484 0 11484 = 2^2 * 3^2 * 11 * 29 11492 0 11492 = 2^2 * 13^2 * 17 11494 0 11494 = 2 * 7 * 821 11512 0 11512 = 2^3 * 1439 11518 0 11518 = 2 * 13 * 443 11592 0 11592 = 2^3 * 3^2 * 7 * 23 11594 0 11594 = 2 * 11 * 17 * 31 11632 0 11632 = 2^4 * 727 11634 0 11634 = 2 * 3 * 7 * 277 11636 0 11636 = 2^2 * 2909 11638 0 11638 = 2 * 11 * 23^2 11650 0 11650 = 2 * 5^2 * 233 11652 0 11652 = 2^2 * 3 * 971 11982 0 11982 = 2 * 3 * 1997 11984 0 11984 = 2^4 * 7 * 107 11986 0 11986 = 2 * 13 * 461 11990 0 11990 = 2 * 5 * 11 * 109 11992 0 11992 = 2^3 * 1499 11994 0 11994 = 2 * 3 * 1999 11998 0 11998 = 2 * 7 * 857 12000 0 12000 = 2^5 * 3 * 5^3 12002 0 12002 = 2 * 17 * 353 12012 0 12012 = 2^2 * 3 * 7 * 11 * 13 12020 0 12020 = 2^2 * 5 * 601 12026 0 12026 = 2 * 7 * 859 12030 0 12030 = 2 * 3 * 5 * 401 12034 0 12034 = 2 * 11 * 547 12036 0 12036 = 2^2 * 3 * 17 * 59 12040 0 12040 = 2^3 * 5 * 7 * 43 12060 0 12060 = 2^2 * 3^2 * 5 * 67 12062 0 12062 = 2 * 37 * 163 12064 0 12064 = 2^5 * 13 * 29 12070 0 12070 = 2 * 5 * 17 * 71 12076 0 12076 = 2^2 * 3019 12100 0 12100 = 2^2 * 5^2 * 11^2  here is a good string, 12095 5 12095 = 5 * 41 * 59 12096 4 12096 = 2^6 * 3^3 * 7 12097 3 12097 = 12097 12098 2 12098 = 2 * 23 * 263 12099 1 12099 = 3 * 37 * 109 12100 0 12100 = 2^2 * 5^2 * 11^2 12101 -1 12101 = 12101 12102 -2 12102 = 2 * 3 * 2017 12103 -3 12103 = 7^2 * 13 * 19 12104 -4 12104 = 2^3 * 17 * 89 12105 -5 12105 = 3^2 * 5 * 269  int PrimeFacCount(int i) { set<int> boo; int p = 2; int temp = i; if (temp < 0 ) { temp *= -1; } if ( temp > 1) { while( temp > 1 && p * p <= temp) { if (temp % p == 0) { boo.insert(p); temp /= p; while (temp % p == 0) { temp /= p; } // while p is fac } // if p is factor ++p; } // while p if (temp > 1 ) boo.insert(temp); } // temp > 1 return boo.size(); } // PrimeFacCount string stringify(int x) { ostringstream o; o << x ; return o.str(); } string Factored(unsigned int i) { string fac; fac = " = "; int p = 2; unsigned int temp = i; if (temp < 0 ) { temp *= -1; fac += " -1 * "; } if ( 1 == temp) fac += " 1 "; if ( temp > 1) { int primefac = 0; while( temp > 1 && p * p <= temp) { if (temp % p == 0) { ++primefac; if (primefac > 1) fac += " * "; fac += stringify( p) ; temp /= p; int exponent = 1; while (temp % p == 0) { temp /= p; ++exponent; } // while p is fac if ( exponent > 1) { fac += "^" ; fac += stringify( exponent) ; } } // if p is factor ++p; } // while p if (temp > 1 && primefac >= 1) fac += " * "; if (temp > 1 ) fac += stringify( temp) ; } // temp > 1 return fac; } // Factored int bund = 0; int bund_record = 0; for(int x = 1; x <= 2111222333; ++x){ int n = PrimeFacCount(x); n %= 2; if(n) bund-- ; else bund++ ; if ( x >= 12100 && (bund + 112000) % 1000 == 0 ) { if ( bund_record != bund) { bund_record = bund; cout << setw(12) << x << setw(7) << bund << setw(12) << x << Factored(x) << endl; } } }  - Are you saying that it's never strictly negative? – TonyK Jun 21 '14 at 21:23 @TonyK, some of these are sign changes, some are local minima or local maxima. It changes sign fairly often. Let me post some juicy selections. – Will Jagy Jun 21 '14 at 21:24 "Just where it is$0$": well obviously! (Successive values always differ by 1.) That's why I wasn't sure what you were claiming. – TonyK Jun 21 '14 at 21:55 @TonyK, thought of a good brief output, posted first in this answer now. – Will Jagy Jun 21 '14 at 22:32 Could you post a gist of your script? – WChargin Jun 22 '14 at 1:53 The answers so far seem to be not definitive. This summand is called the Liouville$\lambda$function, and this exact question was conjectured by Pólya (in the opposite direction, which would have implied the Riemann Hypothesis): https://en.wikipedia.org/wiki/Pólya_conjecture. As it turns out, it does change sign infinitely often, so Pólya's conjecture is false. This was first shown by Haselgrove in 1958 (as well as for the Mertens function). The first sign change occurs just shy of a billion,$n = 906150257$. See also "Sign changes in sums of the Liouville function" by Borwein, Ferguson and Mossinghoff for some more references. EDIT: The Liouville function is$(-1)^{\Omega(n)}$, not$(-1)^{\omega(n)}\$, so it doesn't apply to this exact question. So my answer is still not definitive, just suggestive.

-
Very much appreciated nonetheless. – David R. Oct 10 at 19:38

With some elementary facts of the analytic number theory especially with the Perron's formula, at least we can know its rough estimation via big-O function.

In this case, we have $$f(x) = \frac{1}{2\pi i}\int_{L} \frac{\zeta(s)}{s}\prod_{p\geq 2}\Big( 1-\frac{2}{p^s} \Big)x^s ds$$ by the Perron's formula. And since the part of the product is \begin{align*} \frac{1}{\zeta(s)^2}\bigg(\prod_{p\geq 2} 1-\frac{1}{(p^s-1)^2}\bigg)=\frac{1}{\zeta(s)^2}\bigg(\prod_{p\geq 2}1-\frac{1}{p^{2s}}-\frac{2}{p^{3s}}-\frac{3}{p^{4s}}-\cdots\bigg), \end{align*} we have $$f(x)=O\Big(\max_{y\in[1,x]}\{|M(y)|\}\prod_{p} 1+\frac{1}{(p^s-1)^2}\Big)=O\Big(\max_{y\in[1,x]}\{|M(y)|\}\Big).$$

-