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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [divisor-counting-function]

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

11
votes
5answers
821 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
38 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
32 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
68 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
36 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
38 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
35 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
23 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
75 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
57 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
16 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
424 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
122 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
33 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 ...
0
votes
1answer
49 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
44 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
37 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}^{...
2
votes
2answers
52 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} \...
6
votes
1answer
95 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
19 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
36 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
56 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
199 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
86 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
135 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
56 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
27 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 ...
0
votes
0answers
32 views

Divisor Function Tau [duplicate]

Let $n,s,t$ $\in \mathbb{N} \setminus \{0\} $ . Prove that $s-t \mid \tau(n^s)-\tau(n^t).$ Let $m,n,s$ $\in \mathbb{N}\setminus \{0\}$. Prove that $ s \mid \tau(m^s)- \tau(n^s).$ For 1. Since $\tau$ ...
1
vote
1answer
54 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
23 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
59 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
69 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
85 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
36 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
131 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
74 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
44 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
33 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
281 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
75 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
49 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 ...
-1
votes
1answer
32 views

pigeonhole principle [closed]

Doctor dodge needs to see 65 patients next week; she works Monday through Saturday. A- give a lower bound to the number of patients she will see on the busiest day next week. B- give an upper ...
6
votes
3answers
491 views

Can you give me a big number with many divisors?

Let $\tau(n)$ denote the number of divisors of $n$ and $p$ prime. Today in high school I've tried to find a number that is not very big, but has a huge number of divisors (compared to it's size), i.e....
0
votes
1answer
29 views

Determine the number of strings of length five consisting of five distinct capital letters (A-Z)

A- that do not contain an A. B- that contain an A. C- that contain an A, a B, a C as their first three symbols, in that order. D- that contain an A, a B, and a C as their first three symbols, in ...
0
votes
1answer
264 views

How many ways are there to put five identical red balls and eight identical blue balls into 20 distinct boxes.

How many ways are there to put five identical red balls and eight identical blue balls into 20 distinct boxes? A- if at most one ball can be put into each box. B- if at most one ball of each color ...
0
votes
1answer
56 views

Fundamental principles of counting

Let $| X | = 7$ and $| Y | = 10$. A- How many different one to one functions are there from $X$ to $Y$? B- How many different functions are not one to one from $X$ to $Y$? C- How many different ...
0
votes
1answer
45 views

explicit exact formula for divisor functions and sums

from basic number theory we know $$ \sum_{n\le x}\sigma _{0}(n)= \sum_{n=1}^{\infty}[x/n] $$ where $ [x] $ is the floor function then for the divison function of any order can we evaluate exactly ...
3
votes
2answers
105 views

Why so many numbers with 12 divisors?

For some purposes I have been checking whether or not there were many numbers around 600000 with exactly 12 divisors. I have been struck by the fact that more than 10% of the numbers near 600000 (by ...