Questions tagged [combinatorial-number-theory]

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

Filter by
Sorted by
Tagged with
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, \...
user avatar
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$. ...
user avatar
  • 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,...
user avatar
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$ ...
user avatar
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 ...
user avatar
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}$ ...
user avatar
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 ...
user avatar
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-...
user avatar
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 ...
user avatar
  • 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{...
user avatar
  • 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 ...
user avatar
  • 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'...
user avatar
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} + ...
user avatar
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 ...
user avatar
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 ...
user avatar
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(...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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$? ...
user avatar
  • 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,...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 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$ , $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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, $ $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 '...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$ ?
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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) ...
user avatar
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 ...
user avatar
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: ...
user avatar
  • 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 ...
user avatar