The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [arithmetic-combinatorics]

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.

41 questions
Filter by
Sorted by
Tagged with
0answers
30 views

### Regarding the Erdos-Szemeredi Sum/Product Conjecture

Edit: The theorem that was proved is here: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szemer%C3%A9di_theorem , basically a statement that either there can be many unique elements in a sum matrix ...
0answers
118 views

### Erdos conjecture on arithmetic progression

My motivation for this enquiry is due to interest on Erdos conjecture on arithmetic progression. (https://en.wikipedia.org/wiki/Erd%C5%91s_conjecture_on_arithmetic_progressions) Having come across ...
1answer
71 views

### Minors of a particular matrix?

Take an $\frac{n(n-1)}2\times n$ matrix $M$ with $0/1$ entries each row distinct each row having two $1$s. Take an $\frac{n(n-1)}2\times \frac{n(n-1)}2$ matrix $N$ with $0/1$ entries each row ...
2answers
113 views

### Number of non-negative solutions of an equation with restrictions

Q: Find the number of non-negative solutions of the equation $$r_1+r_2+r_3+\ldots +r_{2n+1}=R$$ when $0 \le r_i \le \min(N,R)$ and $0\le R\le (2n+1)N$. My Attempt: I tried the stars and bars method ...
2answers
84 views

### Number of non-zero entries of self-convolution

Let $f(k)$ be a function on the integers with the properties $f(k)\geq 0$ $\forall k$ $f(k)\geq p$ for at least $t$ values of $k$ Let $g(k)=\sum_{k'} f(k')f(k-k')$ be the self-convolution of $f$. ...
1answer
76 views

### ∀n ∈ N, ∃w1, w2, . . . , wn ∈ A+ such that w = w1w2 . . . wn and C(w) = C(wi) ∀i ∈ {1, . . . , n}

A is a finite set of letters and A+ denotes the set of all finite length strings formed by letters in A, i.e. ∀w ∈ A+, w is a string, each letter in w belongs to A and len(w) ≥ 1. E.g.- If A = {a, b} ...
1answer
186 views

### How many natural numbers below 1 million have their sum of digits equal to 18?

How many natural numbers below 1 million have their sum of digits equal to 18? One way to solve this would be to make all possible cases in which the digits of the no. add up to 18 and then permute ...
1answer
512 views

### How many five-digit numbers can be formed using the digits 1-9 which have at least three identical digits?

How many five-digit nos. can be formed using the digits 1-9 having at least three identical digits? My attempt: Total no. of possible nos. with no restrictions $=9^5$ No. of numbers having two ...
0answers
70 views

### A conjecture on partitions of $\{1,\ldots,n\}$ [closed]

Conjecture: Let $n$ $∈$ $N$. Then for each factor $m ≥ n$ of $n$($n + 1$)/$2$, one can partition the set $\{1, 2, 3, \ldots , n\}$ into disjoint subsets such that the sum of elements in each subset is ...
1answer
44 views

### Representing a number as $a^2+db^2$ given $d$

Given integers $n$ and $d$, how can I find integers $a$ and $b$ (or show that they do not exist) such that $n=a^2+db^2$? If it helps, in my present application I know the factorizations of $n$ and $d$...
2answers
579 views

### Sum and product of k real numbers > 0 is unique?

Can we prove that $\sum_{i=1}^k x_i$ and $\prod_{i=1}^k x_i$ is unique for $x_i \in R > 0$? I stated that conjecture to solve CS task, but I do not know how to prove it (or stop using it if it is ...
1answer
135 views

### find the least natural number n such that if the set $\{1,2,…,n\}$ is arbitrarily divided into two nonintersecting subsets

Find the least natural number $n$ such that if the set $\{1,2,\dots,n\}$ is arbitrarily divided into two non intersecting subsets then one of the subsets contains three distinct numbers such that the ...
2answers
202 views

### Combinatorics with a condition.

Jane is giving gifts to 3 sets of cousins who are brother-sister pairs. She gives the gifts one after the other to her 6 cousins on the condition that no brother receives a gift before his sister. ...
1answer
20 views

0answers
166 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 ...
0answers
248 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 ...
1answer
889 views

3answers
661 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 ...
3answers
283 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$ "...
2answers
245 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 ...
1answer
224 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 ...
1answer
222 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 ...
0answers
188 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 ...
1answer
85 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 ...
2answers
236 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 ...
1answer
623 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$, ...
1answer
93 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 ...
2answers
244 views

### Combinatorics in finite cyclic groups

Discuss the following. I got a good platform to remove all me quarries from my mind by positing the problems like this. Thanks again for support. 1) Find the minimum elements must be selected from ...
1answer
59 views

1answer
330 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 ...
0answers
310 views

### Uses of Chevalley-Warning

In the recent IMC 2011, the last problem of the 1st day (no. 5, the hardest of that day) was as follows: We have $4n-1$ vectors in $F_2^{2n-1}$: $\{v_i\}_{i=1}^{4n-1}$. The problem asks : Prove the ...