$$f(n) = \sum_{i = 1}^n (-1)^{\omega(i)}$$
donde $\omega(n)$ cuenta cuántos factores primos $n$.
No veo ninguna señal de los cambios más allá de $n = 49$, pero sólo he calculado a $n = 1{,}000$.
Respuestas
¿Demasiados anuncios?
Stephan Aßmus
Puntos
16
Pensé en un breve resumen. Comenzando con 12,100 y va hasta 100.000.000 de, aquí están las apariciones de múltiplos de 1000, pero no dos de la misma cosa en una fila. Así, se puede esperar que el valor se movera 0 (y repite) durante bastante tiempo después de cada impreso ocurrencia de 0. Tiene muy largos tramos en los que es negativo, pero infinitamente muchos cambios de signo parece ser la mejor opcion. Si esto se puede resolver, la información a ser utilizada en la Sección 7.4 de la Montgomery-Vaughan Multiplicativo de la Teoría de los números I. Teoría Clásica.
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:~$
Sólo donde es 0. La cosa es negativa desde 12,101 a 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
aquí es una buena cadena,
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;
}
}
}
Erick Wong
Puntos
12209
Las respuestas hasta ahora parece que no será la definitiva. Este sumando se llama la Liouville $\lambda$ función, y esta pregunta exacta fue conjeturado por Pólya (en la dirección opuesta, lo que habría implicado la Hipótesis de Riemann): https://en.wikipedia.org/wiki/Pólya_conjecture.
Pues resulta, que hace cambiar el signo infinitamente a menudo, así que Pólya la conjetura es falsa. Esto fue mostrado por primera vez por Haselgrove en 1958 (así como para la función de Mertens). La primera señal de que el cambio se produce apenas por debajo de los mil millones, $n = 906150257$. Véase también "Signo de los cambios en las sumas de la función de Liouville" por Borwein, Ferguson y Mossinghoff para más referencias.
EDIT: La función de Liouville es $(-1)^{\Omega(n)}$, no $(-1)^{\omega(n)}$, por lo que no se aplican a esta pregunta exacta. Así que mi respuesta no es definitiva, sólo sugerente.
B . O
Puntos
53
Con algunos hechos elementales de la teoría analítica de números, especialmente con el Perron de la fórmula, al menos podemos saber su estimación aproximada a través de big-O función.
En este caso, tenemos $$ 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 $$ por la Escalera de la fórmula. Y desde la parte del producto se \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*} tenemos $$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).$$
