Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [divisor-counting-function]

For questions that involve the divisor counting function, also known as $\tau$ or $\sigma_0$.

1
vote
0answers
12 views

Show that $\sigma=c_1*c_1$, where $c_1$ is the constant function $1$.

I searched and wasn't able to find a question similar enough to mine. Here's the problem: Show that $\sigma=c_1*c_1$, where $c_1$ is the constant function $1$. Here is my attempt. My argument ...
0
votes
2answers
26 views

Prove that there exist infinitely many $n$ such that $d(n+1)>d(n)$, where $d(n)$ is number of positive factors

Prove that there exist infinitely many $n$ such that $d(n+1)>d(n)$, where $d(n)$ is number of positive factors of $n$. I have think of using proof by contradiction, by setting a largest integer $k$...
1
vote
0answers
17 views

Wave Divisor Function

For quit some time (years) I have been playing around with the divisor function (counting the number of divisors for a given integer). I created a 10 slide summary in the attached presentation. Wave ...
0
votes
1answer
43 views

Number of Pythagorean Triples

I am trying to solve an exercise from the book "Theory of Numbers" by B.M.Stewart. The exercise is the following one: Let $T=2^ap_1^{a_1}p_2^{a_2} \dots p_n^{a_n}$, where $a \ge0, n\ge0, 2<p_1&...
1
vote
0answers
50 views

Transforming a sum of products in a product of sums

I am studying the proof for the formula of $\sigma (n)$, the divisor function. At a certain point there is this equivalence but I can't see how it works: $$\sum_{b_i \in \{0,1,\dotsc a_i\}}{p_1^{b_1} ...
2
votes
0answers
54 views

Truncated sum of divisors bound

I am interested in an upper bound for $$ \sum_{\substack{d|N\\ d>A}}\frac{1}{d^3},$$ in particular, I can get the above to be $$\sum_{\substack{d|N\\ d>A}}\frac{1}{d^3}\ll \frac{\text{exp}\...
-1
votes
1answer
74 views

Relation between The Euler Totient, the counting prime formula and the prime generating Functions [closed]

](https://i.stack.imgur.com/lKFS0.png) Relation between The Euler Totient, the counting prime formula and the prime generating Functions There is a formula for the ivisor sum hiih is one of the ...
2
votes
1answer
57 views

The number of decompositions of $2n-1$ into a difference of two squares?

Is there a exact formula for number of decompositions of $2n-1$ into a difference of two squares? Examples: ...
3
votes
1answer
36 views

How to distribute 5 cards among 3 people $A,B,C$ so that none of the person have empty hands

How to distribute 5 cards among 3 people $A,B,C$ so that none of the person have empty hands? My try: 5 cards can be distributed among $A,B,C$ in $2,2,1$ ways. Now there are three ways of arranging $...
1
vote
1answer
37 views

Growth rate of a divisor function

Hi I read an very interesting article about divisor function: https://en.wikipedia.org/wiki/Divisor_function#CITEREFHardyWright2008 I was wondering about a formula which appear under the Growth rate ...
0
votes
2answers
38 views

ELI5: Explanation of why the product of divisors of a natural $n$ is always $n^{\frac{d(n)}{2}}$ where $d(n)$ gives the number of divisors

I tried reading the answers on Product of Divisors of some $n$ proof and unfortunately couldn't understand them. The accepted answer mentions that ${\displaystyle\prod_\limits{d|n}{d^2}=\prod_\limits{...
0
votes
0answers
25 views

Formula for product of sums of pairs of coprime divisors of $n$.

Can we develop a formula for $$ r(n)=\prod_{ \begin{array}{c} x,y\mid n \\ (x,y)=1 \end{array}} (x+y) $$ In words this is the product of sums of all coprime pairs of divisors of $n$. For example $$...
3
votes
2answers
117 views

A proof of $\sum\limits_{d|n} \sigma(d) = n \sum\limits_{d|n} {\tau(d) \over d}$

I'm trying to proof the following statement: Let $n \in \mathbb{Z}$ and the $\sum$ are on the divisors $d$ of $n$. Show that $$\sum\limits_{d|n} \sigma(d) = n \sum\limits_{d|n} {\tau(d) \over d}.$$ ...
4
votes
1answer
87 views

Interchanging summation involving divisors in index

I was reading Apostle's Analytic Number Theory book and I saw this formula being used in many cases. Why is this true? $$ \sum_{n=1}^{\infty} \sum_{d|n} f(d,n) = \sum_{d=1}^{\infty} \sum_{n=1}^{\...
1
vote
0answers
48 views

Asymptotics and bounds of $k$-divisor function $d_k(n)$

Let $d_k(n)$ be the $k$-divisor function, i.e., it is a number of ways to represent $n$ as a product of $k$ natural numbers. I'm interested in the asymptotic behavior (or, at least, in upper bounds) ...
0
votes
2answers
225 views

how to find odd number of odd divisors between 1 to n

Like In range of 1 to 3 there is 2 numbers who has odd number of odd divisors In range 5 to 10 there is 2 numbers who has odd number of odd divisors In range 5 to 10 there is no numbers who has odd ...
-1
votes
1answer
67 views

Let $\sum\limits_{n=1} ^{\infty} \frac{z^n}{1-z^n}$. Show that [closed]

Let $\sum_{n=1} ^{\infty} \dfrac{z^n}{1-z^n}$. Show that $F(z)=\sum_{n=1} ^{\infty} d(n)z^n$ Where $d(n)$ represents the numbers of divisors of $n$. Does anyone have any idea how to start?
0
votes
0answers
45 views

Counting Natural Solutions to Certain Quadratic Equations

I am interested in counting the number of distinct solutions (wlog, a < b) to this equation for a fixed value of y. $$\frac{x}{y} = \frac{1}{a} + \frac{1}{b}; a, b, y \in \mathbb{N}_+$$ I can ...
13
votes
5answers
945 views

Why multiplying powers of prime factors of a number yields number of total divisors?

Suppose we have the number $36$, which can be broken down into ($2^{2}$)($3^{2}$). I understand that adding one to each exponent and then multiplying the results, i.e. $(2+1)(2+1) = 9$, yields how ...
0
votes
0answers
44 views

Asymptotics of divisor function

I know that the definition of a perfect number is that its divisor function value is equal to double the number, i.e., $$\sigma(n) = 2n$$ By accident I came across the number $250801742479451287$, ...
0
votes
0answers
43 views

Upper bound for the divisor counting function?

I'm looking to find an explicit upper bound for the divisor counting function, $d(n)$. This function counts the number of divisors of a number - e.g. 15 has divisors, $1, 3, 5, 15$, hence $d(15)=4$....
3
votes
0answers
71 views

Is there a closed expression for $\sum_{n =2}^{\infty}\pi(n)z^n$?

Is there a closed expression for $\sum_{n =2}^{\infty}\pi(n)z^n$? I mean, Is there a representation for this power series? Here $\pi(n)$ is the number of primes less or equal than $n$.
-1
votes
1answer
44 views

Find the least positive integer with 24 positive divisors [closed]

Find the least positive integer with $24$ positive divisors If we assume the integer is $=a^x.b^y.....$ And $(x+1)(y+1)......=24$ Then there are too many variables How can I get least variables?
3
votes
1answer
82 views

$\phi(n)^{\sigma(n)^{\tau(n)}}=n^2$ find all natural numbers $n$ such that the equality is true

I found this problem in a old number theory test about arithmetic functions. The problem says that a number $n \in N$ is "perfectly crazy" if $$\phi(n)^{\sigma(n)^{\tau(n)}}=n^2,$$ and, as an example, ...
0
votes
0answers
57 views

Is there a general formula for finding the smallest non-trivial positive divisor of a natural number?

For instance, the smallest non-trivial positive divisor ("sntpd") of $12$ is $2$, the sntpd of $25$ is $5$, the sntpd of $9$ is $3$, etc. So I'd like to know if there's a formula that given a ...
1
vote
0answers
35 views

Can the multiplication formula for the Hurwitz zeta function be extended to include this sum?

While searching the internet for the Hurwitz zeta function I found this Mathematics stack exchange question: The multiplication formula for the Hurwitz zeta function $$\zeta(s,mz) = \frac{1}{m^{s}} \...
0
votes
1answer
93 views

Has $\sigma\left(\sigma_0(n)^4\right)=n$ infinitely many solutions?

In this post, for integers $n\geq 1$ we consider the sum of divisors function $\sum_{d\mid n}d$ denoted as $\sigma(n)$ and the divisor-counting function $\sum_{d\mid n}1$ as $\sigma_0(n)$. Then I ...
2
votes
1answer
62 views

Can I efficiently (without brute force) determine the smallest number having the given property? [closed]

If $d(n)$ denotes the number of positive divisors of $n$ , define $$f(n):=d(n)\cdot d(n+1)$$ Can I find efficiently (without brute-force) the smallest integer $n\ge 1$ such that $f(n)\ge m$ , for a ...
0
votes
2answers
25 views

Proof of sum of positive divisors of $n$ (probably repeated question somewhere in the stack)

If $\tau(n)$ is the number of positive divisors of $n$, including 1 and $n$, prove that $$ S_\tau(x) = \sum_{n\leq x} \tau(n) = \sum_{j\leq x}\left[ \frac{x}{j} \right], $$ where $[x]$ is the ...
7
votes
2answers
454 views

A conjecture concerning the number of divisors and the sum of divisors.

I stumbled upon the following conjecture: Let $n$ be a positive integer. Let $\sigma\left(n\right)$ be the sum of all (positive) divisors of $n$, and let $\tau\left(n\right)$ be the number of these ...
0
votes
3answers
460 views

Modified sieve to find count all the divisors from 1 to n in o(n) time

I trying to solve a problem that involves finding the number that has the maximum factors from 1 to $N$ where $N = 10^7$ in just under 2 seconds. I have implemented a sort of "sieve" that starts from ...
0
votes
1answer
52 views

Help in showing that a function is multiplicative

I am solving this same very question: For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$ I want to approach this question via proving the multiplicativity of the ...
-1
votes
1answer
65 views

If an odd perfect number exist could be a solitary number? [closed]

Perfect numbers is a number that is half the sum of all of its positive divisors .And solitary numbers means that $\frac {\sigma(n)}{n}$ is an irreducible fraction, it's seems to me that all even ...
1
vote
1answer
87 views

Bound on Divisor Counting Function

Let $d(n)$ be the number of divisors of n. I'm trying to figure out if there is a constant C such that \begin{equation} d(n) \leq (ln(n))^C \end{equation} My guess is there is no such constant. I ...
0
votes
1answer
45 views

Weighted Sum of Divisor Function For the first N Natural Numbers

Good day to you. The Function : $ F(N) =\sum_{i=1}^{N} \sum_{d|i} 1 $, i.e the function that summarizes the divisors of the first $N$ natural numbers can also be expressed as : $ F(N)=\sum_{i=1}^{...
1
vote
2answers
67 views

Equivalent formula for the sum of first $n$ values of the number of divisors function

In the notes of the following OEIS sequence( https://oeis.org/A006218), it is stated that $$\sigma_0(1) + \sigma_0(2) +... + \sigma_0(n) = \left[ \dfrac{n}{1} \right] + \left[ \dfrac{n}{2} \...
5
votes
1answer
104 views

Analytical Way of Estimating Sums of Floor Functions

Hi Math Stack Exchange, I'm working on a problem that involves the difference between a sum series of floor functions. I have tried taking the more standard number theory approach by looking at ...
0
votes
1answer
21 views

Integers with prescribed divisor count

Given an integer $n\in\Bbb N$ is there always an integer with $n^2$ divisors? How to find such integers?
1
vote
1answer
37 views

A simple representation that satisfies every even perfect number: products over the squarefree parts of its divisors

I wrote a draft of next statement for even perfect numbers that I believe that isn't in the literatute. I am asking to know a rigorous and simple proof. Question. Prove that for each fixed even ...
1
vote
2answers
63 views

A different type of sum of divisors

Let $n\geq 1$ be a natural number. I would like to find the quantity: $$\sum\limits_{d_1 | n}\sum\limits_{\substack{d_2 | n \\ d_3|n \\ (d_2,d_3)=d_1}}d_3.$$ My guess is that the result could be $\...
2
votes
1answer
328 views

Prove that the product of all the positive divisors of two numbers is equal implies the numbers themselves are equal.

Let $P(n)$ and $P(m)$ be the product of all the positive divisors of $n$ and $m$, two positive integers. I know that $P(n) = n^{T(n)/2}$ and $P(m) = m^{T(m)/2}$, where $T(n)$ denotes the number of ...
5
votes
1answer
135 views

Find all $n \in \mathbb N$ such that $\sigma(n) + \phi(n) = n\tau(n)$

I am asked to find all naturals $n$ such that $\sigma(n) + \phi(n) = n\tau(n)$ where $\sigma, \phi, \tau$ are the sum of divisors, euler totient, and divisor counting functions respectively. ($\sigma$ ...
1
vote
1answer
174 views

number of coprime divisors of n with their difference divisible by 3

For an integer n, how many pairs (a, b) [suppose a is smaller than b] of coprime divisors of n exist such that (b-a) is divisible by 3 ? Advanced version of this question: Let F(n) denote the number ...
2
votes
0answers
69 views

A formula for the coefficients of the Ramanujan $\tau$ function

I want to show that $$\tau(n)=\frac{n}{12}(5\sigma_3(n)+7\sigma_5(n))-70\sum_{m=1}^{n-1}(5m-2n)\sigma_3(m)\sigma_5(n-m)$$ is true for all $n\in \mathbb{N}$. Previously I showed that $-147G_6^2+\frac{...
0
votes
0answers
17 views

An elementary approach using the divisor function definition: [duplicate]

Proof conclusion: Let m,n,s $\in$ $\mathbb{N} $\ $\{0\}$. Prove that $s| \tau(m^{s}) - \tau(n^{s})$, where $\tau$ is the divisor function. Hello so my question is that, I've gotten to the point in ...
0
votes
1answer
31 views

Working with elementary type proofs of divisor functions

Proof conclusion to: Let m,n $\in$ $\mathbb{N}$ $\backslash$ $\{0\}$ . Prove that $s |\tau (m^{s}) - \tau(n^{s})$, where $\tau$ is a divisor function. Hello, so I have a tiny question about the ...
1
vote
1answer
65 views

Show that the quotient $\frac{\sigma(p^3)}{\tau(p^3)}$ is an integer for $p$ prime

Let p $\geq$ 3 be a prime. Show that the quotient $\frac{\sigma(p^3)}{\tau(p^3)}$ is an integer. I know that I have to use the product formulas but not exactly sure how to go from there.
0
votes
1answer
33 views

Mods and Multiplicative functions

Where m is the largest odd factor of n, I am trying to prove that $$\sigma(n)\equiv d(m)\mod{2}$$ Any help is appreciated!
0
votes
1answer
139 views

Fastest way to count divisors of number that are not divisible by one prime number.

Let's define function $f(x,d)$ to be the number of divisors of $x$ that are not divisible by $d$ , and $d$ is prime number. What is the fastest way to count those divisors for given $x$ and $d$. For ...
3
votes
2answers
93 views

Solving $\tau(n)+\phi(n)=n$ for $n\in\mathbb{N})_{\ge 1}$.

Let $\tau(n)$ denote the number of divisors of a positive integer $n$, and let $\phi(n)$ be Euler's totient function, i.e. the number of positive integers less than and coprime to $n$. I'd like to ...