Czynniki $2n^2 \leq n$?

Question

Ile czynników $2n^2$ są mniejsze lub równe $n$? Wiem, że liczba czynników$n^2$ mniej niż $n$ to połowa liczby czynników $n^2$ (każdy czynnik $< n$ odpowiada jeden większy niż $n$), ale $2n^2$wydaje się, że to zupełnie inny przypadek. Czy jest jakiś sposób, aby znaleźć na to wyrażenie? A jeśli nie, to czy istnieje na to algorytm? Przyjrzałem się zarówno kombinatoryce, jak i rozkładowi na czynniki pierwsze, ale doszedłem do ślepych zaułków.

Answer 1

Nie widzę ogólnego rozwiązania analitycznego, ponieważ wydaje się, że zależy to od pierwotnej faktoryzacji $n$.

Ale OP prosi również o kod. To bardzo proste. W Mathematica :

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

Więc:

myfun[9098345]

(* 27 *)

Oto fabuła:

---

To nie jest bezpośrednio częścią problemu, ale wydaje się być motywacją problemu. Jeśli powyższa funkcja to$f(n)$, Oblicz $F(N) = \sum\limits_{n=1}^N f(n)$, dla $N = 10^{12}$.

Myślę, że podejście jest następujące: Oblicz liczbę$2$s w tej sumie. Następnie oblicz liczbę$3$s. I tak dalej, a następnie dodaj je.

Liczba $2$jest $10^{12}/2$. Liczba$3$jest $10^{12}/3$. I tak dalej. Ale jakie jest maksimum, które dodajemy do sumy obliczeń? Myślę , że powinien to być największy dozwolony czynnik w$10^{12}$ (ostatni) termin w sumie, tj. $k_{max} = \sqrt{50} \cdot 10^5 = 707107$, uzyskany z $2 n^2 = 10^{12}$ obliczenie.

Jeśli tak, to: $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$.

Prawdopodobnie istnieje kilka artefaktów zaokrąglenia, które należy uwzględnić, ale myślę, że jest to właściwe podejście. Ktoś powinien to zrobić z większą ostrożnością.

Answer 2

To bardzo interesujące pytanie. Założyć$n=2^{a}(2k+1)$ dla jakiejś liczby całkowitej $a$ i $k$. Niech f (x) = liczby dodatnich dzielników liczby całkowitej x. Ponieważ czynniki$2n^2\leq n$ potrzebujemy wielu czynników $2^{2a+1}(2k+1)^2$. Tak mamy$f(2^a(2k+1))+c_{a}$.Gdzie $c_{a}$to współczynnik błędu ma mały współczynnik ograniczenia, który musi być deterministyczny. Chociaż to przybliżony pomysł, nie szukam oprawy, ale dla wskazówek możesz wypróbować małe skrzynki. Jednak niech$g(x)=$wtedy największa liczba całkowita mniejsza równa x, $$c_{a}\leq f(g(2^{\frac{2a+1}{2}}(2k+1)))-f(2^a(2k+1))$$.Gdzie wiemy $f$ jest słynną funkcją dzielnika lub $\tau$ funkcja i $g$jest funkcją podłogi. Użyj tego linku dla granicy, Dolna granica dla sumy funkcji dzielnika