# Tagged Questions

27 views

### Probability,Number Theory

Given $p_k<(2m/n)^{-ck^2}$, $m\geq n$ and $k \in Z$ then prove that $\sum_{|k|>0} p_k < \frac{n}{cm}$ for large values of $c$.
55 views

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

Following a previous question (here you'll find an introduction): A paper by Maier which refutes Cramer's Model suggests we should replace the heuristic "$\Bbb P(n\in\mathcal P)=1/\log n$" with ...
25 views

93 views

### why generating function $A(z) = 1 + z + z^2 + \cdots$ can be denoted as $\frac{1}{1-z}$

It is easy to see that $1 + z + z^2 + \cdots$ is equal to $\frac{1}{1-z}$ when $1 > z > 0$ and for $z >= 1$, they are not equivalent. So I have thought $\frac{1}{1-z}$ is just a short for the ...
27 views

### Probabilty and number theory

If two distinct numbers m and n are chosen at random from the set $\{1, 2, 3, \ldots 100\}$, then the probability that $2^m+2^n+1$ is divisible by $3$ is $p$. Find the value of $\lfloor1/p\rfloor$. A ...
383 views

### Game of cards and GCD

Alice and Bob play the game. The rules are as follows: Initially, there are n cards on the table, each card has a positive integer written on it. At the beginning Alice writes down the number 0 on ...
63 views

### Digits of $n$ factorial

With the notable exception of $0$, for large enough $n$, the digits in base $10$ for $n!$ seem pretty much uniformly distributed (I have also checked for other few bases $> 2$). Have anyone ...
187 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 ...
84 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$ ...
92 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 ...
238 views

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

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 ...
32 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 ...
35 views

153 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 ...
133 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, ...
77 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.
61 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 ...
164 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 ...
209 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 ...
216 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$. ...
171 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 ...
118 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 ...
79 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 ...
150 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 ...
### 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: ...
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 ...