All Questions
Tagged with combinatorics number-theory
276
questions
19
votes
0
answers
533
views
Largest consecutive integer using basic operations and optimal digits?
If you are first time reading this, you may want to read the summary section last.
Solution summary and questions
Sequence values
If the allowed operations are $(+,-,\times,\div)$ and parentheses $(...
18
votes
3
answers
1k
views
Can the Basel problem be solved by Leibniz today?
It is well known that Leibniz derived the series
$$\begin{align}
\frac{\pi}{4}&=\sum_{i=0}^\infty \frac{(-1)^i}{2i+1},\tag{1}
\end{align}$$
but apparently he did not prove that
$$\begin{align}
\...
13
votes
1
answer
580
views
Strange shape of the distribution of the sum of the binomial coefficients ${n\choose r^2}$over squares
Update: Initially the question was posted for $a = 1$. Now it has been generalized for any real $a > 0$
What is known about the distribution of the sum of the binomial coefficients over multiple ...
12
votes
3
answers
19k
views
Calculating integer partitions
A partition of a positive integer $n$, also called an integer partition, is a way of writing $n$ as a sum of positive integers. The number of partitions of $n$ is given by the partition function $p(n)$...
12
votes
5
answers
2k
views
Calculating the median in the St. Petersburg paradox
I am studying a recreational probability problem (which from the comments here I discovered it has a name and long history). One way to address the paradox created by the problem is to study the ...
11
votes
5
answers
11k
views
Non-Decreasing Digits
A number is said to be made up of non-decreasing digits if all the digits to the left of any digit is less than or equal to that digit.
For example, the four-digit number $1234$ is composed of digits ...
11
votes
8
answers
6k
views
How many ways can $133$ be written as sum of only $1s$ and $2s$
Since last week I have been working on a way, how to sum $1$ and $2$ to have $133$.
So for instance we can have $133$ $1s$ or $61$ $s$2 and one and so on. Looking back to the example: if we sum: $1 + ...
11
votes
2
answers
420
views
Gardner riddle on mathemagicians
A cute riddle (but maybe not so easy!) from Gardner:
At a gathering of mathemagicians, the Grand Master and his 8 disciples are seated at a round table. The Grand Master will judge each of his ...
10
votes
0
answers
357
views
Dissecting the complexity of prime numbers
Each prime number greater than $9$, written in base $10$, ends with one of the four digits $1,3,7,9$. Therefore, each ten can be classified according to which of these four digits, summed to the ten, ...
10
votes
2
answers
1k
views
Accuracy of approximation to inclusion-exclusion formula in prime sieve
This thing came up in a combinatorics course I am taking.
Choose a fixed set of primes $p_1,p_2,\dots,p_k$ and let $A_n$ be number of integers in $\{1,2,\dots,n\}$ which are not divisible by any of ...
10
votes
1
answer
660
views
Sparse Ruler Conjecture
Sparse Ruler Conjecture, hard: If a minimal sparse ruler of length $n$ has $m$ marks,
easy: $m-\lceil \sqrt{3*n +9/4} \rfloor \in (0,1)$.
hard: $m+\frac{1}{2} \ge \sqrt{3 \times n +9/4} \ge m-1$...
10
votes
2
answers
7k
views
Why is Euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime in a clean intuitive way?
I had my own proof for it but I really don't like it (it feels not intuitive at all because it requires factoring!) and I feel there must be a more direct way to do it by a different counting argument....
9
votes
2
answers
743
views
Does Collatz Rule $3x+5$ have a bias for certain loops, or are my results faulty?
Not too long ago, I studied a modified Collatz rule where
$$f(x)=
\begin{cases}
3x+5, & \text{if $x$ is odd} \\
x/2, & \text{if $x$ is even}
\end{cases}$$
by observing the trajectories of $...
9
votes
1
answer
563
views
Binomial Congruence
How can we show that $\dbinom{pm}{pn}\equiv\dbinom{m}{n}\pmod {p^3}$ where $m$ and $n$ are nonnegative integers and $p$ is a prime such that $p \geq 5$ ? I can do it for $\mod p^2$ but I am stuck here....
9
votes
2
answers
472
views
Divisibility of an Evenly Spaced Binomial Coefficient Series
By this paper, it can be shown that for $n>0$ and $N\in\mathbb{N}$
$$\sum_{k=0}^n\binom{Nn}{Nk}=\frac{2^{Nn}}{N}\sum_{k=0}^{N-1}(-1)^{kn}\cos^{Nn}\left(\frac{k\pi}{N}\right)$$
Now, for a recursive ...