Waste less time on Facebook — follow Brilliant.
×

CHALLENGE! Computer Science

I have given all computer science genii a challenge. It is so impossible it is possible. You have to write codes that can do the following things:

(a) Be able to print the Riemann zeta function of any number.

(b) Be able to print off the first 10000 primes without using the Sieve of Eratosthenes

(c) (extension) Be able to print numbers in exact values for (a). e.g. \(\pi/6\)

You can write in any language. Special prize for the winner, which will be said after the challenge has been completed.

Note by Sharky Kesa
2 years, 9 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Challenge (b) in python.

1
2
3
4
5
6
7
8
9
# Technically I didnt use a sieve  :P
import urllib
Primes = []
sock = urllib.urlopen("http://primes.utm.edu/lists/small/10000.txt")
for line in sock.read().split('\n')[4:-2]:
    Primes += map(int,line.split())
sock.close()
for prime in Primes:
    print prime

EDIT

Here is a straight forward way of generating primes without a sieve.For each \(N\),check if any of the primes \(< \sqrt{N}\) you previously generated divide it. If they do not,then it is a prime and you can add it to the list of primes and print it out.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
from math import sqrt

def Gen_Primes(Limit):
    Primes = [2 , 3]
    N , Count = Primes[::-1]
    for i in Primes:yield i
    while Count < Limit:
        N += 2
        Is_PP , Root = True , sqrt(N)
        for prime in Primes:
            if prime > Root:
                break
            if N % prime ==0:
                Is_PP=False
                break
        if Is_PP:
            Primes.append(N)
            Count += 1
            yield N

for p in Gen_Primes(10**5):
    print p

Another way of solving this problem is by going through each number and then use a very fast primality testing algorithm such as Miller Rabin to check for primality.

In Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import java.math.BigInteger;

public class main {
  public static void main(String[] args) {
      int limit = 100000;
      int count = 1;
      System.out.println(2);
      BigInteger N = new BigInteger("1");
      BigInteger Two = new BigInteger("2");
      while (count < limit){
          N = N.add(Two);
          if  (N.isProbablePrime(10)){
              count += 1;
              System.out.println(N);
          }
      }
  }
}
Thaddeus Abiy · 2 years, 9 months ago

Log in to reply

@Thaddeus Abiy Nice. Sharky Kesa · 2 years, 9 months ago

Log in to reply

@Thaddeus Abiy when internet is down, try to print with it.. :D Ranadeep Biswas · 2 years, 9 months ago

Log in to reply

@Ranadeep Biswas ur right..was a bit lazy..Ive added more Thaddeus Abiy · 2 years, 9 months ago

Log in to reply

Printing first 10000 primes -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import math

def yieldPrime(n):
    li = []
    num = 2
    while(n):
        for p in li:
            if(p > int(math.sqrt(num))+1):
                li.append(num)
                yield num
                n -= 1
                break
            elif(num % p == 0):
                break
        else:
            li.append(num)
            yield num
            n -= 1
        num += 1

for i in yieldPrime(10000):
    print(i)
Ranadeep Biswas · 2 years, 9 months ago

Log in to reply

For (a), Im using JavaScript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
var zeta;  
var natural = 1;  
function Riemann(s) {  
  zeta = 1/(Math.pow(natural,s));  

  for (var i=0; i<1E+7; i++) {  
    natural++;  
    zeta = zeta + 1/(Math.pow(natural,s));   
  }  
  return zeta;  
}  
alert(Riemann(2));

Im not very good at JavaScript, so, this may not be the most efficient way to calculate the required value, but this does give an approximation for the Riemann Zeta of a number Anish Puthuraya · 2 years, 9 months ago

Log in to reply

@Anish Puthuraya Look at this. Thaddeus Abiy · 2 years, 9 months ago

Log in to reply

@Thaddeus Abiy Thanks a lot...I have edited the comment using the method suggested there... Anish Puthuraya · 2 years, 9 months ago

Log in to reply

@Anish Puthuraya Run the code on the console of any browser, or just make a HTML file that links to the javascript file which contains the above code.. Anish Puthuraya · 2 years, 9 months ago

Log in to reply

\[ Code for a) & b) \]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from math import *

def nCr(n, r):
    return factorial(n) // factorial(r) // factorial(n-r) # Integer only division '//'

def getPartialPrimesUpto(n, start=2):
    return [
        m for m in range(start, n) # 2 -> n
            if all(m % o != 0 for o in range(2, int(sqrt(m))+1))  # Check if all of 2 -> sqrt(m)+1 are not factor of m
        ]

primesList = [2]
def getPrimesUpto(n): # Saves time on continuously calculating primes
    if primesList[-1] < n:
        primesList.extend(getPartialPrimesUpto(n, primesList[-1]+1))
    return primesList[:n]

def RiemannZetaUsingSeries(s, maxTerms=12):
    y = 1/(s-1)
    s1 = 0
    for n in range(0, maxTerms):
        s2 = 0
        for k in range(0, n+1):
            s2 += pow(-1, k) * pow(1+k, 1-s) * nCr(n, k)
        s1 += s2/(n+1)
    y *= s1
    return y

def RiemannZetaUsingEulerProduct(s, maxPrimes=9999):
    primes = getPrimesUpto(maxPrimes)
    y = 1
    for k in range(0, len(primes)):
        y *= 1/(1-primes[k]**-s)
    return y

def RiemannZeta(s, precision=10000):
    if s == 1:
        return "Infinity"
    y = 0
    if s < 1:
        y = RiemannZetaUsingSeries(s)
    else:
        y = RiemannZetaUsingEulerProduct(s)
    y = floor(y*precision)/precision
    return y
1
print(getPrimesUpto(10000 )) # Will print 10000 primes
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
print(RiemannZeta(s))
# Output for some values
# At s = 0    Zeta(s) =  -0.5
# At s = 0.5  Zeta(s) =  -1.4675
# At s = 2    Zeta(s) =  1.6449
# At s = 3    Zeta(s) =  1.202
# At s = 4    Zeta(s) =  1.0823
# At s = -1   Zeta(s) =  -0.0834
# At s = 1.5  Zeta(s) =  2.6076
# At s = -5   Zeta(s) =  -0.004
# At s = -4   Zeta(s) =  0.0
# At s = -3   Zeta(s) =  0.0083
# At s = -2   Zeta(s) =  0.0
Code 0987 · 2 years, 9 months ago

Log in to reply

(a), (b) and (c) using Mathematica (and I think I could solve them using Sage too).

Anyway, do not take this solution into consideration (as if you would), because it is ridiculously unfair with who is using Python, C, C#, Java, Haskell, ... to solve it.

a[n_] := N[Zeta[n]];

b := Map[Prime, Range[1, 10000]];

c[n_] := Zeta[n];
Bernardo Sulzbach · 2 years, 9 months ago

Log in to reply

Minor typo - in (c) it has to be \(\pi^2/6\) Bogdan Simeonov · 2 years, 9 months ago

Log in to reply

@Bogdan Simeonov Well, it is an example, not the zeta function answer. Sharky Kesa · 2 years, 9 months ago

Log in to reply

@Sharky Kesa For instance,

\[\zeta{\left(-19.9960230838937361197456702051425768393\right)}\approx{}\frac{\pi{}}{6}\] Bernardo Sulzbach · 2 years, 9 months ago

Log in to reply

What does problem (c) mean? Daniel Lim · 2 years, 9 months ago

Log in to reply

@Daniel Lim Read it again, I edited it. Sharky Kesa · 2 years, 9 months ago

Log in to reply

@Sharky Kesa extension means web extension? Daniel Lim · 2 years, 9 months ago

Log in to reply

@Daniel Lim No, as in it is in a higher order of difficulty. Sharky Kesa · 2 years, 9 months ago

Log in to reply

@Sharky Kesa ok, how about exact forms? Daniel Lim · 2 years, 9 months ago

Log in to reply

@Daniel Lim Their exact values. Sharky Kesa · 2 years, 9 months ago

Log in to reply

@Sharky Kesa how many significant digits? Daniel Lim · 2 years, 9 months ago

Log in to reply

@Daniel Lim When I said exact values, if it has infinite digits like \(\pi\), it shows it as the string value assigned to pi. If it has lots o digits, give it in the form of an equation. Sharky Kesa · 2 years, 9 months ago

Log in to reply

@Sharky Kesa Wolfram Alpha.

Imgur

Imgur

Daniel Liu · 2 years, 9 months ago

Log in to reply

@Daniel Liu :P Sharky Kesa · 2 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...