0
votes
2answers
42 views

Discrete math: probability of picking certain hands with a preset condition

In 5-card draw poker, a player receives an initial hand of 5 cards, and is then allowed to replace up to three of her cards with the remaining cards in the deck. (b) Suppose that, among the initial 5 ...
1
vote
0answers
57 views

EXERCISE 2.7.2 fron Alon and Spencer probabilistic method.

Prove that there is a positive constant $c$ so that every set $A$ of $n$ nonzero reals contains a subset $B\subset A$ of size $|B| > cn$ so that there are no $b_{1},b_{2},b_{3},b_{4}\in B$ ...
3
votes
1answer
86 views

Expected Value of this function

Let’s consider a random permutation p1, p2, …, pN of numbers 1, 2, …, N and Function F is calculated as F=(X[2]+…+X[N-1])^K, where ...
7
votes
0answers
163 views

Cramér's Model - “The Prime Numbers and Their Distribution”

I was reading "The Prime Numbers and Their Distribution" by Gérald Tenenbaum and Michel Mendès France, the section about Cramér's Model, and I couldn't prove a couple of results. I would like to start ...
0
votes
0answers
21 views

uniform spanning tree of $2 \times n$ graph

In Probability on Trees and Networks Chapter 1 study the uniform spanning tree on the ladder graph: _ |_| |_| |_| ... |_| |_| The probability the bottom rung ...
3
votes
1answer
29 views

Can you prove this recursive multiple $n$-sided dice throwing statement?

Let $W_{s,r,n}$ be the total number of ways that the sum $s$ can be displayed after throwing $r$ number of $n$-sided dice. Define $$W_{s,0,n} = \begin{cases} 1, & \text{if s = 0} \\ 0, & ...
2
votes
0answers
79 views

Fast check If the remainder is 1

Is there any fast method to 'say' that $R = (A \mod B)$ is $1$ or $R > 1$ or $R \neq1$ or $R > k>1$ ( where $k$ is a small integer on $32$ bits) without to actually calculate the real value ...
9
votes
3answers
411 views

Prove the lecturer is a liar…

I was given this puzzle: At the end of the seminar, the lecturer waited outside to greet the attendees. The first three seen leaving were all women. The lecturer noted " assuming the attendees are ...
4
votes
1answer
90 views

relative size of most factors of semiprimes, close?

when chatting about RSA a cohort just asserted something like "most prime factors of semiprimes are roughly the same size" measured in bits. ie "bits" is the number of digits in the base2 ...
4
votes
6answers
597 views

Find the number of positive integers whose digits add up to 42

Find the number of positive integers $$n <9,999,999 $$ for which the sum of the digits in n equals 42. Can anyone give me any hints on how to solve this?
1
vote
3answers
97 views

Probability on divisibility

Let S be the set of all 12-digit positive integers each of whose digits is either 1 or 4 or 7 (for example, 477411171747 is a member of S). What is the probability that a randomly picked member of S ...
1
vote
1answer
602 views

A pair of unbaiased dice are rolled together till a sum of either 5 or 7 is obtained. Then find the probability that 5 comes before 7..

Problem : A pair of unbaiased dice are rolled together till a sum of either 5 or 7 is obtained. Then find the probability that 5 comes before 7.. My approach : Probability of getting 5 ( let it ...
0
votes
0answers
64 views

Out of (2n+1) tickets consecutively numbered, three are drawn at random, the probability that the numbers on them are in A.P…

Problem : Out of (2n+1) tickets consecutively numbered, three are drawn at random, the probability that the numbers on them are in A.P. (a) $\frac{3n}{4n^2-1}$ (b) $\frac{2n}{4n^2-1}$ (c) ...
0
votes
1answer
103 views

Number of ways of arranging numbers with given max difference

How many ways are the there to arrange n numbers out of m numbers (1 to m) so that the difference between the max and min numbers of those n numbers is D which is given. For example : n = 4 m = 3 ...
7
votes
1answer
172 views

To what extent are divisibility by different primes independent?

Let's prove: the probability that two randomly chosen integers are relatively prime is $ \frac{6}{\pi^2} $. and a "proof" by separating relative prime-ness into a product of indendent events ...
0
votes
1answer
29 views

Congruential Generators.

Find all of the cycles of the following congruential generators. For each cycle identify which seeds $X_0$ lead to that cycle. $$(a). X_{n+1} = 9X_n + 3\mod 11$$ $$(b). X_{n+1} = 8X_n + 3\mod 11$$ ...
0
votes
1answer
84 views

Application of Bayes' theorem - probability problem Suppose that the reliability of a HIV test is specified as follows : Of people having HIV, …

Bayes' Theorem States : *If $E_1,E_2,....E_n$ are n non empty evnents which constitute a partition of sample space S, ie.e. $E_1,E_2,....E_n$ are pairwise disjoint and $E_1 \cup E_2 ......\cup E_n$ = ...
0
votes
0answers
27 views

How to choose the longest run of trials?

Supposing we are given $n$ cyclic Bernoulli trials trial with $p=1/2$ where we know the the outcome of each trial. Cyclic in the sense that the trials restart with the same corresponding outcome after ...
0
votes
0answers
52 views

order of magnitude of first moment of prime's distribution?

I have these this question in mind for a while and struggling with. Question: Is it possible to define a first moment (mean) of the distribution of the primes' infinite sequence? And if this can be ...
-2
votes
1answer
66 views

Birthday paradox- valid from 23 people and why not for 22 people ?

My question is why birthday paradox is applicable for 23 people's group and why not for 22 people group. Request you to please guide on this .. I will be greatful to you. Thanks..
11
votes
2answers
497 views

Are primes randomly distributed?

There is a famous citation that says "It is evident that the primes are randomly distributed but, unfortunately, we don't know what 'random' means." R. C. Vaughan (February 1990) I have this very ...
3
votes
2answers
152 views

Zeta function and probability

I know that $\zeta(n) = \displaystyle\sum_{k=1}^\infty \frac{1}{k^n}$ (Where $\zeta(n)$ is the Riemann zeta function) But the reciprocal of $\zeta(n)$ for $n$ a positive integer is equal to the ...
3
votes
0answers
83 views

A challenging problem on prime uncertainty interval

I have a very challenging problem to solve, seeking for good advice; I have to make an intro in the first part and then comming to the problem. Theorem (1): In an interval between a prime $p$ and its ...
4
votes
1answer
90 views

Distribution of Digit Products

A digit product $P(n)$ of a natural number $n$ is given by the product of its decimal digits. For example: $$P(1234) = 24,\;\;\; P(24) = 8,\;\;\; P(8) = 8$$ $$1\times2\times3\times4 = 24, \;\;\; ...
0
votes
1answer
147 views

Probability of two random n-digit numbers dividing each other

Let $n$ be a positive integer. Suppose $a$ and $b$ are randomly (and independently) chosen two $n$-digit positive integers which consist of digits 1, 2, 3, ..., 9. (So in particular neither $a$ nor ...
0
votes
1answer
125 views

Problems with votes [closed]

Can someone help me with this problem? I think that it is something with the Dirichlet. Suppose that a group of voters is to elect a mayor. There are $a$ voters that intend to vote for candidate A, ...
0
votes
0answers
72 views

Probability that two Gaussian integers are divisible

Let $z = x+ iy \in \mathbb{Z}[i]$ and let $a+ib \in \mathbb{Z}[i]$ with $a^2 + b^2 \equiv 1 \mod{4}$. What is the probability that $a+ib$ divides $x + iy$ in $\mathbb{Z}[i]$? This question would ...
1
vote
0answers
56 views

If $x \sim U(Z_n^*)$ then $x^2(mod \; n) \sim U(QR_n)$?

Define: $Z_n^*=\{x \in Z_n | gcd(x,n)=1\}$ $QR_n=\{x \in Z_n | \exists r \in Z_n \; s.t. \; r^2 =x\}$ How can I show that $x \sim U(Z_n^*) \implies x^2(mod \; n) \sim U(QR_n)$? Thank you.
2
votes
1answer
59 views

How big is $Z_n^*$?

I would like to find some upper bound on $\frac{n}{|Z_n^*|}$ i.e. to show that many of the elements in $Z_n$ are also in $Z_n^*$. I want to show that $\frac{n}{|Z_n^*|}=O(log^cn)$ for some $c \in N$. ...
2
votes
2answers
90 views

Behaviour of congruential generator

Define $X_{n+1} = (aX_n + c) \bmod m$ where $a$ is chosen uniformly at random from $\{1,\dots, m-1\}$ and $c$ is chosen uniformly at random from $\{0,\dots, m-1\}$ and $m$ is a fixed prime. Take ...
1
vote
1answer
64 views

probability of a number not having factors below n?

I want to know the probability that a number is not divisible by any prime smaller than or equal to n. ie, I find a big number, I trial division it up to 300000 and don't find any factors. I want to ...
4
votes
1answer
136 views

Are these numbers $h_{r,s}$ irrational?

I came across these numbers in my work some time ago. This type of expressions do not exist in closed form (not to confuse with Vandermonde convolution), I already know that. To simplify I denote ...
3
votes
1answer
181 views

The prime numbers do not satisfies Benford's law

A set of numbers is said to satisfy Benford's law if the leading digit d (d ∈ {1, ..., 9}) occurs with probability, $$ P(d)=\log_{10}(d+1)-\log_{10}d,$$ how do you prove that the prime numbers do ...
7
votes
1answer
214 views

How to calculate probability of these two pair-of-sums ($S_{n}$ and $T_{n}$) and ($SEvenF_{n}$ and $SOddF_{n}$) being the same?

Say we have a sequence of $n$ positive integers, we can assume they're randomly chosen, let's call it $U_{n}$. Let $S_{n}$ = sum of $U_{n}$ from $1$ to $n$. Let $T_{n}$ = sum of $n$ from $1$ to $n$. ...
1
vote
1answer
161 views

Can you determine a formula for this problem?

Given: A list of integers is there.Now there are 2 buckets -bucket A and bucket B.This step is repeated as long as there are numbers left in the list.Integers from start or end of the list are ...
1
vote
3answers
113 views

Which numbers have digits that are random or nearly so?

I was told that the digits of $\pi$ are random (or at least nearly so). Would $\pi$/2 etc. also have that property? Which other numbers have that property? In case there are a vast number of them, do ...
0
votes
1answer
77 views

How to find out the probability of ordered pairs of rational or irrational number $(a,b)$ such that $1<a<50, 1,<b<50$, and $\log_b a$ is rational.

How to find out the probability of ordered pairs of rational or irrational or transcendental number $(a,b)$ such that $1<a<50$, $1<b<50$, and $\log_b a$ is rational? Uniformly ...
0
votes
2answers
148 views

A number theory question about a “double infimum”

Let $x_1,x_2,x_3,\ldots,x_S$ be numbers with $x_i>-1$ for all $i$ and $x_k<0$ for some $k$. How can one show that \begin{equation} \inf_{s\in[1,S]}\inf_{t\in[1,s]}\prod_{i=t}^s ...
5
votes
1answer
161 views

P[random x is composite | $2^{x-1}$ mod $x = 1$ ]?

Select a uniformly random integer $n$ between $2^{1024}$ and $2^{1025}$ (Q) What is the probability that n is composite given that $2^{n-1}$ mod $n = 1$ ? How did you calculate this? More info: ...
7
votes
3answers
191 views

Generating random numbers with the distribution of the primes

I would like to generate random numbers whose distribution mimics that of the primes. So the number of generated random numbers less than $n$ should grow like $n / \log n$, most intervals ...
4
votes
1answer
126 views

Probabilistic Sieve of Eratosthenes

Consider the following algorithm: ...
2
votes
2answers
555 views

“Probability” of a large integer being prime

Someone once told me (rather testily) that we cannot speak of the "probability that a number is prime" because the sequence is deterministic. I think I understood his point but would like to make ...
3
votes
2answers
124 views

Why is the probability that a prime p is a factor of a number n equal to 1/p

I'm learning some number theory and I can't seem to understand why this is the case.
3
votes
1answer
166 views

Dixon's random squares algorithm: a step in the proof of its subexp. running time

I am currently working to understand Dixon's running time proof of his subexp integer factorization algorithm (random squares). But unfortunately I can not follow him at a certain point in his work. ...
0
votes
2answers
53 views

Lower bound on a function of probability distribution

Let $$ \gamma = \frac{1}{\sum_{y}f(y)W(y)}, $$ where $$ f(y) = 1 + e^{-|y|} $$ and $W(y)$ is a probability distribution (unknown) with $y \in \mathcal{Y}$ arbitrary but discrete, and $x \in ...
14
votes
1answer
276 views

Density of odd numbers in a sequence relating base 2 and base 3 expansion

Define the function $$f(4n)=6n+1\\ f(4n+1)=6n+2\\ f(4n+2)=6n+3\\ f(4n+3)=6n+5$$ and the sequence $u_0=2$, $u_{k+1}=f(u_k)$. Let $d_1\le d_2$ be the lower and upper asymptotic density of odd numbers ...
0
votes
1answer
50 views

A pdf on power of two having as mean a power of two

Given $k$, find $n \in N$ and $p_i$ such that $$\sum_{i=0}^n p_i 2^i = 2^k$$ $$\sum_{i=0}^n p_i = 1$$ $$0<p_i<1$$
1
vote
1answer
128 views

A probabilistic method

I am trying to study for a exam and i found a assignmet, that i cant solve. Consider a board of $n$ x $n$ cells, where $n = 2k, k≥2$. Each of the numbers from $S = \{1,...,\frac{n^2}{2}\}$ is written ...
6
votes
1answer
186 views

When is the sum of first $n$ numbers equal to the sum of the next $k$ numbers?

When is the sum $1+2+\cdots + n = (n+1) + (n+2) + \cdots +(n+k)$? The easiest solution $(n,k)$ is $(2,1)$. For example, $1+2 = 3$. Do any others exist? Roots of $(n+k)^2 + (n+k) = 2n^2 +2n$ give ...
1
vote
0answers
125 views

expectation of vector

Let vector $c\in 2N $ is such that first $m$ of its coordinates are $1$ and the rest are $0$ ($c=(1,\ldots, 1,0, \ldots, 0)$). Let $\pi$ be $k$-th permutation of set $\{1, \ldots, 2N\}$. Define ...