# Tagged Questions

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 ...
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$ ...
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 ...
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 ...
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 ...
29 views

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 ...
125 views

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, ...
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 ...
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.
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$. ...
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 ...
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 ...
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 ...
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 ...
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$. ...
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 ...
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 ...
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 ...
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 \inf_{s\in[1,S]}\inf_{t\in[1,s]}\prod_{i=t}^s ...
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: ...
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 ...
126 views

### Probabilistic Sieve of Eratosthenes

Consider the following algorithm: ...
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 ...
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.