12
$\begingroup$

Suppose I have some operation $f(n)$ that is given as

$$f(n)=\sum_{k\ge1}\frac1{a_k}$$

Where $a_k$ is the $k$th factor of $n$.

For example, $f(100)=\frac11+\frac12+\frac14+\frac15+\frac1{10}+\frac1{20}+\frac1{25}+\frac1{50}+\frac1{100}=\frac{217}{100}$

$f(101)=\frac11+\frac1{101}=\frac{102}{101}$

$f(102)=\frac11+\frac12+\frac13+\frac16+\frac1{17}+\frac1{34}+\frac1{51}+\frac1{102}=\frac{216}{102}$

I was wondering if it were possible to plot a graph of $f(n)$ and wondered if there were any interesting patterns. I was also wondering if there is a closed form representation and if $\lim_{n\to\infty}f(n)$ could be evaluated or determined to be finite or not or any other interesting things that might happen in this limit.

Secondly, I was wondering about another similar series, which considers $b_k$ as the $k$th prime factor of $n$.

$$p(n)=\sum_{k\ge1}\frac1{b_k}$$

What can we determine about this series?

$\endgroup$
13
  • 1
    $\begingroup$ I wouldn't call that $\mu$ because there a fairly common function by that name that is similar. $\endgroup$ Mar 11 '16 at 23:51
  • $\begingroup$ @ThomasAndrews Fine. I just think greek letters are pretty to use for things. $\endgroup$ Mar 11 '16 at 23:52
  • 5
    $\begingroup$ A more standard name would be $\sigma_{-1}$. See Divisor function. $\endgroup$ Mar 12 '16 at 0:03
  • 1
    $\begingroup$ The graph of this would be quite interesting. There would be ``gaps" at all the primes. However, that might be hard to see. $\endgroup$ Mar 12 '16 at 0:16
  • 1
    $\begingroup$ Here are plots for the first 100k integers: i.imgur.com/XDyVK7p.png and for the first 10 million: i.imgur.com/y5SYGOd.png The largest value in this range is obtained for $8648640 = 2^6 × 3^3 × 5× 7 × 11× 13$ $\endgroup$ Mar 12 '16 at 17:30
25
$\begingroup$

Note that $n\cdot f(n)$ is the sum of the factors of $n$ (written in a different order), which is denoted by $\sigma(n)$. Thus, $\displaystyle f(n)={\sigma (n)\over n}$.

$\endgroup$
3
  • $\begingroup$ Hm, interesting. Thank you. $\endgroup$ Mar 11 '16 at 23:50
  • 1
    $\begingroup$ This function is sometimes called the abundancy of a number, since $n$ is abundant if $f(n) > 2$, deficient if $f(n) < 2$, and perfect if $f(n) = 2$. See mathworld.wolfram.com/Abundancy.html. Note that Wikipedia (en.wikipedia.org/wiki/Abundant_number) uses the word "abundance" to mean something related but different, and "abundancy index" for your $f(n)$. $\endgroup$ Mar 12 '16 at 2:34
  • 1
    $\begingroup$ @RaviFernando Yes, usually abundance is the difference $\sigma(n) - 2n$ while abundancy is the ratio $\frac{\sigma(n)}{n} = \sigma_{-1}(n)$. But one may have to repeat that definition to make sure everyone knows. A number whose abundancy is an integer, is called a multiply perfect number. Two or more numbers sharing the same abundancy are called friendly numbers. $\endgroup$ Mar 12 '16 at 10:40
7
$\begingroup$

Let $X_k$ be the product of the first $k$ primes. Let $Z_k$ be the sum of the reciprocals of the first $k$ primes. Then clearly $f(X_k)>Z_k$, and it's well known that $Z_k$ is unbounded, so $f(a_k)$ cannot have a finite limit. On the other hand, if $P_k$ is the $k$'th prime, then $f(P_k)$ clearly goes to $1$. Therefore $f(a_k)$ cannot have a limit other than $1$. Therefore $lim_{k\rightarrow\infty}a_k$ cannot exist.

$\endgroup$
7
  • $\begingroup$ How did you arrive at $f(P_k)$ going to $1$? I do not see this. (And us \lim for limits) $\endgroup$ Mar 12 '16 at 0:16
  • $\begingroup$ $f(P_k)$ goes to $1$ by euclid's theorem. $\endgroup$
    – WillO
    Mar 12 '16 at 0:17
  • $\begingroup$ @SimpleArt: if $p$ is prime then $f(p) = 1 + \frac{1}{p}$. The limit of this is $1$. $\endgroup$ Mar 12 '16 at 1:30
  • 6
    $\begingroup$ @SimpleArt: if it's not prime then it's not one of the $P_k$ that WillO is talking about in that sentence. WillO is saying that your sequence has one subsequence that tends to infinity, and another subsequence that tends to $1$. Therefore the sequence has no limit (proof left as exercise). It doesn't matter how dense each subsequence is, only that they both have infinitely many terms. $\endgroup$ Mar 12 '16 at 1:34
  • 1
    $\begingroup$ Note that the Wikipedia section Divisor function § Growth rate has more to say. Remember that $f(n)=\frac{\sigma(n)}{n}$ (Carl Heckman's answer). Then that section says that Grönwall's theorem is: $$\limsup_{n\to\infty} \frac{f(n)}{\log \log n} = e^\gamma$$ And it says that Robin's inequality (valid under the assumption of the Riemann hypothesis) says that every $n>5040$ has $\frac{f(n)}{\log \log n} < e^\gamma$. $\endgroup$ Mar 12 '16 at 10:54
7
$\begingroup$

Ramanujan included this in his original paper on Highly Composite Numbers, originally 1915. http://math.univ-lyon1.fr/~nicolas/ramanujanNR.pdf However, this was in a section left out because of paper shortages.

Let's see, I asked about this on MO https://mathoverflow.net/questions/137865/estimate-term-in-ramanujan-lost-notebook-classic-analytic-number-theory but did not quite get what I wanted, so I wrote to Nicolas. He's a nice man, but he had never heard of me, and the websites I mentioned were unknown to him. Sigh. Anyway, he did answer.

In brief, Ramanujan's construction allows us to produce a sequence of numbers, each new one the previous one times a prime, so that the function $\sigma(n)/n$ is surprisingly large for $n$ of that size. In turn, this gives explicit bounds on the function.

For numerical experiments of your own, the easiest way to approximate the numbers in this sequence is simply to take $$ n = \operatorname{lcm} \{1,2,3, \ldots, k \} $$ and put $n$ into the sequence when it increases, which happens only when $k$ is a prime or prime power. Extremely approximately, $n \approx e^k.$ From Robin's criterion and related stuff, we will have $$ \frac{\sigma(n)}{n} \approx e^\gamma \log \log n \approx e^\gamma \log k, $$ where $ n = \operatorname{lcm} \{1,2,3, \ldots, k \} .$ Note that $e^\gamma \approx 1.7810724.$ Also note that it is the Prime Number Theorem that says that $\log n \approx k.$

Did it myself:

2 n = 2 =  2  function:  1.5 over log k:  2.16404
3 n = 6 =  2 3  function:  2 over log k:  1.82048
4 n = 12 =  2^2 3  function:  2.33333 over log k:  1.68314
5 n = 60 =  2^2 3 5  function:  2.8 over log k:  1.73974
7 n = 420 =  2^2 3 5 7  function:  3.2 over log k:  1.64447
8 n = 840 =  2^3 3 5 7  function:  3.42857 over log k:  1.64879
9 n = 2520 =  2^3 3^2 5 7  function:  3.71429 over log k:  1.69044
11 n = 27720 =  2^3 3^2 5 7 11  function:  4.05195 over log k:  1.68979
13 n = 360360 =  2^3 3^2 5 7 11 13  function:  4.36364 over log k:  1.70126
16 n = 720720 =  2^4 3^2 5 7 11 13  function:  4.50909 over log k:  1.62631
17 n = 12252240 =  2^4 3^2 5 7 11 13 17  function:  4.77433 over log k:  1.68513
19 n = 232792560 =  2^4 3^2 5 7 11 13 17 19  function:  5.02561 over log k:  1.70681
23 n = 5354228880 =  2^4 3^2 5 7 11 13 17 19 23  function:  5.24412 over log k:  1.6725
25 n = 26771144400 =  2^4 3^2 5^2 7 11 13 17 19 23  function:  5.41892 over log k:  1.68348
27 n = 80313433200 =  2^4 3^3 5^2 7 11 13 17 19 23  function:  5.55787 over log k:  1.68633
29 n = 2329089562800 =  2^4 3^3 5^2 7 11 13 17 19 23 29  function:  5.74952 over log k:  1.70746
31 n = 72201776446800 =  2^4 3^3 5^2 7 11 13 17 19 23 29 31  function:  5.93499 over log k:  1.72831
32 n = 144403552893600 =  2^5 3^3 5^2 7 11 13 17 19 23 29 31  function:  6.03071 over log k:  1.7401
37 n = 5342931457063200 =  2^5 3^3 5^2 7 11 13 17 19 23 29 31 37  function:  6.1937 over log k:  1.71527
41 n = 219060189739591200 =  2^5 3^3 5^2 7 11 13 17 19 23 29 31 37 41  function:  6.34477 over log k:  1.70854
43 n = 9419588158802421600 =  2^5 3^3 5^2 7 11 13 17 19 23 29 31 37 41 43  function:  6.49232 over log k:  1.72613
47 n = 442720643463713815200 =  2^5 3^3 5^2 7 11 13 17 19 23 29 31 37 41 43 47  function:  6.63046 over log k:  1.72213
49 n = 3099044504245996706400 =  2^5 3^3 5^2 7^2 11 13 17 19 23 29 31 37 41 43 47  function:  6.74886 over log k:  1.73411
53 n = 164249358725037825439200 =  2^5 3^3 5^2 7^2 11 13 17 19 23 29 31 37 41 43 47 53  function:  6.8762 over log k:  1.73191
59 n = 9690712164777231700912800 =  2^5 3^3 5^2 7^2 11 13 17 19 23 29 31 37 41 43 47 53 59  function:  6.99274 over log k:  1.71494

In comparison, the function for, say, $n$ prime is very small, just $1 + (1/n).$

$\endgroup$
2
  • $\begingroup$ Good answer and it includes a nice approximation to growth rates. Thanks. $\endgroup$ Mar 12 '16 at 2:01
  • $\begingroup$ @SimpleArt I put in some more detail. The largest your function gets is about $e^\gamma \log \log n,$ slowly growing but not bounded. $\endgroup$
    – Will Jagy
    Mar 12 '16 at 2:27
5
$\begingroup$

Just for the fun of it, I've graphed this up to $n=18$

Here is the data:

enter image description here

As you can see, the points move all over the place. Over this domain, it does seem to have a local maximum at every even number though. Perhaps this is because they have the advantage of a plus $1/2$

Here is the table I made if anyone wants to double check it:

enter image description here

Also, here is the link to the graph

$\endgroup$
2
  • 1
    $\begingroup$ Just a note about your "local maximum at every even number" statement. Although that does happen in this range, and probably "usually" happens for large $n$ (although it would be interesting to try to prove this), it isn't always true. For example, the first odd abundant number (i.e. where $f(n) > 2$) is 945, but 944 and 946 are both deficient ($f(n) < 2$). $\endgroup$ Mar 12 '16 at 4:48
  • $\begingroup$ Ya thanks for pointing that out. I was just talking about this range though. $\endgroup$
    – user311559
    Mar 12 '16 at 5:06
3
$\begingroup$

Here is the plot of $f(n)=\frac{\sigma(n)}{n}$ .
Patterns in these plots are amazing!
For $1000$

enter image description here

And here is for $100,000$
enter image description here
This diagram shows the $\lim_{x\to \infty} f_n$ isn't plausible !

$\endgroup$
1
  • $\begingroup$ Just saying, this is awesome $\endgroup$
    – user311559
    Mar 21 '16 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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