Асимптотика сумм с функцией Мёбиуса

[Sonic86]

Руст в сообщении #472384 писал(а):

Можно ограничиться до $10^8$. Если можно сделать график указанной функции, было бы хорошо.

Программа рассчитала за полчаса. Но дело не в этом. Файл весит 1,5 Гб, архив - 150 Мб. Файл блокнотом не открывается (оперативы не хватает). И кроме Excelя у меня нет других средств построения графиков (да и вообще, если 10 точек на 1 мм, то $10^4$ метров надо на график.) Как-то его зажимать или усреднять нецелесообразно - пропадут максимумы. Да и выглядеть это будет так, словно кривая почти заполняет всю область.
В общем, я посчитал только максимумы и минимумы для сумматорной функции. Их получилось около 7000, вот они:

Вот так максимумы зажимаются для $f(n)$:

(как и должно быть - функция ограничена)
Я еще пытался выделить одну четверть из всех максимумов - получается все равно много. Если сейчас еще что-то получится - выложу.

(код программы)

Примитивно:

#include "stdafx.h"
#include <fstream>
#include <iostream>
#include <math.h>
using namespace std;

int main()
{  
   int i,f,d,S,Smin,Smax;
   long long k,j,n;
   int P[3402]; // здесь хранятся простые числа до корня из n
   fstream ext, pr;
   pr.open("Primes.txt",ios::in);
   for(i=0;i<3402;i++){pr>>P[i];}
   pr.close();
   n=100000000;
   ext.open("Extremums and summatory function of Moebius function.txt",ios::out);
   ext<<1<<'\t'<<1<<'\t'<<1<<'\n';
   S=1; Smin=1; Smax=1;
   for(j=2;j<=n;j++){
      k=j; i=0; d=P[0]; f=1;
      while(d*d<=k && f!=0){
         if(k%d==0){
            k=k/d;
            if(k%d==0){f=0;}
            else{f=-f;}
         }
         i++; d=P[i];
      }
      if(k>1){f=-f;}
      S+=f;
      if(S>Smax){
         Smax=S;
         ext<<j<<'\t'<<Smin<<'\t'<<Smax<<'\n';
      }
      if(S<Smin){
         Smin=S;
         ext<<j<<'\t'<<Smin<<'\t'<<Smax<<'\n';
      }
      if(j%100000==0){cout<<j<<endl;}
   }
   ext.close();
}

[Sonic86]

Руст в сообщении #472332 писал(а):

Что касается $\sum_{k=1}^n\frac{\mu(k)}{k}$, то элементарными путями можно вывести $O(\frac{1}{\ln n})$. Только я не уверен, что коэффициент получится 1.

Из решета Эратосфена имеем:
$\pi (n) - \pi (\sqrt{n})+1 = \sum\limits_{1 \leqslant d \leqslant n} \mu (d) \left[ \frac{n}{d} \right] = n \sum\limits_{1 \leqslant d \leqslant n} \frac{\mu (d)}{d} +R(n)$
Левая часть $\sim \frac{n}{\ln n}$. Предполагая, что $R(n)=o(\sum)$, получаем, что $\sum\limits_{1 \leqslant d \leqslant n} \frac{\mu (d)}{d} \sim \frac{1}{\ln n}$ все-таки с коэффициентом 1. Иначе $R(n) \sim \frac{n}{\ln n}$.
(все-таки мне кажется, что коэффициент отличается от коэффициента в произведении по простым).

[Руст]

Спасибо за графики. Я не ожидал, что график заполняет всю область. Предполагал, что после нормировки на $\sqrt n$ функция ведет себя более менее гладко как сумма множество синусов со случайными зигзагами, но гладко.

[Sonic86]

Руст в сообщении #472455 писал(а):

Спасибо за графики. Я не ожидал, что график заполняет всю область. Предполагал, что после нормировки на $\sqrt n$ функция ведет себя более менее гладко как сумма множество синусов со случайными зигзагами, но гладко.

Я кажется просто неправильно выразился. Я просто объяснял, почему я не смогу нарисовать график для $n \leqslant 10^8$ - это же очень много. Для $n \leqslant 6 \cdot 10^4$ могу - он тут различимо выглядит:

Для $n \leqslant 3 \cdot 10^5$ так:


-- Вс июл 31, 2011 18:16:59 --

Sonic86 в сообщении #472431 писал(а):

Да и выглядеть это будет так, словно кривая почти заполняет всю область.

Это я наврал - кривая вполне различима.
Но технических средств рисования таких графиков для гигантских $n$ у меня все равно нету.

[Руст]

Так более понятно. Как и ожидалось после нормировки на $\sqrt n$, соответствующей действительной части нулей дзета функции, остаются колебания в виде суммы многих синусов, связанных с мнимыми частями нулей дзета функции.