Arithmetic combinatorics is the study of combinatorial estimates associated with arithmetic operations. It lies in the intersection of harmonic analysis, combinatorics, ergodic theory, and number theory. This tag is for questions related to arithmetic combinatorics.

learn more… | top users | synonyms

-2
votes
1answer
46 views

product free, property P [on hold]

In jurnal mocow jurnal combinatorik and number theory "multiplicative property of set residue say in paragraph one, say for every positive integer, every set of residues mod of cardinality larger than ...
1
vote
1answer
17 views

Least moving-overlapped subset of [1..n] that has the biggest natural density as possible.

Given a natural number n>1. I'd like to find a set $\phi = \{s_1,s_2, \cdots , s_m \} \subset \{1,2,\cdots , n \} $ with $m > 1$ that minimizes the following quantity: $$ S_{\phi} = ...
0
votes
1answer
34 views

Link between two products

Could someone help me to solve this problem : Let's denote by $A_i$ the following product, $$ A_i = \prod_{\substack{k=1 \\ k\neq i}}^n (a_k - a_i) $$ Is there any link or simple formula between ...
6
votes
1answer
88 views

A question on Derangement Combinatorics

Six cards and six envelopes are numbered 1, 2, 3, 4, 5, 6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the ...
3
votes
1answer
28 views

Piecing together full density subsequences

A subset $A$ of $\mathbb{N}$ is said to be of full density if: $$\lim_{n\rightarrow \infty} \frac{|A\cap [1,n]|}{n}=1.$$ Suppose there exists a function $g:\mathbb{N}\rightarrow\mathbb{R}^{\geq 0}$, ...
3
votes
0answers
82 views

Convergence of integers by transformations

Let $x=(a,b)$, where $a,b$ are in $N$ Now we have the transformations: $$T_1(x) = (ka, b+1)$$ $$T_2(x) = (b,a)$$ where $k$ is in $N$. Where the order of choosing a transformation is not fixed. ...
3
votes
4answers
184 views

When a set of consecutive numbers can be covered by differences between distinct integers?

I will start with an example. Suppose that I would like to cover the set $\{1,2,3\}$ by differences between three integers $m_1,\ m_2$ and $m_3$ in the following sense: $$ ...
2
votes
0answers
112 views

Least Impossible Subset Sum

Given a set A which contains natural numbers from 1 to N. Also given another set B which contains p natural numbers between 1 to N. We have to find out the least sum of subset which is not possible in ...
1
vote
0answers
165 views

Minimum Sum that cannot be obtained from the 1…n with some missing numbers

Given positive integers from $1$ to $N$ where $N$ can go upto $10^9$. Some $K$ integers from these given integers are missing. $K$ can be at max $10^5$ elements. I need to find the minimum sum that ...
6
votes
1answer
221 views

IMO 2015 warm up problem

I get this problem from IMO 2015 facebook page. Let $x_i$ be positive integers for $i=1,2,...,11$. If $x_i+x_{i+1}\geq 100$, $|x_i-x_{i+1}|\geq 20$ for $i=1,2,...,10$. And $x_{11}+x_{1}\geq 100$, ...
-3
votes
1answer
106 views

Integers Placed On A Circle

My problem is such: On a circle there are $9$ distinct positive integers aranced in such a way that the product of two non-adjacent numbers in the circle is a multiple of $n$ and the product of any ...
3
votes
1answer
23 views

Boundedness of $\gcd(|x-y|,|a_x-a_y|)$ in sequence

Let $a_1,a_2,\ldots$ be an infinite sequence of distinct positive integers, and let $n$ be a positive integer. Does there always exist integers $x,y$ such that $\gcd(|x-y|,|a_x-a_y|)>n$? When ...
24
votes
3answers
577 views

Arithmetic Progressions in slowly oscillating sequences

An infinite sequence ($a_0$, $a_1$, ...) is such that the absolute value of the difference between any 2 consecutive terms is equal to $1$. Is there a length-8 subsequence such that the terms are ...
1
vote
3answers
170 views

this is a conjecture or a result? every arithmetic progression contains a sequence of $k$ “consecutive” primes for possibly all natural numbers $k$?

Writing a little better the previous question: is it true that if we let $a$ and $b$ be coprime integers, then the arithmetic progression : $a + bh: h\in {\mathbb Z}$, contains a sequence of $k$ ...
6
votes
2answers
208 views

Number of sudokus with no consecutive arithmetic progression of length 3 in any row or column.

How many such Sudokus are there? Any reference to papers, books, articles or any insight into the problem will be greatly appreciated. I've tried several search engines, scholarly and not, with no ...
1
vote
1answer
82 views

Circular variation with repetition

I would like to know formula for circular variation with repetition. What I mean is : You have round table with n-spots. On every spot there can be number from 1 to k. So for n = 4 and k = 3 ...
5
votes
1answer
186 views

How prove that there are $a,b,c$ such that $a \in A, b \in B, c \in C$ and $a,b,c$ (with approriate order) is a arithmetic sequence?

Let $N=\{ 1,2,3,..., 3n \}$ with $n$ is a positive integer and $A,B,C$ are three arbitrary sets such that $A \cup B \cup C = N, A \cap B = B \cap C = C \cap A = \varnothing, |A| = |B| = |C| = n $. How ...
2
votes
0answers
66 views

Efficient way to count number of arithmetic progression on coloring of $\mathbb{N}$.

Consider a coloring of $\mathbb{N}$ with two colors. How many monochromatic arithmetic progressions of a fixed length $m$ (i.e. numbers of the form $a+nd$ are colored the same) are there in the subset ...
1
vote
1answer
52 views

Parity of Partition Function

Let $T(n)$ denote the number of partitions of $n$ into parts not congruent to $3$ mod $6$. Deduce that $T(n)$ is also the number of partitions of $n $ in which odd parts appear at most twice (even ...
11
votes
2answers
157 views

What are Green's almost primes?

In a general-audience talk, Ben Green explains his famous proof with Terence Tao as an application of Szemer├ędi's theorem, but placing the primes within a smaller set of almost-primes in which they ...
13
votes
1answer
446 views

Narcissistic numbers in other bases

It is well known that $153$ is a narcissistic number; that is, it is equal to the sum of the cubes of its digits since $153=1^3+5^3+3^3$. Other bases have similar numbers. For example, in base $3$, ...
2
votes
1answer
83 views

Numbers not of the form $x^2+My^2$

Why are there only 436 numbers not of the form $x^2+My^2$ for $x>0$, $y>1$ and $M>0$? This is A074885 from OEIS. The last number is 1875902. Can the following argument be fixed up? I ...
0
votes
1answer
55 views

Combinations problem with 2 contradicted answers!

If I have the digits from $0$ up till $9$: $0,1,2,3,\cdots,9$. How many 3-digit number can be made from these set of digits if the number is greater than $600$? My solution was as follows:There are ...
2
votes
3answers
517 views

Multiset Combination in Combinatorics

I want to buy a $k$-combination of doughnuts, where $k$ is any amount less than or equal to the total doughnuts available. At the bakery there are $n$ different types of doughnuts but there are ...
8
votes
1answer
267 views

Expectation of a Random Subset of the Roots of Unity.

Let $p$ be a prime. If $1_A(x)$ denotes the indicator function of the set $A\subset\mathbb{Z}/p\mathbb{Z}$ and $$\hat{1}_A(t):=\frac{1}{p}\sum_{n=1}^p 1_A(n)e^{2\pi i \frac{nt}{p}}$$ denotes the ...