Skip to main content

Questions tagged [combinatorial-number-theory]

This is a tag used for number-theoretical questions with combinatorial flavor.

Filter by
Sorted by
Tagged with
0 votes
1 answer
27 views

Enumeration of $k$-sparse 0/1-vectors of length $N$ [duplicate]

Let $\mathbf{x}$ be a $k$-sparse vector of length $N$ containing $k$ ones. There are $N\choose k$ such vectors and one would need $\log_2 {N\choose k}$ bits to enumerate all of them. Is there an ...
Ema's user avatar
  • 31
1 vote
1 answer
46 views

Existence of Solutions of mixed Linear-Quadratic Equation System modulo $p$

I need some help on the existence of solutions of an equation system modulo some prime $p$. The equation system has three parametes $n$, $N$ and $p$ and the equations are of the form $$ \sum_{i=1}^n ...
rkw's user avatar
  • 19
0 votes
0 answers
47 views

Given a set of whole numbers $\{1,\ldots,k\}$, how many combinations of the set add to integer $N$?

For a set of whole numbers from $1$ to $k$, how many combinations can be made that add to $N$? I had half solved this problem not too long ago, and when plotted on a table I got a diagonal ...
charlie's user avatar
0 votes
0 answers
67 views

What is the maximum range of a convex finite additive 2-basis of cardinality k?

Conjecture: Given any $d \in \mathbb{Z}_{\geq 2}$ and $k=2d-2$, we have \begin{align*} \max \{ n : (\exists &f \in \{ \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0} \})\\ &[((\forall i \in \...
Michael Chu's user avatar
1 vote
1 answer
100 views

How many subsets $S$ of integer interval $[0,n]$ such that $n, n-1 \not \in S+S$?

Conjecture: Given any $n \in \mathbb{Z}_{\geq 0}$, we have $$|\{S : (S \subseteq [0,n]) \land (n, n-1 \not \in S+S)\}| = F(n+2),$$ where $F$, the sequence of Fibonacci numbers, is given by $F(j) = F(...
Michael Chu's user avatar
1 vote
0 answers
73 views

Largest subset of $\{1, 2, ..., n\}$ containing no two elements whose product is a square

Suppose $n$ is a positive integer. Let $f(n)$ denote the largest size of a subset $T$ of $\{1, 2, ..., n\}$ such that $T$ does not contain any two elements $a, b$ whose product $ab$ is a perfect ...
Prism's user avatar
  • 11.3k
2 votes
1 answer
104 views

If $\mathbb{N}$ is partitioned into finitely many subsets, must one of the subsets be a finite basis?

I recently came across an interesting problem in this document from the Berkeley Math Circle (year 2000). Namely, Problem 4 in page 2 asks: Problem. A set $S$ of positive integers is called a finite ...
Prism's user avatar
  • 11.3k
1 vote
0 answers
33 views

Showing that a set of equations have positive density of solutions

Consider the following set of equations $$a_{0}b_{0} \neq 0, \hspace{3mm} a_{0}b_{1}+a_{1}b_{0} = 0, \hspace{3mm} \text{ and } a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0} = 0 $$ in the variables $\vec{a} = (a_{0}...
Gafar Maulik's user avatar
1 vote
0 answers
30 views

Skolem-Mahler-Lech Converse

Can any periodic set of integers be realized as the zero-set of a linear recurrence relation? It's stated on the OEIS page for eventually periodic sequences that "all eventually periodic ...
Jon Hillery's user avatar
4 votes
0 answers
83 views

Any $n$ distinct positive integers always have three of them with large least common multiple

The problem is stated as follows: Prove or disprove: there exists some absolute constant $c>0$, satisfying the following statement: Given any $n$ distinct positive integers $a_i$, $1\leq i\leq n$, ...
Alxercc's user avatar
  • 81
2 votes
1 answer
51 views

How to show $A_x:= \{ \left\lfloor x^n\right\rfloor:n\in\mathbb{N}\}$ is **not** an additive basis (of order $k=2$) of $\mathbb{N}$ if $x>1?$

I know that there are many unanswered questions and conjectures when it comes to additive bases (of order $k=2$) of $\mathbb{N}.$ However, for the question I have in mind, I think it should be ...
Adam Rubinson's user avatar
1 vote
1 answer
108 views

Can anyone help with this combinatorial number theory problem involving complex numbers? (From Problems from the Book Ch. 7)

Let $a_k,b_k,c_k$ be integers, for $k=1,2,3...,n$ and let $f(x)$ be the number of ordered triples $(A,B,C)$ of subsets (not necessarily non-empty) of $S$ with $A \cup B \cup C=S=\{1,2,3...,n\}$ such ...
Indianimperialist123's user avatar
0 votes
0 answers
15 views

"halfthink sets" contain n and n+1

A problem: Georgina calls a 992-element subset $A$ of the set $S = \{1, 2, 3, . . . , 1984\}$ a halfthink set if • the sum of the elements in $A$ is equal to half of the sum of the elements in $S$, ...
wsxceerf's user avatar
1 vote
0 answers
159 views

Understanding the proof of Van der Waerden's theorem by Graham and Rothschild.

I am studying the proof of Van der Waerden's theorem by Graham and Rothschild. I have tried to understand each step, but I need to fill in some gaps. Van der Waerden's theorem says that: $\forall k, r ...
Sayantan's user avatar
2 votes
0 answers
37 views

Minimising an expression involving prime numbers.

I would like to solve the following problem for a general $n$: Find disjoint sets $P$ and $Q$ of prime numbers so that \begin{align*} \pi_P = \prod_{p \in P} p \leq n \textrm{ and } \pi_Q = \prod_{q \...
Joseph Harrison's user avatar
2 votes
0 answers
143 views

How sparse/"thin" (asymptotically) can additive bases of order $2$ be?

A subset $B$ is called an (asymptotic) additive basis of order $2$ if every sufficiently large natural number $n$ can be written as the sum of at most $2$ elements of $B.$ How small/sparse can such ...
Adam Rubinson's user avatar
1 vote
2 answers
72 views

Combinatorial Analysis: The fundamental principle of counting

Where is my logic wrong? I want to count how many numbers with the digit $2$ there are between $100$ and $400$. I thought the following: I will separate in cases. First case. The first digit is one, ...
Gustavo Gabriel's user avatar
1 vote
0 answers
40 views

combinatorial analysis

I'm trying to justify the combination formula in my head. I arrived at the following conclusion: The combination of n different objects taken r is equal to the product of the number of arrangements ...
Howard_Anton22's user avatar
1 vote
1 answer
39 views

Combinatorial Analysis: The Fundamental Principle of Counting

To solve the following problem: "How many natural numbers with three distinct digits are there?". The best way would be to analyze how many different ways I can choose the first digit (there ...
Howard_Anton22's user avatar
2 votes
0 answers
40 views

Constructing every pair of two square numbers with fixed sum

Let $s\in\mathbb{N}$ have the prime factorization $s=2^gp_1^{f_1}p_2^{f_2}\dots q_1^{h_1}q_2^{h_2}\dots$, where $p_i \equiv 1$ and $q_i \equiv 3$ (mod 4). I already know how many distinct $(a,b)\in\...
Wilfred Montoya's user avatar
18 votes
1 answer
613 views

Let $p$ be a prime number and $S\subseteq\{1,2,\cdots,p-1\}$ be a subset such that $|S|>p^{\frac{3}{4}}$...

Let $p$ be a prime number and $S\subseteq\{1,2,\cdots,p-1\}$ be a subset such that $|S|>p^{\frac{3}{4}}$. Prove that for every positive integer $m$, there exist $a_{1},a_{2},b_{1},b_{2},c_{1},c_{2} ...
nonuser's user avatar
  • 90.7k
1 vote
2 answers
75 views

8 Positive integers making numbers in the range $-1985\leq k\leq 1985$.

Problem. (IMO 1985, Longlisted Problem 25). Find $8$ positive integers $n_1, \ldots, n_8$ with the following property. For every integer $k$, $-1985\leq k\leq 1985$, there are $8$ integers $\alpha_1, \...
caffeinemachine's user avatar
3 votes
1 answer
150 views

Counting numbers up to $n$ whose prime factorizations have exactly $k$ prime factors with exponent $1$

Question. Let $N_k(n)$ count how many numbers $1\le x\le n$ for which $x$ has exactly $k$ unitary prime divisors, or equivalently $x$'s prime factorization has exactly $k$ primes with exponent $1$. ...
anon's user avatar
  • 152k
1 vote
0 answers
50 views

Does $\sum_{i=1}^n p_i(x) \sqrt{q_i(x)} =0 $ imply that $x$ is algebraic?

Let $p_i,q_i \in \mathbb{Z}[X]$ and Let $P(x) = \sum_{i=1}^n p_i(x) \sqrt{q_i(x)} $. Can we deduce that if $P(x) = 0$ then $x$ is an algebraic number? For some simple examples I can see that it's true,...
Kooranifar's user avatar
2 votes
1 answer
2k views

Proof - The number of partitions of n into at most m parts is the number of partitions into parts whose largest part is at most m

The proof is based on Ferrer's diagram. I know the fact that a partition that can be written with a graphical representation is ferrer's diagram. How do start the proof or implement that to prove that ...
Brinder Gurm's user avatar
2 votes
0 answers
326 views

Construct $n$ integers in base $n^2$ that are in the ratio of $1:2:\cdots :n$ using every digit exactly once

Consider the following problem: Given an positive integer $n$, construct $n$ integers $a_1,a_2,\cdots ,a_n$ in base $n^2$. Each of the numbers $0,1,\cdots ,n^2-1$ should occur in the digits of $a_i$ ...
Wallbreaker5th's user avatar
1 vote
0 answers
73 views

Multiplicities of members of the multiset of products of members of a set $A\subseteq\{1,2,3,\ldots\}$

In this answer I included this lemma: Suppose $A\subseteq\{1,2,3,\ldots\}$ and $\sum\limits_{n\in A} \dfrac 1 n < \infty$. Then $\sum\limits_{n\in B} \dfrac 1 n <\infty$ where $B$ is the ...
Michael Hardy's user avatar
1 vote
1 answer
48 views

Express an integer $m$ as sum of 1, 0 and -1 for fixed number of summands $j$

Let $j \in \mathbb{N}_0$. I'm looking for the number of all possible combinations, such that for a given $|m| \leq j, m \in \mathbb{Z}$ $m = \sum \limits_{k=1}^{j} a_k\quad$ where $a_k \in {-1, 0, 1}$ ...
infinitezero's user avatar
0 votes
0 answers
64 views

Generating restricted finite additive $2$-bases from doubly-eager bit-strings

A bit-string is any finite sequence of $1$s and $0$s. For example, $1011011$, $1011010$, and $000110$ are bit-strings. In this post, I will refer to bit-strings as strings, to be concise. I now ...
Michael Chu's user avatar
0 votes
1 answer
90 views

How many subsets $S$ of integer interval $[0,n]$ such that $k \not \in S+S$?

After a bit of experimentation, I thought of the following conjecture: Given any $n \in \mathbb{Z}_{\geq 0}$ and $k \in [0,2n]$, we have $$|\{S : (S \subseteq [0,n]) \land (k \not \in S+S)\}| = 2^{|n-...
Michael Chu's user avatar
0 votes
1 answer
64 views

Prove or disprove: If [$q\in\mathbb{Q}$ and $a+b = x+y+z = q$] then [$a,b,x,y,z ∈$ either $\mathbb{Q}⊻¬\mathbb{Q}$].

A small observation is that the unit integer $1$ can be split arbitrarily into two pieces: both pieces must exclusively be either rational or irrational (but not a heterogeneous mixture). This ...
user946772's user avatar
8 votes
1 answer
512 views

What is the general formula of the sum $\sum_{k=0}^{n}(-1)^{k} \binom{n}{k}\binom{k/2}{m}$ for $m,n\in\mathbb{N}$?

The classical Euler's gamma function $\Gamma(z)$ can be defined by \begin{equation} \Gamma(z)=\lim_{n\to\infty}\frac{n!n^z}{\prod_{k=0}^n(z+k)}, \quad z\in\mathbb{C}\setminus\{0,-1,-2,\dotsc\}. \end{...
qifeng618's user avatar
  • 1,816
2 votes
1 answer
370 views

Is this a strict Lower bound on the amount of numbers less than x but coprime to y?

Let $\Lambda(x,y)$ be the relative totient function that counts the amount of numbers less than $x$, which are coprime to $y$. After interpreting Euler's totient function, $\phi(y)$, as a result of ...
Brad Graham's user avatar
  • 1,161
0 votes
0 answers
51 views

Hybrid 'Discrete triangular number base' numbers

I'm trying to invent a new type of number who's digits are composed of hybrid 'Discrete Triangular Number Base' numbers (Which have two components; one in 'Discrete Triangular Number Base X and Base Y'...
Imk0tter's user avatar
0 votes
1 answer
77 views

5 Distinct non-negative integers who's sum is 51. Prove for every solution there is always one sub-set of size 4 who's sum is at least 42.

Suppose $X = \begin{Bmatrix} x_{1}, & x_{2}, & x_{3}, & x_{4}, & x_{5} \end{Bmatrix}$ is a set of 5 distinct non-negative integers, with a set-sum of $x_{1} + x_{2} + x_{3} + x_{4} + ...
Minko_Minkov's user avatar
2 votes
0 answers
164 views

Ranking and unranking combinations with replacement

Problem statement: You observe a sample of five 6-sided dice. Compute this sample's rank, then show how to unrank it. General Overview The number of combinations with replacement can be calculated as ...
Alexander L. Hayes's user avatar
1 vote
0 answers
58 views

Possible alternate proof of Bertrand's postulate.

I don't know if I am right. So I came here. What I did was use the theta function, defined as the sum $\theta(x)=\sum_{p\leq x} \log{p}$. So we have that there is always a prime between x and 2x, for ...
combinatorialist46Carey2's user avatar
2 votes
0 answers
51 views

Is there a pair of tuples N, M of prime numbers which (a) have the same product, and (b) whose partial products have the same sum?

If N is a finite list of numbers, let $p(N)$ be the product of the numbers in N, that is, $$p(N)=\Pi_{i=1}^{|N|}N_i$$ and let $s(N)$ be the sum of the partial products of the numbers in N, that is $$s(...
Michael Hartley's user avatar
2 votes
0 answers
24 views

Explanation of a variable in this ~1page paper on arithmetical progressions

I'm a first year so this is purely out of curiosity. This paper https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1078964/?page=1 seems to propose a better density for arithmetical-progression free sets. I ...
squirrels's user avatar
  • 217
1 vote
0 answers
28 views

A Number Theory problem based on selection of sequences [duplicate]

Take any 37 integers from the set $\{1,2,3,...112\}$, then show that there will always exist two integers out of those 37 integers such that $(x-y)\in\{9,10,19\}$ Here is my approach: Let the set ...
Pravimish's user avatar
  • 641
0 votes
0 answers
394 views

odd even position of digits in a number

Please give answer of this question with explanation, There is a number 36867294. If the digits at even positions in the number are deleted, then which of the following could be the difference of two ...
Meghav Ladani's user avatar
2 votes
1 answer
205 views

Stationary distribution of a Markov chain on the nonnegative integers

Let $\lambda_k,\mu_k\in\mathbb R_{\ge0}$ $(k\ge1)$ be nonnegative real numbers such that $\sum_{k=1}^\infty k\lambda_k<\infty,$ let $S=\mathbb Z_{\ge0}$ be the nonnegative integers, let $T=\mathbb ...
xFioraMstr18's user avatar
4 votes
1 answer
193 views

Examples in number theory where a heuristic argument fails

Many conjectures in number theory are motivated by heuristic arguments, and many results that are known to be true can be predicted by heuristic arguments. To give an example, consider the Euler ...
Leo's user avatar
  • 181
1 vote
0 answers
31 views

Does every positive power of $7$ contain $2$ in their ternary representation?

Does every positive power of $7$ contain $2$ in their ternary representation? I.e. Determine whether there exists a finite subset of non-negative integers $\{a_1 < \dots < a_n \}$ and a positive ...
Oliver Clarke's user avatar
2 votes
1 answer
230 views

N*n*m distinguishable balls with m different colors

I recently asked the following question which is resolved: n*m distinguishable balls with m different colors, the probability of randomly choosing k balls containing all balls from at least 2 ...
Gongotar's user avatar
1 vote
0 answers
42 views

Simplify $\frac{1}{n}\sum_{d\mid u} \varphi(d)\cdot 2^{\frac{nr}{d}}$

I have been trying to solve the following problem: Let $n$ and $r$ be positive integers. How many subsets of $\lbrace 1,2,\dots, nr\rbrace$ are there whose elements have a sum divisible by $n$? ...
mxian's user avatar
  • 2,019
1 vote
1 answer
114 views

Proving a monotonic subsequence exists

CONTEXT I have been studying about finding the limit of a sequence lately, and it becomes apparent that one way for a sequence to have limit is that it is monotonic and has a lower (or upper) bound. I,...
Nikola Tolzsek's user avatar
0 votes
2 answers
174 views

Prove prime $p$ divides $\binom{p^k}{n}$ for any $n$, $1 \le n \le p^k-1$, $k$ a positive integer

I have got $$\binom{p^k}{n} = \cfrac{p^k}{n} \binom{p^k-1}{n-1}=p\biggl[\cfrac{p^{k-1}}{n}\binom{p^k-1}{n-1}\biggl]$$ The first approach is to show that the term in the square bracket is also an ...
user avatar
8 votes
2 answers
430 views

Is it true that at least two of any consecutive $2m$ positive integers cannot be divided by odd prime numbers less than $2m$?

Let $m>1$ and $p_2,\cdots,p_k$ are all odd prime numbers less than $2m$. $q,a_2,\cdots,a_k$ are arbitrarily selected integers(I mean no matter how you choose these numbers). $$G_1=\lbrace n\in \...
lsr314's user avatar
  • 15.9k
2 votes
0 answers
156 views

Conjecture that relates the set of primes to inequalities

The following conjecture which I posed has been verified for all $n<10000$ , my question is to find a proof or a disproof of it. The conjecture is as follows: Consider for all $n \in \mathbb N$ , $...
Ahmad Jamil Ahmad Masad's user avatar