Stack Exchange Network

Stack Exchange network consists of 174 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$.

0
votes
2answers
18 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
24 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 $$...
4
votes
2answers
40 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
80 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
25 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
92 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
65 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
41 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
895 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
39 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
34 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
70 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
40 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
61 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
47 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
30 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
85 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 ...
3
votes
1answer
61 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
22 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
437 views

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

I stumbled upon the following conjecture: $$\tau(n)+\sigma(n)\equiv 1(2) \leftrightarrow n = 2m^2$$ Does anybody have an idea on how to prove this, maybe in parts? Or maybe someone has a ...
0
votes
3answers
310 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
40 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
59 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
65 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
39 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
58 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
97 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
20 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
61 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
267 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 ...
4
votes
1answer
115 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
155 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
65 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
30 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
60 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
29 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
96 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
81 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 ...
1
vote
1answer
104 views

Restricted divisor summatory function

It is known that the average number of divisors, calculated over all positive integers between $1$ and $N$, can be expressed using the classical Dirichlet formula as $$\frac{1}{N} \sum_{n=1}^N d(n)= \...
0
votes
0answers
38 views

Dirichlet serie of divisors function

I found on Wikipedia that $$D(s,\sigma_a \sigma_b) := \sum_{n \geqslant 1} \frac{\sigma_a(n)\sigma_b(n)}{n^s} = \frac{\zeta(s)\zeta(s-a)\zeta(s-b)\zeta(s-a-b)}{\zeta(2s-a-b)}$$ where as usual $\...
0
votes
0answers
33 views

On highly-composite values of polynomials

Can we characterize those non-constant polynomials $f(x) \in \mathbb Z[x]$ such that the set $\{|f(n)| : n \in \mathbb Z\}$ contains infinitely many "highly composite" (https://en.wikipedia.org/wiki/...
4
votes
1answer
139 views

Equation $x = \tau(2^x - 1)$

I want to find all integer solutions of the equation $x = \tau(2^x – 1)$, where $\tau(n)$ is the number of divisors of n. I know that 1, 2, 4, 6, 8, 16 and 32 are solutions, but I have no idea how to ...
2
votes
0answers
84 views

Exact formula of divisor problem

given the sum of divisors of a function $$ D(x)= \sum_{n=1}^{x}d (n) = x\log x + x(2\gamma-1) + \Delta(x)\ $$ then what is the EXACT formula of $ \Delta (x) $ not the O-notation but the EXACT power ...
4
votes
1answer
45 views

if the number $K$ has $45$ divisors, and the number $K^2$ has $M$ divisors, what is the sum of all possible values of $M$?

if the number $K$ has $45$ divisors, and the number $K^2$ has $M$ divisors, what is the sum of all possible values of $M$? My try follows. $45=15×3$ ; $45 = 45×1$ ; $45 = 9×5$ . Then $k$...
-2
votes
2answers
35 views

Fundamental principles of counting [closed]

Of all numbers between 10,000 and 99,999, inclusive how many. A- Do not contain the digit 5? B- Do contain the digit 5? C- Are odd and contain no digit more than once? D- Have no two consecutive ...
1
vote
1answer
345 views

The number of divisors of 2700 including 1 and 2700 equals

I don't really know how to approach this kind of problems, is there any trick or formula for this?
3
votes
0answers
81 views

Divisor Function Analytic Continuation

I'm trying to define the divisor function $d(k)$ over a larger domain than the integers but the result I produce appears to converge nowhere, including the integer points i originally expected it to ...
0
votes
1answer
51 views

counting number of square unit the line should travel

Imagine the first quadrant of the real plane as consisting of unit squares. A typical square has $4$ corners: $(i,j)$, $(i+1,j)$, $(i+1,j+ 1)$, and $(i,j+1)$, where $(i,j)$ is a pair of non-negative ...