3
votes
0answers
87 views

Sum of product partitions of divisors

Let $M(n)$ be the the set of the multiplicative partitions of $n$, and let $D(n)$ be the set of the sum of the multiplicative partitions of the divisors of $n$. eg $M(30)=\{\{30\},\{2,15\},\{3, ...
2
votes
2answers
42 views

Formula for the number of solutions of the congruence equation $xy-wz=0$ over $\mathbb{Z}_p$?

The equation $xy-wz=0$ has 10 solutions over $\mathbb{Z}_2$ and 33 solutions over $\mathbb{Z}_3$ (e.g. $x=y=2 \land w=z=1$ is one of the solutions). Is there any formula for the number of solutions ...
2
votes
1answer
42 views

In how many ways can a number be factorized over the field $\mathbb{Z}_p$ into two numbers?

For example, over the field $\mathbb{Z}_5$, we can factor number 4 into two numbers in three different ways, i.e. 4=4$\times$1, 4=2$\times$2, and 4=3$\times$3. I am looking for a general formula of ...
2
votes
3answers
95 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
61 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 ...
3
votes
1answer
155 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
61 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
556 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
73 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
94 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
89 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
117 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
132 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
101 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
182 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
63 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
57 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
132 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
134 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
123 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
74 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
227 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
161 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
337 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
350 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
105 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
137 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
241 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 ...
14
votes
3answers
446 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
275 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 ...
4
votes
2answers
256 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
237 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
245 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
268 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
186 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
357 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
103 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
218 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
338 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
221 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 : ...
10
votes
3answers
331 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
207 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
538 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
208 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?