All Questions
Tagged with elementary-number-theory summation
482
questions
2
votes
1
answer
56
views
Proof of $\frac{\Phi_n'(x)}{\Phi_n(x)} = \frac{1}{x^n-1}\sum_{k=1}^{n}c_k(n)x^{k-1}$
Let $c_k(n)$ denote Ramanujan's sum, and $\Phi_n(x)$ be the $n$th cyclotomic polynomial. Prove that
$$\frac{\Phi_n'(x)}{\Phi_n(x)} = \frac{1}{x^n-1}\sum_{k=1}^{n}c_k(n)x^{k-1}$$
My attempt was to ...
- 702
0
votes
0
answers
42
views
How to show that $\sum_{j = 1}^{A \left({n}\right)} \left\{{\frac{n - {j}^{2}}{2\, j}}\right\}$ satisfies Weyl's criterion.
We can write this sum in terms of even ($j = 2k$) and odd ($j = 2k-1$) summation index as
$$\sum_{j = 1}^{A \left({n}\right)} \left\{{\frac{n - {j}^{2}}{2\, j}}\right\} = \sum_{k = 1}^{\lfloor{A \left(...
- 967
0
votes
0
answers
81
views
Looking for a solution of $\sum_{i = 1}^{k} \sum_{{d}_{1}\, {d}_{2} = i (2k - i), {d}_{1} \le N, {d}_{2} \le N} [GCD(2 k, {d}_{1}, {d}_{2}) = 1]$
The double sum is
$$\sum_{i = 1}^{k} \sum_{\substack{{d}_{1}\, {d}_{2} = i \left({2k - i}\right), \\ {d}_{1} \le N, {d}_{2} \le N}} \left[{\left({2\, k, {d}_{1}, {d}_{2}}\right) = 1}\right]$$
where [.....
- 967
0
votes
1
answer
58
views
How to define a function that satifies this condition?
I would like to define a function $f(n)$.
It must be such that it should produce the sum of all elements till the nth term of the series mentioned below:
$$2,2,2,3,3,3,4,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,...
- 73
3
votes
0
answers
79
views
The number $1^1 + 3^3 + 5^5 + .. + (2^n - 1)^{2^n-1}$ is a multiple of $2^n$ but not a multiple of $2^{n+1}$
Prove that for all $n>1$ the number $1^1 + 3^3 + 5^5 + .. + (2^n - 1)^{2^n-1}$ is a multiple of $2^n$ but not a multiple of $2^{n+1}$.
Proof: Let $$S_n=1^1 + 3^3 + 5^5 + .. + (2^n - 1)^{2^n-1}$$
We ...
- 101
0
votes
1
answer
66
views
Asymptotic for $\sum_{d\mid N}\frac{d^{2}}{\sigma\left(d\right)}$ [closed]
Let $N\in\mathbb{N}$. I'm looking for an asymptotic formula for $\sum_{d\mid N}\frac{d^{2}}{\sigma\left(d\right)}$ as $N\rightarrow\infty$. I tried to use known asymptotic formulas for similar ...
- 49
3
votes
0
answers
59
views
Is it possible to construct a sequence using the first $n$ prime numbers such that each segment has a unique sum?
For example, consider the sequence $2,7,3,5$. The sums of the segments of this sequence are as follows, and they are all unique:
$$2, 2+7, 2+7+3, 2+7+3+5, 7, 7+3, 7+3+5, 3, 3+5, 5$$
Can we generate ...
- 1,451
3
votes
0
answers
75
views
Can we show that $\frac{\sum_{j=1}^n j^2\cdot j!}{99}$ generates only finite many primes?
Define $$f(n):=\frac{\sum_{j=1}^n j^2\cdot j!}{99}$$
Is $f(n)$ prime for only finite many positive integers $n\ge 10$ ?
Approach : If we find a prime number $q>11$ with $q\mid f(q-1)$ , then for ...
- 85.1k
0
votes
2
answers
62
views
Comparing integral with a sum
Show that \begin{equation}\sum_{m=1}^k\frac{1}{m}>\log k.\end{equation}
My intuition here is that the LHS looks a lot like $\int_1^k\frac{1}{x}\textrm{d}x$, and this evaluates to $\log k$. To ...
- 135
0
votes
1
answer
39
views
Differences between sums of reciprocals of primes and products thereof.
I am not a number theorist, but I know that number theorists are notorious for estimating sums including primes. So, I have the following question, which I may not have seen addressed, but I am sure ...
- 717
2
votes
3
answers
199
views
Sum of floored fractions $\lfloor \frac{1^3}{2009} \rfloor + \lfloor \frac{2^3}{2009} \rfloor + \cdots + \lfloor \frac{2008^3}{2009} \rfloor$
I want to compute the remainder of $A$ divided by 1000, where $A$ is
$$A = \lfloor \frac{1^3}{2009} \rfloor + \lfloor \frac{2^3}{2009} \rfloor + \cdots + \lfloor \frac{2008^3}{2009} \rfloor.$$
I tried ...
- 918
-2
votes
1
answer
61
views
Summation of $\frac{\sum_{n=1}^{\infty}\frac{T\left(n\right)}{n^{3}}}{\sum_{n=1}^{\infty}\frac{\phi\left(n\right)}{n^{3}}}$ [closed]
Define $T(x)$ as $T(x) = \operatorname{gcd}(1,x)+\operatorname{gcd}(2,x)+ \dots+\operatorname{gcd}(x,x)$. How do I find the value of
$$\frac{\sum_{n=1}^{\infty}\frac{T\left(n\right)}{n^{3}}}{\sum_{n=1}...
2
votes
1
answer
79
views
$m_i, n_j$ integers and $\{m_i\}_{i=1}^{k}\neq\{n_j\}_{j=1}^{k'}.$ Does $\sum\frac{1}{m_i}=\sum\frac{1}{n_j}\implies\sum m_i\neq\sum n_j?$
Suppose $\{m_i\}_{i=1}^{k}$ and $\{n_j\}_{j=1}^{k'}$ are each finite subsets of $\mathbb{N},$ $\{m_i\}_{i=1}^{k}\neq\{n_j\}_{j=1}^{k'},$ and $\displaystyle\sum_{i=1}^{i=k}\frac{1}{m_i} = \sum_{j=1}^{...
- 20.7k
1
vote
1
answer
69
views
Summation notation over divisors confusion
What does the following summation notation represent?
$\sum\limits_{d_1 \mid a, \; d_2\mid b}f(d_1d_2)=\sum\limits_{d_1\mid a }\sum\limits_{d_2 \mid b}f(d_1)f(d_1)=\sum\limits_{d_1\mid a}f(d_1)\sum\...
- 637
5
votes
2
answers
262
views
Determine all positive integers $n$ such that: $n+d(n)+d(d(n))+\dotsb=2023$.
For a positive integer number $n>1$, we say that $d(n)$ is its superdivisor if $d(n)$ is the largest divisor of $n$ such that $d(n)<n$. Additionally, we define $d(0)=d(1)=0$. Determine all ...
- 418
13
votes
0
answers
189
views
Can the sequence $\{\lfloor \alpha n \rfloor\}$ be divided into two parts with equal sums, for all $\alpha \in \mathbb{R}$?
Define the sequence $a_n = \lfloor \alpha n \rfloor$ for a real number $\alpha$.
Is there any pair of natural numbers $k, l$ satisfying the following condition?:
$$\sum_{n=1}^k a_n = \sum_{n=k+1}^l ...
- 1,451
2
votes
3
answers
177
views
Is $1 \times 1 + 2 \times 2 + 3 \times 4 + 4 \times 8 = 49$ a coincidence? (Is $\sum_{i=0}^k(i+1)2^i$ ever a square again?)
When watching a gaming video, I noticed an intriguing fact:
$$
1 \times 1 + 2 \times 2 + 3 \times 4 + 4 \times 8 = 49,
$$
which is a square number.
I asked myself, is this a coincidence or not? ...
- 4,051
3
votes
0
answers
185
views
Digit Sum for Base 2 Alternate Definition
I was looking at the digit sum definition, but I also saw a simpler version that can be used for binary numbers. I'm trying to figure out and understand how the generic formula for any base can be ...
- 131
2
votes
1
answer
92
views
Prove that $0.1111$ is not a sum of 1111 funny numbers and that every $x\in (0,1)$ is the sum of 1112 different funny numbers.
An irrational number in $(0,1)$ is funny if its first four decimal digits are the same. For example, $0.1111 + e/10^5$ is funny. Prove that $0.1111$ is not a sum of 1111 funny numbers and that every $...
- 1,225
1
vote
0
answers
120
views
is a closed form solution possible?
I have a facination with prime numbers and unsolved problems, and i ended up creating a formula that returns the index of any prime number. The main problem is I don't know if the summations if its ...
- 23
2
votes
1
answer
132
views
Is there a name for this constant and its value where $\alpha = \sum_{p}\frac{\log \left({p}\right)}{p \left({p-1}\right)}$
The constant $$\alpha = \sum_{p} \frac{\log \left({p}\right)}{p \left({p-1}\right)}$$ comes from the calculation $$\sum_{p=2}^{x} \frac{\log \left({p}\right)}{p-1} = \sum_{p=2}^{x} \frac{\log \left({p}...
- 967
5
votes
0
answers
73
views
Is $1105$ the only Poulet-number of the form $2^a+3^b$?
Conjecture : $1105$ is the only Poulet-number that can be written in the form $2^a+3^b$ with positive integers $a,b$
A Poulet-number is a composite number $N$ satisfying the congruence $2^{N-1}\equiv ...
- 85.1k
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_{...
user1214193
2
votes
1
answer
66
views
Evaluate the sum or asymptotic expansion of $\sum_{p\ge 3} \frac{\log \left({p}\right)}{{p}^{2} - 1}$
In my research I cam across this sum
$$S = \sum_{p\ge 3} \frac{\log \left({p}\right)}{{p}^{2} - 1}$$
where $p$ is a prime number. Numerical evaluation of the first $10^8$ primes yields $S = 0....
- 967
2
votes
0
answers
49
views
Weird computation on the (variant) divisor problem
I have a weird computations here about the (variation of the) divisor problems that involves the squarefull numbers. It is the problem to determine
$\displaystyle \sum_{a^2b^3\le x} 1,$ which is ...
- 1,033
5
votes
1
answer
125
views
Is this valid? $\sum_{n=1}^{x} \frac{\Lambda \left({n}\right)}{n} \sim \log \left({x}\right) - \gamma + O \left({\frac{1}{x}}\right)$
From Theorem 4.9 of Apostol Introduction to Analytic Theory, p 88
$$\tilde{\psi} \left({x}\right) =
\tilde{\psi}_{1} \left({x}\right) = \sum_{n=1}^{x} \frac{\Lambda \left({n}\right)}{n} \sim \log \...
- 967
2
votes
1
answer
108
views
The sum of the reciprocals of the Carmichael-numbers.
Let $C_n$ be the $n$-th Carmichael-number and $$r:=\sum_{j=1}^{\infty} \frac{1}{C_j}$$
If we stop at the last Carmichael-number below $10^{16}$ ,we get $$0.0047065376661376\cdots $$ as an ...
- 85.1k
1
vote
0
answers
64
views
Evaluation of sum and asymptotic expansion of $\sum_{k=1}^{\lfloor{m/2}\rfloor} \left\{{\sqrt{k^2+n}}\right\}$
Find the sum if possible and the asymptotic expansion to high order of $$W \left({m, n}\right) = \sum_{k=1}^{\lfloor{m/2}\rfloor} \left\{{\sqrt{k^2+n}}\right\}$$
where $\left\{{...}\right\}$ is the ...
- 967
0
votes
1
answer
105
views
Evaluation sum and its asymptote $\sum_{s=1}^{N} \sum_{t=1}^{N} \left[{\sqrt{4t-s^2} \in \mathbb{Z}}\right]$
I am working on the evaluation of $$S \left({N}\right) = \sum_{s=1}^{N} \sum_{t=1}^{N} \left[{\sqrt{4t-s^2} \in \mathbb{Z}}\right]$$ and its asymptotic expansion where $N \ge 1$. Here $\sqrt{4t-s^2} \...
- 967
2
votes
0
answers
94
views
Need help with this sum involving linear congruences
A few months ago while dealing with squarefree integers in arithmetic progressions, this problem arose about finding bounded solutions to linear congruences.
The problem:
I have constants $a$ and $q$ ...
- 1,009
4
votes
1
answer
368
views
How many numbers less than N have a prime sum of digits?
I'm working on solving Project Euler's Problem 845. It's asking us to find the $10^{16}$-th positive integer number that has a prime sum of digits. Adopting a 'naive' solution, I compute the sum of ...
2
votes
2
answers
141
views
How to choose which stronger claim to prove when proving $\sum_{i=1}^n \frac{1}{i^2} \le 2$?
I am studying an inductive proof of the inequality $\sum_{i=1}^n \frac{1}{i^2} \le 2$. In the proof, it was decided to prove the stronger claim $\sum_{i=1}^n \frac{1}{i^2} \le 2-\frac{1}{n}$, as this ...
- 3,019
4
votes
1
answer
106
views
Simplifying floor function summation $\sum^m_{k=0} \left(\left\lfloor{\frac{n}{m}k}\right\rfloor-\left\lceil{\frac{n}{m}(k-1)}\right\rceil\right)$
Is there a way this summation can be simplified/cast in a more revelatory form (non-summation representation, single-term only, etc.)?
$$\sum^m_{k=0} \left(\left\lfloor{\frac{n}{m}k}\right\rfloor-\...
- 315
26
votes
1
answer
908
views
Mysterious sum equal to $\frac{7(p^2-1)}{24}$ where $p \equiv 1 \pmod{4}$
Consider a prime number $p \equiv 1 \pmod{4}$ and $n_p$ denotes the remainder of $n$ upon division by $p$. Let $A_p=\{ a \in [[0,p]] \mid {(a+1)^2}_p<{a^2}_p\}$.
I Conjecture
$$\sum_{a \in A_p } a=\...
- 3,792
2
votes
2
answers
354
views
At most one representation as a sum of two fibonacci-numbers?
I wanted to start a project to find primes of the form $F_m+F_n$ with integers $m,n$ satisfying $1<m<n$ , where $F_n$ denotes the $n$ th fibonacci-number.
I wondered whether duplicate numbers ...
- 85.1k
5
votes
2
answers
284
views
The most elementary proof of divisibility of sum of powers
I am wondering how one can prove that for an arbitrary odd natural number $n$ and an arbitrary natural number $a$ the power-sum $S_{(a,n)}=1^n+2^n+\ldots +a^n $ is divisible by $S_{(a,1)}=1+2+\ldots + ...
- 1,066
0
votes
2
answers
85
views
Construct a prime using $[2, 2, 2, ...., 3]$
Is there a generalized method to constructing primes through sums using the set $[2, 2, 2, ..., 3]$ given its elements are $n$- many 2s and a 3. This question obviously requires knowledge on ...
user1107557
1
vote
0
answers
65
views
Prove that $\lim\limits_{n\to\infty} a_n=\infty$.
Let $a_n$ denote the exponent of $2$ in the numerator of $\sum_{i=1}^n \dfrac{2^i}{i}$ when written in the lowest form. For example, $a_1=1,a_2=2,a_3=2.$ Prove that $\lim\limits_{n\to\infty} a_n=\...
- 1,837
2
votes
0
answers
71
views
When is $\sum_{1 \leq n \leq k}n^{-n+k}$ prime?
Consider the following finite sum $f: \mathbb{N} \rightarrow \mathbb{N}$ defined as
$$f(k) = \sum_{1 \leq n \leq k}n^{-n+k}$$
$$ = 2 + 2^{k-2} + 3^{k-3}...+ (k-1)$$
It is easy to see that $f(2) = 2$ ...
user1107557
2
votes
1
answer
127
views
Show that the product of the $2^{2019}$ numbers of the form $\pm 1\pm \sqrt{2}\pm\cdots \pm \sqrt{2019}$ is the square of an integer.
Show that the product of the $2^{2019}$ numbers of the form $\pm 1\pm \sqrt{2}\pm\cdots \pm \sqrt{2019}$ is the square of an integer.
I'm aware very similar problems were asked before (e.g. here and ...
- 2,031
1
vote
1
answer
314
views
Number theory approach to Project Euler's "Large Sum" problem?
I am refreshing some of my skills by solving problems on the Project Euler site. It is a repository of problems that usually require some mathematics knowledge and programming knowledge to solve ...
- 1,876
1
vote
0
answers
85
views
Probability that two integers are coprime
Maybe it is a silly question, but anyway. We know that the probability that two positive integers are coprime is $6/\pi^2$. However, for fixed positive integers $r$ and $s$, I'd want to compute the ...
- 73
6
votes
0
answers
57
views
For which integers $a\gt 0, b\ge 0$ is $\sum_{k=1}^n \frac1{ak+b}$ never an integer for $n > 1$?
For which integers $a\gt 0, b\ge 0$ is
$\sum_{k=1}^n \frac1{ak+b}$
never an integer for $n > 1$?
This is inspired
by a number of cases where this is true
($(a, b)
=(1, 0),
(3, 1)
$).
It might be ...
- 108k
6
votes
1
answer
228
views
An alternating sum
I ran into an alternating sum in my research and would like to know if the following identity is true:
$$
\sum_{i = 0}^{\left\lfloor \left(n + 1\right)/2\right\rfloor} \frac{\left(n + 1 - 2i\right)^{n ...
- 147
1
vote
1
answer
129
views
Proving $\sum_{1}^{n} \left\lceil\log_{2}\frac{2n}{2i-1}\right\rceil=2n -1 $
Show that $$\sum_{i=1}^{n} \left\lceil\log_{2}\frac{2n}{2i-1}\right\rceil=2n -1 $$ where $ \lceil\cdot\rceil$ denotes the ceiling function.
My method: one way would be observe each part of the ...
- 977
1
vote
1
answer
62
views
Max value of $p \ge 0$, $p \in \mathbb{Z}$ which makes $\frac{a_n}{3^p} \in \mathbb{N}$, when $\{a_n\}$ is an arithmetic sequence?
For $d \in \mathbb{N}$, $\{a_n\}$ is a arithmetic progression with $a_1 = 9$, and its common difference $d$.
$b_n$ is a max value of $p$ $(p \ge 0$, $p \in \mathbb{Z})$ which makes $\frac{a_n}{3^p} \...
- 343
1
vote
0
answers
59
views
Changing index of a double summation [duplicate]
How does one prove the following result, where $x$ is a three-parameter function defined on $\mathbb Z^3$? $$ \sum_{\ell=1}^{P}\sum^{\ell-1}_{i=0} x(\ell,i,\ell-i) \quad = \quad \sum^{P}_{j=1}\sum^{P-...
- 1,139
0
votes
1
answer
194
views
A sum related to the Mobius function
It is well-known that
$$\frac{\phi(n)}{n}=\sum_{d\mid n}\frac{\mu (d)}{d} \quad n\in \mathbb Z^+$$
Where $\phi $ is Euler's totient function and $\mu$ is the Mobius function. But using the formula for ...
- 4,196
1
vote
1
answer
73
views
Prove or disprove that $\sum_{k=1}^p G(\lambda^k) = ps(p)$
Prove or disprove the following: if $\lambda$ is a pth root of unity not equal to one, $G(x) = (1+x)(1+x^2)\cdots (1+x^p),$ and $s(p)$ is the sum of the coefficients of $x^n$ for $n$ divisible by $p$ ...
- 1,225
4
votes
4
answers
271
views
On swapping the order of a summation
Consider the following sum $$S=\sum_{k=1}^nd(k)$$
where $d(k)$ is the number of divisors of $k$. We can rewrite the sum like this $$S=\sum_{k=1}^n\sum_{d\mid k}^k1$$
but now how can I change the order ...
- 4,196