0
votes
0answers
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$.
3
votes
0answers
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 ...
1
vote
0answers
25 views

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

Following a previous question (here you'll find an introduction): The book states that almost surely $$\pi_S(x+y)-\pi_S(x)=\mathrm{li}(x+y)-\mathrm{li}(x)+O(\sqrt y)$$ as soon as $y/(\log ...
2
votes
0answers
40 views

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

Following a previous question (here you'll find an introduction): The book states that using the convergence of the binomial distribution towards the Poisson distribution, it's easy to show that ...
3
votes
1answer
76 views

Probability that two random integers have only one prime factor in common

The probability that two integers picked at random are relatively prime is known to be $1/\zeta{(2)}=6/\pi^2\approx0.607927...$. Generalizing, the probability that $n$ random integers have $\gcd=1$ is ...
-1
votes
1answer
48 views

Probability that the sum of visible faces is $72$?

$5$ dice are stacked one over the other to make a column. $4$ faces of each of the first $4$ dice are visible while $5$ faces of the topmost die is visible. What is the probability that the sum of ...
3
votes
0answers
90 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, ...
3
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
2answers
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 ...
1
vote
0answers
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$ ...
3
votes
1answer
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 ...
9
votes
0answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
35 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
81 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 ...
10
votes
3answers
586 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 ...
5
votes
1answer
101 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
786 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
106 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
796 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
92 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
139 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
199 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
30 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
112 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 ...
-2
votes
1answer
74 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
613 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
183 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
86 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
91 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
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 ...
0
votes
1answer
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, ...
0
votes
0answers
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 ...
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
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$. ...
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 ...
5
votes
1answer
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 ...
3
votes
1answer
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 ...
7
votes
1answer
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$. ...
1
vote
1answer
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 ...
1
vote
3answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 \begin{equation} \inf_{s\in[1,S]}\inf_{t\in[1,s]}\prod_{i=t}^s ...
5
votes
1answer
162 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
196 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 ...