n = 2 ∑ 2 0 1 6 k = 0 ∑ n j = 0 ∑ ϕ ( n ) + 1 ⎝ ⎛ ( k n ) ( ϕ ( n ) + 1 ) ! ( − 1 ) n + k ( n + k ) j ⎠ ⎞ = ?
For your final step of your calculation, you may refer to this list of prime numbers .
Notations :
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
I did a similar thing a while back, just that for the prime-testing-function I used
P ( x ) = ( k = 1 ∑ x g cd ( x , k ) ) − ( 2 x )
G ( x ) = ( − 2 x − 1 . 8 ∣ x + 0 . 9 − ∣ x + 0 . 9 ∣ ∣ + 2 x + 1 . 1 ⋅ 2 ∣ − x − 1 . 1 − ∣ − x − 1 . 1 ∣ ∣ − 1 )
P r i m e ( x ) = G ( P ( x ) )
Log in to reply
Poon, this triple-sum posed in this problem is probably about the worst prime-counting function that could be devised. But let me admit that I was first particularly fascinated with the curious properties of this sum
k = 0 ∑ n ( ( n k ) ( − 1 ) n + k ( k + 1 ) j ) = 0 , if 0 ≤ j < n , n ! , if j = n , for all integer n > 0
that I later decided to make use of to create this ridiculous prime-counting triple-sum. Maybe some people had fun with this, but maybe no so much with others.
So far, most of the prime-testing, or prime-counting, or prime-generating functions that I have seen, (unlike your example?), make use of floor or ceiling functions. As a matter of fact, this equally ridiculous prime-generating function
also makes use of such floor functions, expressed in complex form. Click
this
for a better view.
Problem Loading...
Note Loading...
Set Loading...
Relevant wiki: Prime counting function
This triple sum counts up the number of prime numbers up to 2 0 1 6 , which works out to 3 0 5 .
First, we start with the statement, which will be proven later
k = 0 ∑ n ( ( n k ) ( − 1 ) n + k ( m + k ) j ) = 0 , if 0 ≤ j < n , n ! , if j = n , for all integer n , m > 0
from which we can state, letting m = n arbitrarily
j = 0 ∑ q k = 0 ∑ n ( ( n k ) ( − 1 ) n + k ( n + k ) j ) = 0 , if 0 ≤ q < n , n ! , if q = n
again from which we can state, reversing order of summation and dividing by n !
k = 0 ∑ n j = 0 ∑ q ( ( n k ) n ! ( − 1 ) n + k ( n + k ) j ) = 0 , if 0 ≤ q < n , 1 , if q = n
Now from number theory (at least not yet proven otherwise)
ϕ ( n ) + 1 = n
only if n is prime, otherwise
ϕ ( n ) + 1 < n
so that from above, we can state
k = 0 ∑ n j = 0 ∑ ϕ ( n ) + 1 ( ( n k ) ( ϕ ( n ) + 1 ) ! ( − 1 ) n + k ( n + k ) j ) = 0 , if n = not prime, 1 , if n = prime
from which we can do the third and final summation
n = 2 ∑ x k = 0 ∑ n j = 0 ∑ ϕ ( n ) + 1 ( ( n k ) ( ϕ ( n ) + 1 ) ! ( − 1 ) n + k ( n + k ) j ) = π ( x )
where π ( x ) is the Prime Counting function, which counts the number of primes equal to x or less. Hardly the most efficient formula as a Prime Counting function, but it still works as one.
Additional notes:
If you are still wondering about
k = 0 ∑ n ( ( n k ) ( − 1 ) n + k ( m + k ) j ) = 0 , if 0 ≤ j < n , n ! , if j = n , for all integer n , m > 0
restate it as follows
k = 0 ∑ n ( ( n k ) ( − 1 ) n + k i = 0 ∑ j ( ( j i ) ( m − 1 ) i ( k + 1 ) j − i ) ) = 0 , if 0 ≤ j < n , n ! , if j = n , for all integer n , m > 0 or, reversing order of sum
i = 0 ∑ j ( ( j i ) ( m − 1 ) i k = 0 ∑ n ( ( n k ) ( − 1 ) n + k ( k + 1 ) j − i ) ) = 0 , if 0 ≤ j < n , n ! , if j = n , for all integer n , m > 0
which holds true for all integer n , m > 0 if
k = 0 ∑ n ( ( n k ) ( − 1 ) n + k ( k + 1 ) j ) = 0 , if 0 ≤ j < n , n ! , if j = n , for all integer n > 0
This can be restated as
k = 0 ∑ n ( ( n k ) ( − 1 ) n + k ( k + 1 ) ( k + 1 ) j − 1 ) = 0 , if 0 ≤ j < n , n ! , if j = n
and since
k = 0 ∑ n ( ( n k ) ( − 1 ) n + k ( 1 ) ( k + 1 ) j − 1 ) = 0 , if 1 ≤ j < n , n ! , if j = n
we have, after the difference is divided by n (with k = 0 yielding the trivial value of 0 )
k = 1 ∑ n ( ( n k ) ( − 1 ) n + k ( n k ) ( k + 1 ) j − 1 ) = 0 , if 1 ≤ j < n , n ! , if j = n
or
k = 1 ∑ n ( ( n − 1 k − 1 ) ( − 1 ) n + k ( k + 1 ) j − 1 ) = 0 , if 1 ≤ j < n , n ! , if j = n
which is back to where we were, but with n decreased by 1
k = 0 ∑ n ( ( n k ) ( − 1 ) n + k ( k + 1 ) j ) = 0 , if 0 ≤ j < n , n ! , if j = n , for all integer n > 0
Through induction, we reach the trivial case where n = 1 and compute the values directly for j = 0 and j = 1 .
k = 0 ∑ 1 ( ( n k ) ( − 1 ) n + k ( k + 1 ) j ) = 0 , for j = 0 , and 1 , for j = 1 .
The proof in more correct form should start at the bottom and through induction prove for all n > 0 by taking the steps in reverse order.