Skip to main content

Questions tagged [divisor-counting-function]

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

Filter by
Sorted by
Tagged with
3 votes
0 answers
32 views

estimating an elementary sum involving divisor function

Please guide me as to how to obtain the below bound and whether it is optimal. Let a squarefree integer $N=\prod_{1 \leq i \leq m} p_i$ be a product of $m$ primes ($p_1 < p_2 < \dots < p_m$) ...
user166305's user avatar
4 votes
1 answer
173 views

Show that there are only finitely many pairs of positive integers $(n, m)$ such that $d(m!) = n!$.

Show that there are only finitely many pairs of positive integers $(n, m)$ such that $d(m!) = n!$, where $d(n)$ denotes the number of positive divisors of $n$. My approach (it isn’t complete and ...
math.enthusiast9's user avatar
-1 votes
1 answer
65 views

How many divisors does $66^{49$} have? [duplicate]

The question was What is the amount of natural divisors of $66^{49}$ I know that I most likely have to calculate the prime divisors of $66$ (so $2$, $3$ and $11$). However I do not know how to go ...
panda's user avatar
  • 15
0 votes
0 answers
76 views

Highly composite numbers which are the middle of a twin prime

From the first $10\ 000$ highly composite numbers listed in OEIS , the following $20$ are the middle of a twin-prime that is we have a highly composite number $N$ such that both $N-1$ and $N+1$ are ...
Peter's user avatar
  • 85.1k
2 votes
1 answer
62 views

On the "efficiency" of digit-sum divisibility tricks in other bases (or about the growth rate of the number of divisors function).

Out of the different divisibility tricks there's a really simple rule that works for more than one divisor: The digit-sum. Specifically, if the sum of the digits of a number is a multiple of $1,3$ or $...
Robert Lee's user avatar
  • 7,273
2 votes
1 answer
48 views

Solutions of equations of form $\tau(n+a_i)=\tau(x+a_i)$ where $\tau$ is the number of divisors function and $a_i$ is a diverging series

Consider the function $$\tau(n)=\sum_{d|n}1$$ which gives the number of divisors of a number. The question is: How much information does $\tau(n)$ contain about $n$? The answer is obviously: not very ...
xyz1234's user avatar
  • 103
2 votes
1 answer
75 views

A Diophantine equation centered around the divisor counting function and squares

For each positive integer $n$, let $τ(n)$ be the prime counting function. Prove that for all positive integers $a$ and $b$ satisfy the following equation that $a+b$ is even: $a + τ (a) = b^2 + 2$. So ...
A Neutrino Boy's user avatar
2 votes
1 answer
141 views

Prove that φ(n) + d(n) ≤ n + 1 [duplicate]

Prove that φ(n) + d(n) ≤ n + 1. d(n) is the number of positive divisors of n. φ(n) is the Euler's Totient Function. Attempt: For a prime number n, φ(n) = n - 1 (all numbers less than n are relatively ...
comp.course.master's user avatar
0 votes
0 answers
20 views

Solve $0=(u^2+v^2)^{\frac12}\left(u\sum_{n=1}^{\infty}\sigma_3(n)ny^n\cos(t-nz)+v\sum_{n=1}^{\infty}\sigma_3(n)ny^n\sin(t+nz)\right)$ for $t$

Let $t\in\left(\frac{\pi}3,\frac{2\pi}3\right)$. Let $y:=e^{-2\pi\sin t}$. Let $z:=2\pi\cos t$. Let $u:=1+240\sum_{n=1}^{\infty}\sigma_3(n)y^n\cos(nz)$. Let $v:=240\sum_{n=1}^{\infty}\sigma_3(n)y^n\...
Abraham Zhang's user avatar
3 votes
1 answer
84 views

Dirichlet series of $\ln(n) \tau(n)$

I was experimenting with a technique I developed for double/multiple summation problems, and thought of this problem: Find $$S(p)=\sum_{n=1}^{\infty} \frac{\ln(n) \tau(n)}{n^p}$$ where $\tau(n)=\sum_{...
user avatar
2 votes
0 answers
53 views

Numbers of divisors for a Mersenne number

Recently I encountered a problem: If n is a positive integer, then is the number of divisors of $2^n - 1$ less or greater than the number of divisors of n? I tried factoring and taking modulo n but ...
notabot's user avatar
  • 21
3 votes
0 answers
127 views

Proving that there are infinite primes with digit sum 8 in base 10

I recently wrote about a problem I cam up with while thinking about number theory, which you can find on this post. Long story short, I'm trying to prove there are infinite natural numbers such that ...
Francisco Sierra's user avatar
1 vote
2 answers
175 views

Call $n\in\Bbb N$ "balanced" if the sum of its digits equals the count of its divisors. How many "balanced" numbers are there up to $m$?

I recently stumbled across a problem about numbers' divisor count (more specifically, how many positive integers are equal to the square of their divisor count - answer was 2: they are 1 and 9). But I ...
Francisco Sierra's user avatar
0 votes
0 answers
55 views

Product of All Positive Divisors of a Number [duplicate]

Based on my current knowledge, the formula for finding the product of all positive divisors of a number $n$ is $= n^{\frac{\tau (n)}{2}}$ where the function $\tau (n)$ outputs the number of positive ...
Camelot823's user avatar
  • 1,467
7 votes
0 answers
100 views

Asymptotic on $\sum_{n<x} 1/d_{\alpha}(n)$, $d_\alpha$ is the general divisor function.

Let $d(n)$ be the divisor function, that is, $$d(n)=\sum_{1\leq k\leq n, \,k|n} 1.$$ Or equivalently, $d(n)$ can be defined as the coefficients of $\zeta^2(s)$: $$\zeta^2(s)=\sum_{n\geq1} d(n)n^{-s}.$$...
Landau's user avatar
  • 1,963
1 vote
0 answers
138 views

Number of Divisors of $m$ Such That They're All Less Than Some $n$

Recently I watched this Numberphile video. In it, they ask a rather interesting question. Q. There are $100$ lightbulbs placed in a horizontal row. These bulbs are labelled from $1$ to $100.$ ...
aqualubix's user avatar
  • 2,145
6 votes
1 answer
270 views

Optimal bounds for the product of the divisor function $d(n)$ in short intervals

Let $d(n)$ denote the number of divisors of a positive integer $n$. It is pretty obvious that $d(n) \ge 2$ for any given number $n \ge 2$, since every number is divisible by $1$ and itself. $2$ is ...
Kinheadpump's user avatar
  • 1,341
0 votes
0 answers
78 views

Goldbach's Conjecture: Counterexample of "necessary condition"

Definitions: Divisor Function: $$\sigma_x(n) = \sum_{d\mid n} d^x$$ Euler's Totient Function: $$\phi(n) = \# \{m \in \mathbb{Z}^+ \mid (\gcd(m,n)=1) \wedge (1 \le m \le n)\}$$ Conjecture: The ...
Joshua Ortiz's user avatar
1 vote
1 answer
101 views

The main term when counting $d(n)$ in arithmetic progressions

For $q,a\in \mathbb N$ write $d=(q,a)$. Why might be $$\sum _{h|q}\frac {c_h(a)\log (d/h)}{h}=-\frac {q'}{\phi (q')}\sum _{h|q}\frac {c_h(a)}{h}\sum _{h'|q'}\frac {\mu (h')\log h'}{h'}+\sum _{h|d}\...
tomos's user avatar
  • 1,662
5 votes
1 answer
228 views

Iterating over numbers with many divisors

I would like to iterate over the numbers with more than $D$ divisors in a large range $[x, x+N]$. Current values I'm working with are $D=626$ and $x\approx N\approx10^{11}.$ At the moment I'm using a ...
Charles's user avatar
  • 32.3k
4 votes
2 answers
776 views

How did Ramanujan came up with this?

The following is a picture of equation from Ramanujan's lost notebook. In this page, Ramanujan gives a closed form for, $$\sum_{n\geq 1}\sigma_{s}(n)x^{n}$$ In an attempt initially it's claimed that, ...
RAHUL 's user avatar
  • 1,521
0 votes
2 answers
43 views

Count non-decreasing sequences of a given length N made from multiples under a limit M

Given integers N and M, count how many sequences A of N integers satisfy the following conditions? $1 ≤ A_i​ ≤ M(i=1,2,…,N)$ $A_{i+1}$ is a multiple of $A_i$. $(i=1,2,…,N−1)$ For example for N=3 and M=...
ishandutta2007's user avatar
0 votes
1 answer
93 views

What is the Dirichlet Convolution of the identity function with itself?

If you have two identity functions, then $f(d) * g(n/d)$ would be just $dn/d = n$. Since we have an $n$ added for each divisor of $n$, would the resulting function just be $n$ times the number of ...
Isaac Wachsman's user avatar
1 vote
1 answer
71 views

Determining all arithmetic multiplicative functions that are idempotent to the convolution product

Exercise. Determine all the arithmetic multiplicative functions that are idempontent to the convolution product, i.e., determine all the functions $f$ such that, for every $a \in \Bbb N$, we have: $$ (...
xyz's user avatar
  • 1,141
0 votes
1 answer
339 views

Finding a formula for $\sum_{d|n} \tau(d)$, where $\tau(d)$ is the number of divisors of $d$.

I am currently in the middle of the following exercise: Exercise. Compute $$ \sum_{d|n} \left(\sigma(d)\mu\left(\frac{n}{d}\right)+\tau(d)\right),$$ where $\sigma$ is the function that corresponds to ...
xyz's user avatar
  • 1,141
0 votes
2 answers
320 views

How are phi and tau defined? [closed]

I'm working on a proof problem that uses $\phi(n)$ and $\tau(n),$ and I am wondering if $\phi(n)$ and $\tau(n)$ are the factors of $n$/relatively prime numbers smaller than $n$, or the number of ...
ᴇɴᴅᴇʀᴍᴀɴ's user avatar
1 vote
1 answer
70 views

Hand calculation of divisor summatory function

Maybe this question is stupid, but there was a problem in a math competition (not even in the highest stage) in my county which asked to Find $ \sum_{n\leq390} d(n)$, where $d(n)$ is the number of ...
Federico A's user avatar
0 votes
0 answers
80 views

Count the number of ordered triples of positive integers whose product is not greater than a given number?

Given N, count the number of ordered triplets(a,b,c) whose product $abc \leq N$. I have found the series here . But I am not sure I understand Benoit Cloitre work which proposed an efficent way to ...
ishandutta2007's user avatar
1 vote
0 answers
53 views

How can we show this relationship between the recursive sum of divisors function and Figurate Number Polynomial on Primes?

Let us define the following recursive function involving the sum of divisors function $\sigma(n)$: \begin{array}{ l } r(n,1)=\sigma(n) \\ r(n,2)=\sum_{d|n}r(d,1) \\ r(n,3)=\sum_{d|n}r(d,2) \\ \...
Eldar Sultanow's user avatar
1 vote
1 answer
66 views

Why does this identity with the product $\prod_{p\mid n}(p+k)$ and recursive sum of divisors function is true?

Let us define the following recursive function involving the sum of divisors function $\sigma(n)$: \begin{array}{ l } r(n,1)=\sigma(n) \\ r(n,2)=\sum_{d|n}r(d,1) \\ r(n,3)=\sum_{d|n}r(d,2) \\ \...
Eldar Sultanow's user avatar
5 votes
1 answer
110 views

How can we show this relationship between the sum of divisors function and the sum $p^{m}+2p^{m-1}+3p^{m-2}+\ldots+(m+1)$?

The sum of divisors function is commonly denoted by $\sigma(n)$. Now let us introduce a recursive definition of divisor functions: $r_{n,1}=\sigma(n)$ $r_{n,2}=\sum_{d|n}r_{d,1}$ $r_{n,3}=\sum_{d|n}...
Eldar Sultanow's user avatar
2 votes
1 answer
58 views

Stepwise irregularity of the divisor function, or does $\limsup_{n\to\infty} |d(n+1)-d(n)| = \infty$?

Defining $d(n):= \sum_{d|n} 1$, I know that $\liminf_{n\to\infty} d(n) = 2$, and Wigert showed that $\limsup_{n\to\infty} \frac{\log(d(n))}{ \log n/\log\log n} = \log 2$ (natural logarithm). This ...
D.R.'s user avatar
  • 8,935
0 votes
1 answer
72 views

Question involving series of divisor function and Euler function

We shall prove that $\sum_{n=1}^{+\infty} \frac{d(n)}{2^n}=\sum_{n=1}^{+\infty} \frac{1}{\phi(2^{n+1}-1)}$, where d(n) the divisor function. I was thinking of making use of the fact that d(n) is ...
MIkeTheSci's user avatar
1 vote
0 answers
39 views

Count the Number of Positive Integer Solutions to $\prod_{i=1}^{k}x_i\le N$

Given a fixed integer $k$ and a large positive integer $N$, I'd like to count the number of positive integer solutions to the equation $\prod_{i=1}^{k}x_i\le N$ in sublinear time. Note that when $k=2$,...
Hang Wu's user avatar
  • 1,586
-2 votes
2 answers
134 views

Count the number of integer solutions to $x_1+x_2+x_3+x_4+x_5+x_6=25$ when, $x_1,x_2,x_3$ are odd and $x_4,x_5,x_6$ are even and $x_i is N$

How to count the number of integer solutions to $$x_1+x_2+x_3+x_4+x_5+x_6=25$$ When, $x_1,x_2,x_3$ are odd ($2k+1$) and $x_4,x_5,x_6$ are even ($2k$), $x_i \in N$. Is there a general formula to ...
ask0question1's user avatar
1 vote
3 answers
122 views

If $n=2^{10}\times 3^5$. Find number of divisors of $n^2$ which are less than $n$ but do not divide $n$

If $N=2^{10}\times 3^5$. Find number of divisors of $n^2$ which are less than $n$ but do not divide $n$ My solution: $$n^2=2^{20}\times 3^{10}$$ Factors of $n^2=\left(20+1\right)(10+1)=21\times 11=...
SHIV's user avatar
  • 183
1 vote
2 answers
133 views

What does the notation $\sum_{d\mid (k,n)}$ mean?

I'm trying to understand how to generate this sequence, but I'm confused about this notation: $$\sum_{d\mid (k,n)}$$ Does it mean the sum of all factors of both $k$ and $n$?
keysmusician's user avatar
2 votes
0 answers
70 views

Can this divisor and floor function be calculated faster

Let $d(n)$ is the number of divisors of $n$. Example: $d(6) = 4$ because $6$ has $4$ divisors {$1, 2, 3, 6$} (Sequence A000005). Let $D(n)$ is the sum of first $n$ functions $d(x)$. Or we have $D(n) = ...
Vo Hoang Anh's user avatar
0 votes
1 answer
240 views

If we know about the divisors of $n$, what can we comment about the divisors of $n+x$?

I was dealing with a different problem when this question struck me- Let us have a natural number $n$, and we know that the divisors of $n$ are $d_1,d_2,\dots d_k$. Now, we add any other $x\in \...
Sayan Dutta's user avatar
  • 9,592
2 votes
1 answer
136 views

Can $\sum_{k=1}^n \arctan(\cot(\frac{\pi n}{k}))$ be simplified?

I found this relation about the floor function on some forum: $$⌊x⌋ = x -\frac{1}{2}+\frac{\arctan(\cot(\pi x))}{\pi}$$ I found it intriguing as this could be used in relating several non - continuous ...
2pie's user avatar
  • 23
1 vote
3 answers
728 views

What is the formula to calculate the number of divisors of $n!$

I felt like trying to find the number of divisors of $n!$. I have found that taking the number of subsets of the first $n$ natural numbers ($n! = \sum\limits_{i = 1}^ni:i \in \mathbb{N}$), one can say ...
Spectre's user avatar
  • 1,573
6 votes
1 answer
197 views

The function $ g(n)=\sum_{\substack {1\lt k\leq n \\ \gcd(k,n)=1}}d(k-1)$

In 1965 Puliyakot Keshava Menon proved that $${\displaystyle \sum _{\substack {1\leq k\leq n \\ \gcd(k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n)}$$ being $\varphi(n)$ the totient function of $n$. If we move ...
Augusto Santi's user avatar
2 votes
2 answers
83 views

Some questions about the arithmetic function $\,g(n)=\sum_{(k,n)=1}\tau(k)$

Given the arithmetic function $\tau(n)=\sum_{d|n}1$, let's define the function $$g(n)=\sum_{1\le k\le n\;(k,n)=1}\tau(k)$$ For $n\ge1$ the first values of $g(n)$ are $1,1,3,3,8,3,14,7,14,8,...$ ...
Augusto Santi's user avatar
1 vote
0 answers
101 views

Approximation for the number of unordered $k$-factorizations of positive integer $n$

I am trying to find an approximation formula for the number of multiplicative partitions of $n$ with $k$ parts. I found that an approximation formula for the number of multiplicative partitions with ...
dumpram's user avatar
  • 61
3 votes
0 answers
128 views

What is $\sum_{n=2}^{\infty} \frac{d(n)}{n(n-1)} $?

While trying to evaluate a multiple rational zeta series, the following sum came up: $$\sum_{n=2}^{\infty} \frac{d(n)}{n(n-1)} = \sum_{n=2}^{\infty} \Big{(} \frac{d(n)}{n-1} - \frac{d(n)}{n} \Big{)}. \...
Max Muller's user avatar
  • 7,118
2 votes
0 answers
123 views

Average Number of Small Divisors

I'm working on a pet project of mine and I've come across a seemingly simple problem that I can neither solve nor find any reference to in the literature. The problem is this: Given $x$ sufficiently ...
Joshua Stucky's user avatar
1 vote
0 answers
35 views

Given $n\in\mathbb N$ what are the maximum number of divisors of a natural number not more than $n$? [duplicate]

So the question is in the title itself. The minimum number of divisors are $2$ (for primes), but the maximum number of divisors are what we are interested in. It cannot be more than the number itself ...
Martund's user avatar
  • 14.7k
1 vote
1 answer
87 views

Square of number of divisors of n equals n

Find $n \in \mathbb{N}$ such that $n = \tau(n)^2$ ($\tau(n)$ being the number of positive divisors of $n$). I tried some values for $n$, it seems that besides $n = 1$ and $n = 9$ there's no other ...
Iridium's user avatar
  • 99
1 vote
1 answer
52 views

Trying to figure out the asymptotic density

Let $a>0$. I have the following function $f: \mathbb{N} \to \mathbb{R} $ defined in the following way: \begin{equation}\label{km relation} f(m) = m +\lfloor a m - \tfrac{a }{2} +\tfrac12 \rfloor....
Sean Thrasher's user avatar
3 votes
1 answer
131 views

About Euler totient function $\underbrace{\varphi( \varphi( \dots \varphi(}_{k\ \text{times}} n) \dots ))$

Let $\varphi^k(n)=\underbrace{\varphi( \varphi( \dots \varphi(}_{k\ \text{times}} n) \dots ))$. Define $f:\mathbb{N}/ \{1\}\rightarrow \mathbb{N}$ so that $f(n)$ is the number of iterations of the ...
Zootopia's user avatar
  • 743

1
2 3 4 5 6