2
votes
3answers
87 views

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$. I could not approach the problem at all. I have no idea how to try the problem. Please help.
0
votes
1answer
43 views

Integer linear combinations of coprime integers

Consider the finite set $S=\{s_1,s_2,\dots,s_n\}$ such that $GCF(s_1,s_2,\dots,s_n)=1$. Show that $\exists n$ such that $n$ cannot be written as $n=c_1s_1+c_2s_2+\dots+c_ns_n \forall c_i,s_i \in ...
2
votes
1answer
120 views

Why is Euler's totient function equal to (p-1)(q-1) when N=pq and p and q are prime? [duplicate]

Why is Euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime? I had my own proof for it but I really don't like it (it feels not intuitive at all because it requires ...
1
vote
0answers
55 views

Estimations for the number of prime factors, counted with multiplicity (elementary combinatorics)

If $N_k(x):=\ \mid\{n\leq x : \Omega(n)=k\}\mid$, where $\Omega(n)$ is the number of prime factors (counted with multiplicity) in $n$, I am trying to reason a crude under-estimate for large $k$ and ...
3
votes
2answers
434 views

How many perfect squares divide 1!2!3!4!5!6!7!8!9!

What I naturally did was to find the prime factorisation of the product of factorials which is $ 2^{30}3^{13}5^5 7^3 $. Clearly there is 15 unique perfect squares that divide $2^{30}$, 6 unique ...
0
votes
0answers
69 views

parity of powers of prime factors

lets consider the prime factorisation of a number N let the powers of the primes in this factorisation be a,b,c ....and so on. Is there a way to determine whether the number of powers that are even ...
2
votes
1answer
89 views

Is it true that $p_{n}+p_{n+1}>p_{n+2}$ for all $n\geq 2\ ?$

Let $p_{n}$ denotes the $n$-th prime number. Is it true that $p_{n}+p_{n+1}>p_{n+2}$ for all $n\geq 2\ ?$
3
votes
1answer
85 views

Bounding the density of finite coprime sets

I am currently running into a problem related to coprime numbers. Consider a set of $d$-dimensional integer vectors, $z \subset \mathbb{Z}^d$ such that each component $z_i$ is bounded by another ...
0
votes
1answer
103 views

Divide 500 into certain group so that all no's 1 to 500 can be found.

500 coins are there. Divide 500 coins into certain bags such that any rupees from 1 to 500 can be found by the combination of the bag's coins. What are the minimum nos of bags ?
3
votes
2answers
115 views

Efficiently identifying spam honeypots

I realise that the title is computing specific, but I think the underlying problem is general - I just don't know how to phrase it more generally (which may be part of my problem). So I am asking ...
1
vote
1answer
82 views

Divisibility of multinomial by a prime number

What is the condition for divisibility of multinomial $ \dbinom {n}{x_1, x_2, \dots, x_k} $ by a prime $p$? Update: I tried to solve using a generalisation of Lucas Theorem by representing the $n$ ...
2
votes
1answer
49 views

A question on primes and equal products

Is the following statement true; "For any odd prime number $p$ , any set of $p-1$ consecutive integers can not be partitioned into two subsets such that the elements of the two sets have equal ...
6
votes
2answers
154 views

Proving that a “prime graph” is connected

Let the prime graph be defined as the graph of all natural numbers, with two vertices being connected if the sum of the numbers on the two vertices add up to a prime number. Prove that the prime ...
2
votes
1answer
57 views

Counting the number of distinct integers in a range that fit a specified pattern

I've been thinking about primorials in the context of the twin prime conjecture. I am seeing this primarily as an exercise to improve my intuition about primorials and prime patterns more than the ...
1
vote
1answer
54 views

Divisibility and factors [duplicate]

1) Can factors be negative? Please prove your opinion. 2)If prime factorization is given to you, how will you find out how many composite factors are there? Not the factors, just how many. For 2), my ...
0
votes
1answer
120 views

Number of combinations

You are given K prime numbers, bigger than 6, find the number of different number that can be made of those prime numbers(using 1 number, 2 numbers ..., k numbers). Obviously you need to get the ...
0
votes
0answers
125 views

Iterate over combinations ordered by sum

I have a sorted list of a large number of primes. I want to iterate over combinations of fixed size $n$ in increasing order of their sum. Naturally the standard approach for $n=4$: $$s_0 = \sum(A, ...
0
votes
1answer
115 views

Total number of ways to arrange the prime divisor of a number so it can be written using M digits

How many ways we can arrange all the prime divisor of a number so it can be written using M factors, where M <=T. T is the total number of prime divisor of the give number N. Example:N=27, its ...
0
votes
0answers
72 views

Distribution of binary digits in moduli

Considering the (infinite) set of all positive integers that are a product of $2$ primes only, represented in binary $100...01$. Question: is the distribution of the proportion of $0,1$ digits ...
0
votes
1answer
208 views

Six Unique numbers which generate unique sum during addition

I have a Six numbers which are like points that satisfy certain condition. If the condition is satisfied that point will be given or else 0 will be assigned as points. I am Storing the points in ...
0
votes
2answers
138 views

The number of possible factorizations of a positive integer.

Given a positive integer $n>1$ with prime factorization $$n=\prod_{p_i \text{ prime}}p_i^{k_i}, \space i\ge1, \space k_i \in \mathbb N^*$$ how can I compute the number of factorizations of ...
3
votes
1answer
320 views

Longest Odd/Even Sequence in Composite Patterns

NOTE I have completely reworded this because I made a complete hash of it the first time, it got worse as I added to it. I apologize to anyone who might have been confused, and hope that this will be ...
1
vote
3answers
311 views

Finite or infinite set?

Due to my not-so-advanced math skills, this question may take a few attempts to state clearly: Consider the unordered pair (2-tuple) partitions of n (e.g. with n=4, we have {{4,0},{3,1},{2,2}}). ...
0
votes
2answers
132 views

$k$ hands in $n$'s hair

Moderator Message: this question is from an ongoing competition. Define a prime $p$ as having $k$ hands in $n$'s hair if $p^k|n$ and $n|2^n+1$ . Does there exist an integer $n$ with $2012$ hands ...
3
votes
1answer
102 views

Upper bound on smallest prime $p$ needed to tell two numbers $\leq n$ apart modulo $p$

I'm going through this paper: E. D. Demaine, S. Eisenstat, J. Shallit, and D. A. Wilson. Remarks on separating words. ArXiv e-prints, March 2011. And on page 2, there is the following lemma: Lemma ...
2
votes
2answers
131 views

Minimum set of US coins to count each prime number less than 100

Say I wanted to be able to carry enough coins in my pocket such that at any time, I could count out exact change totaling any of the prime numbers less than 100. How would I determine the minimum set ...
4
votes
1answer
91 views

Find $k$-tuples satisfies $j=n_2+2n_3+\cdots+(k-1)n_k$ if $n_1+\cdots+n_k=n$.

Let $n_i \in N$, $i=1,\ldots,k$ and such that $n_1+\cdots+n_k=n$. Fix $j \in N$. I would like to find all $k$-tuples (or algorithm how to find $k$-tuples) satisfies $$ j=n_2+2n_3+\cdots+(k-1)n_k $$ ...
3
votes
1answer
232 views

(Not) Surprising Result on Natural Numbers as Sum of $k$-Almost Primes

I started with the following idea: Let $P_k$ be the infinte set of all $k$-almost primes. The counting function for $k$-almost primes less than $x$, is $\displaystyle \pi_k(x)\sim\frac{x}{\log ...
13
votes
3answers
433 views

Are the logarithms in number theory natural?

I find the frequent emergence of logarithms and even nested logarithms in number theory, especially the prime number counting business, somewhat unsettling. What is the reason for them? Has it maybe ...
1
vote
2answers
262 views

Question on (Semi) Prime Counting Functions

I'm looking for a function counting all numbers, let's call them power semi-primes for the moment, of the form $a^nb^m\leq t$. $a,b$ are primes and might be equal. Edit: $n$ and $m$ are fixed. I ...
3
votes
2answers
235 views

Counting Functions or Asymptotic Densities for Subsets of k-almost Primes

This question is an extension of this question. There the asymptotic density of k-almost primes was asked. By subsets I mean the following: Let $\lambda$ be a partition of $k$ and $P_{\lambda}=\{ ...
4
votes
2answers
232 views

Is there a connection between König's infinity lemma and primes?

Google search yields the paper by RH Cowen called Generalizing König's infinity lemma. Due to my insufficient technical background, I am afraid, I cannot fully appreciate the paper. Tout court, ...
3
votes
2answers
237 views

Given a finite list of prime factors, what is the fastest way to find all numbers that can be formed from them

$$ \text{Let} \ S = \{p_1,p_2,p_3,...,p_n\} $$ $$ \text{where} \ p_i \in \Bbb P$$ What is the fastest known method method/algorithm to generate all unique numbers through product operation on $S$? ...
4
votes
2answers
262 views

How many ordered triple $ (p,a,b) $ is possible such that $p^a=b^4+4$?

If we have a prime number $p$ and two natural numbers $a$ and $b$ such that $p^a=b^4+4$, then how many such ordered triplets $(p,a,b)$ exist? What should be the strategy to solve this one? The only I ...
1
vote
1answer
180 views

Unique factorization less than 100

How do I approach this problem using unique factorization?... How many numbers are product of (exactly) $3$ distinct primes $< 100$? edit: Just to add to that, How does unique factorization ...
6
votes
1answer
343 views

Combinatorial interpretation of the Prime Number Theorem?

One version of the Prime Number Theorem is that $p_n \sim n \ \ln \ n$, while by Stirling's formula $\ln(n!) \sim n \ \ln \ n$; consequently, $p_n \sim \ln(n!)$, $\rm \color{red}{\text{and } e^{-p_n} ...
2
votes
1answer
99 views

With what probability is this polynomial equal to zero (mod a prime $p$)?

If we suppose that we have a polynomial $q(x)$ of the following form: $q(x) = \sum_{i=0}^N{c_i x^i} \text{ where } c_i=0 \text{ or } c_i=1$ In other words, if we are given a polynomial with binary ...
4
votes
1answer
214 views

$16$ natural numbers from $0$ to $9$, and square numbers: how to use the pigeonhole principle?

There are $16$ natural numbers placed next to each other. Each is a number from $0$ to $9$. These are in any order, and you can have as many repeats as you want (e.g. all $16$ numbers can be zero, or ...
4
votes
4answers
318 views

How many cpus needed to check a 100 million digit prime number efficiently?

If I had access to potentially large number of CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the ...
1
vote
0answers
213 views

Anti-prime sequence

I have permutation from $x$ to $y$. And how to make sequence which $d$ summed numbers from this sequence ISN'T a prime number. if we have sequence $x_1,x_2,x_3,x_4,x_5 \dots y$ than $d$ means : ...
9
votes
3answers
307 views

Are there any Combinatoric proofs of Bertrand's postulate?

I feel like there must exist a combinatoric proof of a theorem like: There is a prime between $n$ and $2n$, or $p$ and $p^2$ or anything similar to this stronger than there is a prime between $p$ and ...
7
votes
3answers
202 views

Combinatorics question: Show divisibility

Let $a\geq2$, $b\geq2$ be two prime numbers and k be a natural number with $k\leq min(a,b)$. How can one show that $z := \binom{a+b}{k} - \binom{a}{k} - \binom{b}{k}$ is divisible by the product ...
7
votes
2answers
526 views

Accuracy of approximation to inclusion-exclusion formula in prime sieve

This thing came up in a combinatorics course I am taking. Choose a fixed set of primes $p_1,p_2,\dots,p_k$ and let $A_n$ be number of integers in $\{1,2,\dots,n\}$ which are not divisible by any of ...
5
votes
1answer
206 views

Partitioning sets such that the sum of 2 elements is Prime

Given an $n >0$ is it possible to partition the set $\mathcal{P} = \{1,2, \cdots, 2n\}$ into $n$ pairs $(a_{i},b_{i})$ such that $a_{i} + b_{i}$ is a prime?