Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I bet you a quarter it does. I've got no mathematical justification for that, though. –  Mike Miller Jun 21 at 20:15
1  
@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 at 17:39

2 Answers 2

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;
       }
     }
}

share|improve this answer
    
Are you saying that it's never strictly negative? –  TonyK Jun 21 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 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 at 21:55
    
@TonyK, thought of a good brief output, posted first in this answer now. –  Will Jagy Jun 21 at 22:32
    
Could you post a gist of your script? –  WChargin Jun 22 at 1:53

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.