All Questions
Tagged with integer-partitions elementary-number-theory
76
questions
20
votes
1
answer
4k
views
Partition of ${1, 2, ... , n}$ into subsets with equal sums.
The following is one of the old contest problems (22nd All Soviet Union Math Contest, 1988).
Let $m, n, k$ be positive integers such that $m \ge n$ and $1 + 2 + ... + n = mk$. Prove that the numbers $...
19
votes
1
answer
1k
views
Can we partition the reciprocals of $\mathbb{N}$ so that each sum equals 1
Let $S = \{1, 1/2,1/3,\dots\}$
Can we find a partition $P$ of $S$ so that each part sums to 1, e.g.
$$P_1 = {1}$$
$$P_2 = { 1/2,1/5,1/7,1/10,1/14,1/70}$$
$$P_3 = {1/3,1/4,1/6,1/9,1/12,1/18}$$
$$P_4 = \...
18
votes
6
answers
9k
views
Prime Partition
A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
17
votes
0
answers
255
views
For what $n$ can $\{1, 2,\ldots, n\}$ be partitioned into equal-sized sets $A$, $B$ such that $\sum_{k\in A}k^p=\sum_{k\in B}k^p$ for $p=1, 2, 3$?
This is a recent problem in American Mathematical Monthly. The deadline for this question just passed:
$\textbf{Problem:}$ For which positive integers $n$ can $\{1,2,3,...,n\}$ be partitioned into ...
10
votes
3
answers
3k
views
Number of partitions of $50$
Does someone know the number of partitions of the integer $50$? I mean, in how many ways can I write $50$ as a sum of positive integers?
I know that there's a table by Euler, which is useful to know ...
9
votes
2
answers
264
views
P-graph of partition elements of 100 under common divisibility relation
Given a multiset of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if they have a common divisor greater than ...
7
votes
1
answer
233
views
What is the significance of this identity relating to partitions?
I was watching a talk given by Prof. Richard Kenyon of Brown University, and I was confused by an equation briefly displayed at the bottom of one slide at 15:05 in the video.
$$1 + x + x^3 + x^6 + \...
7
votes
2
answers
312
views
For every partition $\pi$ of a fixed integer $n$, $\sum{F(\pi)}=\sum{G(\pi)}$
I need to prove the following question.
For every partition $\pi$ of a fixed integer $n$, define $F(\pi)$=number of occurrences of 1 as a summand, and $G(\pi)$=no. of distinct summands in the ...
7
votes
1
answer
406
views
Representations of an integer as the sum of other integers
Given a finite set $S$ of (distinct) integers $s_1, \dots, s_n$ and an integer $x$, I'm looking for all representations (where order is important)
$$
x=\sum_{i=1}^ks_{t_i} (t_i\in\{1,\dots,n\})
$$
...
6
votes
2
answers
4k
views
Find all ways to factor a number
An example of what I'm looking for will probably explain the question best. 24 can be written as:
12 · 2
6 · 2 · 2
3 · 2 · 2 · 2
8 · 3
4 · 2 · 3
6 · 4
I'm familiar with finding all the prime factors ...
6
votes
2
answers
2k
views
Lower bounds for the partition function
In this question we consider the partition function $p(n)$ - that is, the number of ways to express $n$ as a sum of positive integers.
One easy exercise is to show that $$ p(n) \geq 2^{\lfloor \sqrt{...
6
votes
2
answers
241
views
$p\equiv 1\pmod 4\Rightarrow p=a^2+b^2$ and $p\equiv 1\pmod 8\Rightarrow p=a^2+2b^2$, what about for $p\equiv 1\pmod {2^n}$ in general
Primes $p$ with $p\equiv 1\pmod 4$ can be written as $p=a^2+b^2$ for some integers $a,b$. For $p\equiv 1\pmod 8$ we have $p=a^2+2b^2$. Can primes that satisfy $p\equiv 1\pmod{2^n}$ for $n>3$ be ...
6
votes
2
answers
212
views
Partitions of n that generate all numbers smaller than n
Consider a partition $$n=n_1+n_2+\cdots+n_k$$ such that each number $1,\cdots, n$ can be obtained
by adding some of the numbers $n_1,n_2,\cdots,n_k$.
For example, $$9=4+3+1+1,$$
and every number ...
6
votes
1
answer
84
views
Partition of a number $n$ whose each part is coprime with this number
I'm trying to solve the following problem: given an integer $n$, under which conditions of $n$ the following statement is true:
For any $1 < k \leq n$, there is always a partition of $k$ parts of $...
5
votes
1
answer
108
views
A conjecture on partitions
While trying to prove a result in group theory I came up with the following conjecture on partitions:
Let $b(i,j)$ be the number of partitions of $i$ with greatest part exactly equal to $j$ , for ...