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
4 votes
1 answer
136 views

Determining the largest $\sigma_0((n+1)^2)$, given $2<n<2024$ [duplicate]

For which $n$ with $2<n<2024$ is $\sigma_0((n+1)^2)$ the largest? Here, as usual, $\sigma_0(m)$ denotes the number of positive divisors of $m$. I am struggling with this problem and any sort of ...
Arios's user avatar
  • 61
2 votes
1 answer
72 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
104 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
19 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
69 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
48 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
119 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
170 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
53 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,407
7 votes
0 answers
85 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,881
1 vote
0 answers
122 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
  • 1,740
6 votes
1 answer
263 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,331
0 votes
0 answers
68 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
100 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,640
5 votes
1 answer
208 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
  • 32k
4 votes
2 answers
721 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,483
0 votes
2 answers
41 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
87 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
65 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,342
0 votes
1 answer
281 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,342
0 votes
2 answers
265 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
68 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
78 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
65 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
101 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
54 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,531
0 votes
1 answer
64 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,576
-2 votes
2 answers
118 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
106 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
0 votes
2 answers
89 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
68 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
-1 votes
1 answer
230 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
  • 8,621
2 votes
1 answer
129 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
624 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
194 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
79 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
100 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
126 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
  • 6,686
2 votes
0 answers
116 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
34 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
75 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
51 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
130 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 vote
3 answers
92 views

Finite Factors of Refactorable Numbers

This was just a question that I came up with while learning about refactorable numbers. While looking through the sequence of refactorable numbers (1, 2, 8, 9, 12, 18....), I decided to look at the ...
Danyu Bosa's user avatar
1 vote
1 answer
56 views

When is the number of Divisors of a Number equivalent to one of its Factors?

My math teacher asked me this problem for homework and I am unsure how to solve it. Which numbers contain a number of factors equivalent to the value of one of their divisors? I found that 8 works, ...
Danyu Bosa's user avatar
1 vote
0 answers
43 views

Proof of $ \sum_{q \le x/d} 1 = \frac{x}{d} + O(1) $

Theorem 3.2 (d) of Introduction to Analytic Number Theory by Apostol states $$ \sum_{n \le x} n^a = \frac{x^{\alpha + 1}}{\alpha + 1} + O(x^\alpha) \text{ if } \alpha \ge 0.$$ Then later it uses ...
Lone Learner's user avatar
  • 1,076
6 votes
1 answer
125 views

Sum of recipocals of number of divisors

I wrote a math problem that went like this: Alice writes out all integers from 1 to $n$ on a blackboard. Each round, if there are still numbers on the board, Alice chooses a number on the board at ...
Ryan Yang-Liu's user avatar
0 votes
0 answers
60 views

What existing relationships are there in the divisor counting function for τ(m), τ(n) and τ(mn)?

I'm currently working through Fundamentals of Number Theory by LeVeque, and one of the problems asks whether I can find some relationship between $τ(m)$, $τ(n)$ and $τ(mn)$, where $τ$ is the number of ...
Eric's user avatar
  • 131

1
2 3 4 5 6