Saturday, February 16, 2019

Why does this pattern occur when using modular arithmetic against set of prime numbers?



I have been recently playing around with number theory and going through the project Euler problems. So I am very new to a lot of these things. I apologize for not knowing how to look up my answer. This is kinda a two part question I think.



First I created a list of prime numbers from 1 to ten million. Then I looped through this list up to about 350,000. In this loop I created a variable X for the prime number I was on, then another variable y for the for X + primeList[x]. each time I did this I calculated y mod x and saved that into a new list. I graphed that and got a strange pattern that I'm sure has to do with some basic concept of modular arithmetic that I just don't understand. I have included the screen shot of my graph below.



My python code:




for x in range(1,100000):
start = primeList[x]
mod = primeList[x+primeList[x]]
result = mod % start
primeModList.append(result)


As the second part of my question. I tried creating a pseudorandom list of numbers to kind of simulate the distributions of primes (I do understand this does not really work, but not sure of any other way to do it). I ran that same list through the same process and did not achieve the same results. Although if I increased my randomList[value] by the primeList numbers I did achieve the same result.




My code for this was:



for x in xrange(10000000):
n = randint(0,10000000)
randomList.append(n)

randomList.sort()

for x in range(1,100000):
start = randomList[x]

mod = randomList[x+randomList[x]]
result = mod % start
ranModList.append(result)


To reiterate I want to know why this pattern shows, and what major difference causes it to only show when increasing by number in my prime list and not my random list.



My graph of the prime number set in blue, and my set of my remainders in green.


Answer



Let $p_n$ be the $n$'th prime, and let $y_n = p_{n + p_{n}} \mod p_n$, i.e.

$p_{n+p_{n}} = x_n p_n + y_n$ where $0 \le y_n < p_n$ and $x_n = \lfloor p_{n+p_n}/p_n \rfloor$. Now the point is that
$r_n = p_{n+p_n}/p_n$ will tend to grow, but
slowly: $p_n \sim n \log n$, $p_{n+p_n} \sim (n + p_n) \log(n + p_n) \sim n (\log n)^2$, so $r_n \sim \log n$. $x_n = \lfloor r_n \rfloor$ will typically be constant for long intervals. For example, it is $12$ for
$3070 \le n \le 7073$. On an interval where $x_n = c$, $y_n = (r_n - c) p_n$
will tend to be increasing, from near $0$ at the beginning of the interval to near $p_n$ at the end.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...