Questions tagged [combinatorial-number-theory]
This is a tag used for number-theoretical questions with combinatorial flavor.
74
questions
1
vote
2
answers
68
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, \...
- 16.9k
3
votes
1
answer
57
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$. ...
- 15.4k
1
vote
0
answers
46
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,...
- 580
2
votes
0
answers
303
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$ ...
1
vote
0
answers
64
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 ...
1
vote
1
answer
43
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}$
...
- 343
0
votes
0
answers
39
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 ...
- 103
0
votes
1
answer
68
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-...
- 103
0
votes
1
answer
49
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 ...
- 107
7
votes
1
answer
323
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{...
- 1,007
2
votes
1
answer
346
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 ...
- 1,131
0
votes
0
answers
47
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'...
- 1
0
votes
1
answer
40
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} + ...
2
votes
0
answers
64
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 ...
1
vote
0
answers
57
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 ...
2
votes
0
answers
43
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(...
- 1,963
2
votes
0
answers
23
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 ...
- 175
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 ...
- 492
0
votes
0
answers
193
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 ...
2
votes
1
answer
140
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 ...
- 825
4
votes
1
answer
135
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 ...
- 161
1
vote
0
answers
25
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 ...
- 1,375
2
votes
1
answer
133
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 ...
- 87
1
vote
0
answers
41
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$?
...
- 1,811
1
vote
1
answer
85
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,...
- 1,250
0
votes
2
answers
117
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 ...
user721372
9
votes
2
answers
420
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 \...
- 15.5k
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$ ,
$...
1
vote
1
answer
83
views
Ann and Ben plays the following game
My Math Team Teacher gave us this combinatorial-number-theory problem.
Ann and Ben plays the following game:
The numbers $1, 2, 3,...,n$, where $n\in\mathbb{Z}^+$, are written on the blackboard.
Ann ...
- 2,707
5
votes
1
answer
81
views
Who has the winning strategy for the game?
My friend Mickey asked me to play the following game with him.
The number $1$ is written on the whiteboard. Me and Mickey take turns to do the following, starting with me.
If the number written on ...
- 2,707
2
votes
3
answers
233
views
A fraction $p/q<1$ such that $p+q=333$.
Let $p/q<1$ and $p+q=333$. Show that the number of fractions where $p$ and $q$ has no common factor is $108$.
This is what I’ve worked out:
$333/2 = 166.5$,
and since $p<q$,
$p\leq 166, $
$...
- 63
2
votes
1
answer
92
views
How many copied numbers?
When I was doing my math team training, I encountered a difficult question. The question is
If there is exist a natural number $n$ such that a number equal $n$ written twice, then $n$ is a copied ...
- 2,707
1
vote
1
answer
57
views
Prove that for every $n\geq6$ the equation $1/a_1^2 + ... 1/a_n^2 = 1$ has answer in $\mathbb{Z}$
Prove that for every $n \geq 6$ the equality $1/a_1^2 + ... 1/a_n^2 = 1$ has answer in $\mathbb{Z}$ (I mean it has an answer where all $a_i \in \mathbb{Z}$) (Repetition is allowed)
After some testing ...
- 869
5
votes
1
answer
109
views
Is the problem Find all $x,y \in \mathbf{N}$ such that $\binom{x}{2} = \binom{y}{5}$ solved?
I was recently browsing and came upon this document which gives some open problems involving Diophantine Equations.
Document: http://www.math.leidenuniv.nl/~evertse/07-workshop-problems.pdf
Upon ...
- 95
2
votes
2
answers
131
views
The number of $f \circ f=f $
Let $A=\{1,2,3...n\}$，How many functions satisfy the following conditions？
(1) $f \circ f=f $
(2) $f \circ f =I_A$
(3) $f \circ f\circ f=I_A$
$\circ$ is composite.
The question is from a '...
- 853
3
votes
0
answers
45
views
If $A\subset\mathbb N$ does not contain any two integers such that one divides the other, must $A$ have density $0$?
Suppose we have a set $A\subset\{1,2,3,\ldots\}$ such that there do not exist $m,n\in A$ where $m\mid n$. Does it follow that $A$ has natural density $0$?
(Note: The definition of the natural density ...
- 525
1
vote
0
answers
96
views
Generating function for number of partitions with Rank and Crank
The generating function for the number of partitions, $p(n)$ of a number is given by $\displaystyle{\sum_{n=1}^{\infty}p(n)q^n=\frac{1}{(q;q)_{\infty}}}$ where $(q;q)_{\infty}=\displaystyle{\lim_{n \...
- 106
0
votes
0
answers
41
views
What composite number can be represented as $\binom{n}{k}$ for $k\neq1$ or $n-1$
This is a problem I came up with when I was working with binomial coefficients. Let's call the title statement $(*)$. Obviously for any primes do not satisfy $(*)$, therefore we only need to focus on ...
- 4,843
5
votes
2
answers
287
views
Number of triples of divisors who are relatively prime as a triple
Given a number $n \in \mathbb{N}$, define $a(n)=\{(d_1,d_2,d_3): d_i|n,\ \gcd(d_1,d_2,d_3)=1,\ 1 \leq d_1 \leq d_2 \leq d_3\}$. What is $|a(n)|$?
There were similar questions asked about pairs rather ...
- 321
0
votes
0
answers
98
views
Is this a proof for the rational distance problem of a unit square?
I found this 2015 research paper (http://unsolvedproblems.org/S75.pdf) that claims it has solved the rational distance problem of a unit square. When I look in other stackexchange and reddit threads, ...
1
vote
0
answers
116
views
Combinatorial counting problem for induced subgraphs
We define P(x,y) in the following way: Given an initial undirected graph of n vertices,
P(x,y)=1 if an induced subgraph with exactly x vertices and y edges exists. Else P(x,y)=0.
For example, let ...
- 11
1
vote
1
answer
161
views
$\sum_{i=1}^n P(n,i)$ [duplicate]
We can know clearly from
$$(1+X)^n=\sum\limits_{i=0}^{n}C(n,i)X^n$$
that
$$ \sum\limits_{i=0}^{n}C(n,i)=2^n.$$
Whereas, I want to know if there are any researched results about permutations in the ...
user517681
2
votes
2
answers
92
views
$A+A\subseteq A\times A$
Define $A+A=\{a+b\colon a,b\in A\}$,$A\times A =\{ab\colon a,b\in A\}$.
Does there exist a finite integer set $A\subseteq \mathbb{Z}^+$, such that $|A|>1$ and $A+A\subseteq A\times A$ ?
- 1,170
8
votes
2
answers
199
views
Bijective proof that $8+1=9$, or really $3^2-1=2^3$
Catalan's conjecture states that $8$ and $9$ are the only consecutive powers. This suggests to me that the identity $3^2-1=2^3$ might be purely "accidental". So here's the challenge: Is there any ...
- 26.6k
3
votes
1
answer
255
views
Lonely Runner Conjecture proof for $k=3$ runners
I'm currently reading Lonely runner conjecture which has been proved upto $k=7$. I could understand the cases with $k=1,2$ i.e, one and two runners repsectively, but I am stuck at $k=3$. Can anyone ...
- 165
1
vote
1
answer
34
views
Finding number of n digit Terminate NUMBERS
One is allowed to use the digits 5,6,7,8 any number of times to form a terminate number. A n digit terminate number is one which contains digit 5 either an even number of times or does not contain ...
- 401
4
votes
1
answer
72
views
moving on a grid with integer condition
assume you are a flea jumping on a grid (similar to $\mathbb{Z}^2$). You can do any jump that define an integer distance, but moreover it has to change both coordinates (for instance, the moves (3,4) ...
- 331
2
votes
1
answer
103
views
Relation between some prime numbers and their sum
Let $p$ and $q$ be two prime numbers less than $900$ billion. If $p + 6, p + 10, q + 4, q + 10$ and $p + q + 1$ are all primes, what is the greatest value that $p + q$ can take?
Can you help me to ...
- 153
6
votes
2
answers
406
views
Probability that the sum of $k$ distinct integers selected from $1, 2, \dots, n$ is divisible by $n$
Would you please help me solve Problem 7 of Section 4.5, "Combinatorial Number Theory," in An Introduction to the Theory of Numbers, Niven, Zuckerman, Montgomery, 5th ed., Wiley (New York), 1991:
...
- 2,991
5
votes
1
answer
211
views
Multisets $A$ and $B$ of positive integers so that sum of $A$ is product of $B$ and vice versa
I happened to notice that $2 \cdot 3 = 1+5$ and $2+3 = 1 \cdot 5$. I researched a little further:
With size (cardinality) 1 there is trivially an infinite amount of solutions.
With size 2 there is ...
- 103