×

# 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 ago

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); } } } } 
· 3 years ago

Nice. · 3 years ago

when internet is down, try to print with it.. :D · 3 years ago

ur right..was a bit lazy..Ive added more · 3 years 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) 
· 3 years 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 · 3 years ago

Look at this. · 3 years ago

Thanks a lot...I have edited the comment using the method suggested there... · 3 years 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.. · 3 years 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 = [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 
· 3 years 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];

· 3 years ago

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

Well, it is an example, not the zeta function answer. · 3 years ago

For instance,

$\zeta{\left(-19.9960230838937361197456702051425768393\right)}\approx{}\frac{\pi{}}{6}$ · 3 years ago

What does problem (c) mean? · 3 years ago

Read it again, I edited it. · 3 years ago

extension means web extension? · 3 years ago

No, as in it is in a higher order of difficulty. · 3 years ago

ok, how about exact forms? · 3 years ago

Their exact values. · 3 years ago

how many significant digits? · 3 years 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. · 3 years ago

Wolfram Alpha.

Imgur

· 3 years ago