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$.
Solution 1:
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;
}
}
}
Solution 2:
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.