Tagged Questions
0
votes
1answer
78 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
49 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
45 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
51 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$. ...
1
vote
2answers
86 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
35 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 ...
2
votes
1answer
102 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
140 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
197 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
151 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
108 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
55 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
140 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
123 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
167 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
110 views
0
votes
2answers
235 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
103 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
128 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
45 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
206 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
49 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
104 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
178 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
118 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
...
0
votes
2answers
313 views
Probability of an even sum
In a set of numbers there are 5 even numbers and 4 odd numbers. If two numbers are chosen at random from the set, without replacement, what is the probability that the sum of these two numbers is ...
2
votes
0answers
99 views
sum of probability
I am having trouble of calculating the following probability:
Let $\epsilon_i$, $i=1,\dotsc,N$ be Rademacher random variables. Let $n_i\in \{0, 1, 2, \dotsc, 2M\}$, $i=1,\dotsc,N$ such that ...
2
votes
1answer
83 views
maybe generating function?
A question asking for the number of ways of choosing $2A$ numbers from $\{0,1,..,2B\}$ with a sum of $2C$ can be answered with the help of generating function
$$
...
2
votes
2answers
195 views
Probability of two events
I am having trouble of calculating the following probability:
Let $\epsilon_i$, $i=1,\dotsc,N$ be Rademacher random variables. Let $n_i\in \{0, 1, 2, \dotsc, M\}$, $i=1,\dotsc,N$ such that ...
2
votes
1answer
336 views
Conditional expectation of product of Bernoulli random variables
Let $\epsilon_1,\ldots,\epsilon_m$ be Bernoulli random variables, i.e. $P(\epsilon_i=1)=P(\epsilon_i=-1)=\frac 12$.
I wanted to calculate (or at least approximate) the following conditional ...
0
votes
1answer
229 views
Relationship between Kronecker's Approximation Thm and Weyl's Equidistribution Thm?
According to Prof. Wikipedia, the Equidistribution Theorem was proved by Weyl in 1910 and independently by two others around the same time.
The theorem states that for $\alpha$ irrational, the ...
0
votes
1answer
298 views
How to arranged two or more different colored blocks in all possible ways?
Is any algorythem that can arrange two or more different blocks in all possible ways.. in series (rows and columns.)?
If I have two colored(red and blue) blocks and I try to arranged in one possible ...
2
votes
1answer
225 views
Number of primes less than 2n
A series of questions. Explanations would be useful. I have done the first four parts. I am confused on how to go about the last two.
Show that for any prime $p$ the largest power of $p$ that ...
0
votes
1answer
70 views
A simple case of Linear Diophantine equations in with probability application
Suppose $1\le x \le k, 1\le y \le k$, and we need to find a explicit formula for the the number of integers solution for the equation such that $$x+y=z$$ where $z \in\{2,...,2k\}$
I'm doing this ...
4
votes
3answers
485 views
How to approach number guessing game(with a twist) algorithm?
I posted this on stackoverflow, but was advised to also post here. It's kind of a math/algo question so I think it's kind of stuck between both worlds of math and computer science. I believe this to ...
0
votes
1answer
150 views
Is the average of many “random” numbers useful information?
Ok, so I found this site: http://tweetcracker.com/. Essentially, people just tweet 10 digit numbers in hopes it is the correct number (like lottery, except free).
I heard that if you took all the ...
6
votes
1answer
109 views
Dixon's Theorem to probabilistically bound largest factor of N
I have recently decided to read up on the current integer factorization algorithms. When looking into some of the algorithms, I came across the following statement:
Say that p is the smallest ...
5
votes
1answer
454 views
What is the probability of randomly selecting $ n $ natural numbers, all pairwise coprime?
It's known that the probability of selecting $ n $ natural numbers randomly and ending up with a greatest common divisor equal to one is $ \prod (1-p^{-n}) = 1/\zeta(n) $. However, a total GCD of 1 ...
5
votes
2answers
187 views
Given $2$ randomly chosen integers $x,y$ what is $P(k=gcd(x,y))$?
Given $2$ randomly chosen integers $x,y$ what is the probability that a integer $k$ is the greatest common divisor of $x$ and $y$?
I know that the probability of $x,y$ being coprime is ...
6
votes
3answers
411 views
On the probability that two positive integers are relatively prime
In many of the sources I have consulted about this, the "probability" that two positive integers chosen at random are relatively prime is calculated as the limit as $n \to \infty$ of the probability ...
19
votes
3answers
220 views
Probability distribution for the remainder of a fixed integer
In the "Notes" section of Modern Computer Algebra by Joachim Von Zur Gathen, there is a quick throwaway remark that says:
Dirichlet also proves the fact, surprising at first sight, that for fixed ...
7
votes
4answers
329 views
Calculating the median in the St. Petersburg paradox
I am studying a recreational probability problem (which from the comments here I discovered it has a name and long history). One way to address the paradox created by the problem is to study the ...
3
votes
1answer
61 views
number-theoretic? probabilities associated with $e^{-n}$ and $1/\Gamma(n)$
I was thinking about the fact that $\frac{1}{\zeta(n)}$ is the probability that $n$ randomly chosen integers are coprime, and wondered if there were “natural” ways in which $e^{-n}$ (for ...
1
vote
2answers
231 views
Probability of being B smooth
Given an integer N and a smooth base B; what is the (approximate) probability that N is completely divisible by primes <= B.
I assume there is some nice connection to the de Bruijn or Dickman ...
1
vote
1answer
158 views
Probability to pick “1” from a list of infinite disistnct integers
Lets say we construct a list as follows.
It has f(n) 1's, and f(2) 2's and f(3) number of three's in it etc.
Let L(n,f) be this list, so if f(n)=n^2 we get L(3,n^2)=(1,2,2,2,2,3,3,3,3,3,3,3,3,3)
If ...
3
votes
1answer
172 views
Snakes and Probabilistic Enigma
Assume that there are n snakes. Any 2 ends (tail or head) of the "2n" available have to be picked up and tied together and this process has to be repeated infinitely.
If p/q (gcd(p,q) = 1) is the ...
5
votes
1answer
329 views
Ulam spiral: Is there an “unusual amount of clumping” in prime-rich quadratic polynomials?
I was reading Martin Gardner's Mathematical Games column on the Ulam spiral which appeared in the March 1964 issue of Scientific American. (The spiral actually featured on the cover of that issue.) ...
7
votes
2answers
621 views
Probability of cumulative dice rolls hitting a number
Is there a general formula to determine the probability of unbounded, cumulative dice rolls hitting a specified number?
For Example, with a D6 and 14:
5 + 2 + 3 + 4 = 14 : success
1 + 1 + 1 + 6 + ...
2
votes
1answer
183 views
For an arbitrary positive integer d and random modulus m, what is the probability that d mod m = 0?
More specifically, assume d taken from [1, 2^n] and m is taken from [1, n]. What is an upper bound on the probability that d is a multiple of m?
10
votes
1answer
517 views
What's the probability that a sum of dice is prime?
Prompted by today's Minute Math question on the MAA site (http://amc.maa.org/mathclub/5-0,problems/T-problems/T-web,ia/2005web/tb05-12-ia.shtml), I started thinking about the probability that the sum ...
