Faktoren von $2n^2 \leq n$?

Dec 11 2020

Wie viele Faktoren von $2n^2$ sind kleiner oder gleich $n$? Ich weiß, dass die Anzahl der Faktoren von$n^2$ weniger als $n$ ist die Hälfte der Anzahl von Faktoren von $n^2$ (jeder Faktor $< n$ entspricht einem größer als $n$), aber $2n^2$ist ein ganz anderer Fall, wie es scheint. Gibt es eine Möglichkeit, einen Ausdruck dafür zu finden? Und wenn nicht, gibt es einen Algorithmus dafür? Ich habe mich sowohl mit Kombinatorik als auch mit Primfaktorisierung befasst, bin aber zu Sackgassen gekommen.

Antworten

1 DavidG.Stork Dec 11 2020 at 11:53

Ich sehe keine allgemeine analytische Lösung, da dies von der Primfaktorisierung von abzuhängen scheint $n$.

Das OP fragt aber auch nach Code. Das ist sehr einfach. In Mathematica :

myfun[n_: Integer] := Length[
Select[Divisors[2 n^2], # <= n &]]

Damit:

myfun[9098345]

(* 27 *)

Hier ist eine Handlung:


Dies ist nicht direkt Teil des Problems, scheint aber die Motivation des Problems zu sein. Wenn die obige Funktion ist$f(n)$, Berechnung $F(N) = \sum\limits_{n=1}^N f(n)$, zum $N = 10^{12}$.

Ich denke, der Ansatz ist der folgende: Berechnen Sie die Anzahl von$2$s in dieser Summe. Berechnen Sie dann die Anzahl der$3$s. Und so weiter, dann addieren Sie sie.

Die Anzahl der $2$s ist $10^{12}/2$. Die Anzahl der$3$s ist $10^{12}/3$. Usw. Aber wie hoch ist das Maximum, das wir in der Gesamtberechnung addieren? Ich denke, es sollte der größte zulässige Faktor in der sein$10^{12}$ (letzter) Term in der Summe, dh $k_{max} = \sqrt{50} \cdot 10^5 = 707107$erhalten von der $2 n^2 = 10^{12}$ Berechnung.

Wenn das stimmt, dann: $F(10^{12}) = 10^{12} \sum\limits_{k = 1}^{k_{max}} \frac{1}{k} = 10^{12}\ {\rm HarmonicNumber}(k_{max}) = 10^{12} \cdot 14.0461536491411$.

Es gibt wahrscheinlich einige Rundungsartefakte, die enthalten sein müssen, aber ich denke, dies ist der richtige Ansatz. Jemand sollte dies mit größerer Sorgfalt tun.

2 Math_Buddy Dec 11 2020 at 11:52

Dies ist eine sehr interessante Frage. Annehmen$n=2^{a}(2k+1)$ für eine ganze Zahl $a$ und $k$. Sei f (x) = Anzahl der positiven Teiler der ganzen Zahl x. Da Faktoren von$2n^2\leq n$ Wir brauchen eine Reihe von Faktoren von $2^{2a+1}(2k+1)^2$. So haben wir$f(2^a(2k+1))+c_{a}$.Wo $c_{a}$ist der Fehlerfaktor hat einen kleinen gebundenen Faktor, der deterministisch sein muss. Obwohl es eine grobe Idee ist, finde ich die Grenze nicht, aber für Hinweise können Sie kleine Fälle versuchen. Jedoch lassen$g(x)=$größte ganze Zahl kleiner gleich x dann, $$c_{a}\leq f(g(2^{\frac{2a+1}{2}}(2k+1)))-f(2^a(2k+1))$$Wo wir wissen $f$ ist berühmte Teilerfunktion oder $\tau$ Funktion und $g$ist die Bodenfunktion. Verwenden Sie diesen Link für die Grenze, die Untergrenze für die Summe der Divisorfunktionen