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

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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}$

Sort by:

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); } } } } 

- 6 years, 2 months ago

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

- 6 years, 2 months ago

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

- 6 years, 2 months ago

Nice.

- 6 years, 2 months ago

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

- 6 years, 2 months ago

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..

- 6 years, 2 months ago

Look at this.

- 6 years, 2 months ago

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

- 6 years, 2 months ago

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) 

- 6 years, 2 months ago

What does problem (c) mean?

- 6 years, 3 months ago

Read it again, I edited it.

- 6 years, 3 months ago

extension means web extension?

- 6 years, 3 months ago

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

- 6 years, 3 months ago

- 6 years, 3 months ago

Their exact values.

- 6 years, 3 months ago

how many significant digits?

- 6 years, 3 months ago

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.

- 6 years, 3 months ago

Wolfram Alpha. Imgur

- 6 years, 3 months ago

:P

- 6 years, 3 months ago

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

- 6 years, 2 months ago

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

- 6 years, 2 months ago

For instance,

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

- 6 years, 2 months ago

(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];


- 6 years, 2 months ago

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 =  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 

- 6 years, 2 months ago