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
3 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

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 - 3 years, 5 months ago

Log in to reply

Nice.

Sharky Kesa - 3 years, 5 months ago

Log in to reply

when internet is down, try to print with it.. :D

Ranadeep Biswas - 3 years, 5 months ago

Log in to reply

ur right..was a bit lazy..Ive added more

Thaddeus Abiy - 3 years, 5 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 - 3 years, 5 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 - 3 years, 5 months ago

Log in to reply

Look at this.

Thaddeus Abiy - 3 years, 5 months ago

Log in to reply

Thanks a lot...I have edited the comment using the method suggested there...

Anish Puthuraya - 3 years, 5 months ago

Log in to reply

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 - 3 years, 5 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 - 3 years, 5 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 - 3 years, 5 months ago

Log in to reply

Minor typo - in (c) it has to be \(\pi^2/6\)

Bogdan Simeonov - 3 years, 5 months ago

Log in to reply

Well, it is an example, not the zeta function answer.

Sharky Kesa - 3 years, 5 months ago

Log in to reply

For instance,

\[\zeta{\left(-19.9960230838937361197456702051425768393\right)}\approx{}\frac{\pi{}}{6}\]

Bernardo Sulzbach - 3 years, 5 months ago

Log in to reply

What does problem (c) mean?

Daniel Lim - 3 years, 5 months ago

Log in to reply

Read it again, I edited it.

Sharky Kesa - 3 years, 5 months ago

Log in to reply

extension means web extension?

Daniel Lim - 3 years, 5 months ago

Log in to reply

@Daniel Lim No, as in it is in a higher order of difficulty.

Sharky Kesa - 3 years, 5 months ago

Log in to reply

@Sharky Kesa ok, how about exact forms?

Daniel Lim - 3 years, 5 months ago

Log in to reply

@Daniel Lim Their exact values.

Sharky Kesa - 3 years, 5 months ago

Log in to reply

@Sharky Kesa how many significant digits?

Daniel Lim - 3 years, 5 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 - 3 years, 5 months ago

Log in to reply

@Sharky Kesa Wolfram Alpha.

Imgur

Imgur

Daniel Liu - 3 years, 5 months ago

Log in to reply

@Daniel Liu :P

Sharky Kesa - 3 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...