5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ primeList[n] is the $n$th prime, that we usually write $p_n$ ? and your primeModList is $r_n = p_{n+p_n} \bmod p_n$ ? then the distribution of $p_k \bmod p_n$ for $k > n$ is really not trivial, and I doubt $k = n+p_n$ yield such a nice (green) graph. $\endgroup$ – reuns Jul 7 '16 at 19:17
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ overall you say that his green plot $y_n = p_n \{p_{n+p_n} / p_n\} $ is $\approx (n \log n)\{(n \log^2 n) / (n \log n)\} \approx (n \log n)\{ \log n\}$ $\endgroup$ – reuns Jul 7 '16 at 20:19
0
$\begingroup$

As far as your second question goes, I don't believe prime numbers are randomly distributed. For example, for primes greater than 2, a prime number can only be odd. Further, since every 3rd odd number is divisible by 3, the only potential primes are of the form $6k±1$, for $k\in\mathbb N$ (for primes greater than 3). Perhaps prime numbers are randomly distributed among those candidates, but not among the natural numbers themselves.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.