# HG changeset patch
# User Felix Geller
# Date 1312042300 -7200
# Node ID 0cfe9a686d3ab985fd6a076c7636f92b1c842d8a
# Parent b0e1b6b1d95364cc9cccc35fba384f4317cc5e1c
Programming praxis exercise 2011-07-29
diff --git a/ProgrammingPraxisExercises.ns3 b/ProgrammingPraxisExercises.ns3
new file mode 100644
--- /dev/null
+++ b/ProgrammingPraxisExercises.ns3
@@ -0,0 +1,82 @@
+Newspeak3
+'Programming-Praxis'
+class ProgrammingPraxisExercises usingPlatform: pf = (|
+ ArrayList = pf collections OrderedCollection.
+|)
+(
+class Exercise20110729 = (
+"
+In the two previous exercises we have seen three different methods for computing the prime-counting function n(n), all based on a formula of Legendre. We have also seen the difficulty of the calculation, as three eminent mathematicians got their sums wrong, and the difficulty continues even today with the use of computers, as Xavier Gourdon had to stop an attempt to compute n(10**23) because of an error. Given the difficulty of calculation, in some cases it might make sense to calculate an approximate value of n, instead of an exact value. In today's exercise we look at two methods for approximating the prime-counting function.
+
+The first method dates to the German mathematician Carl Friedrich Gauss, who gives an estimate n(x) ~ Li(x), the logarithmic integral--this is the celebrated prime number theorem, which Gauss figured out when he was fifteen years old! The logarithmic integral can be calculated by expanding the infinite series
+
+Li(x) = Int_0_x(dt/log_e(t)) = gamma + log(log(x)) + Sum_k=1_inf((log(x))**k)/k! k)
+
+to the desired degree of accuracy; somewhere around a hundred terms ought to be sufficient for arguments up to 1012. Beware the singularity at x=0.
+
+In 1859, Bernhard Riemann, whose hypothesis about the prime numbers is one of the greatest open questions in mathematics, described a different, and much more accurate, approximation to the prime counting function:
+
+R(x) = Sum_n=1_inf((mu(n)/n * Li(x**1/n))
+
+where mu(n) is the Möbius function that takes the value 1 when n is 1, 0 when the factorization of n contains a duplicated factor, and (-1)k, where k is the number of factors in the factorization of n, otherwise. There is no better way to compute the Möbius function than to compute the factors of n. As with the logarithmic integral, about a hundred terms of the infinite series ought to be sufficient to get a good approximation for arguments up to 1012.
+
+Your task is to write functions to compute the logarithmic integral, the Möbius function, and Riemann's R function, and to compare the results to the values you calculated for the prime-counting function in the previous exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
+"|
+ gamma = 0.57721566490153286061.
+ upLimit = 100.
+|)
+('as yet unclassified'
+Li: x = (
+| sum = Sum from: 1 to: upLimit add: [ :k | (x ln ** k) / ((factorialOf: k) * k)]. |
+ ^ (gamma + x ln ln + sum compute) rounded.
+)
+R: x = (
+ ^ (Sum from: 1 to: upLimit add: [ :n | (mu: n) / n * (Li: ( x raisedTo: (1 / n))) ])
+ compute floor.
+)
+factorialOf: x = (
+| factorial = 1. |
+ 1 to: x do: [ :i | factorial:: factorial * i ].
+ ^ factorial
+)
+factorsOf: n = (
+| primes = primesUntil: n.
+ factors = ArrayList new.
+ tempFactor= n. |
+ primes do: [ :p |
+ [ (tempFactor \\ p) = 0 ] whileTrue: [
+ factors add: p.
+ tempFactor:: tempFactor / p ]].
+ ^ factors
+)
+mu: x = (
+| factors |
+ x = 1 ifTrue: [ ^ 1 ].
+ factors:: factorsOf: x.
+ factors do: [ :of | (factors select: [ :if | if = of ]) size > 1
+ ifTrue: [ ^ 0 ]].
+ ^ -1 ** factors size.
+)
+primesUntil: n = ( "Sieve of Eratosthenes"
+| ints = ArrayList newWithSize: n.
+ p = 2. |
+ 2 to: n do: [ :i | ints at: i put: i ].
+ [ p * p <= n ] whileTrue: [ | mark = p * p. |
+ [ mark <= n ] whileTrue: [
+ ints at: mark put: nil.
+ mark:: mark + p. ].
+ p:: ints detect: [ :ea | ea ~=nil and: [ ea > p ]] ifNone: [ n + 1]].
+ ^ ints select: [ :x | x ~= nil ].
+))
+class Sum from: s to: e add: cls <[]> = (|
+ start = s.
+ end = e.
+ closure = cls.
+|)
+('as yet unclassified'
+compute = (
+| tempResult = 0. |
+ start to: end do: [ :n |
+ tempResult:: tempResult + (closure value: n) ].
+ ^ tempResult
+)))
\ No newline at end of file
diff --git a/ProgrammingPraxisTests.ns3 b/ProgrammingPraxisTests.ns3
new file mode 100644
--- /dev/null
+++ b/ProgrammingPraxisTests.ns3
@@ -0,0 +1,77 @@
+Newspeak3
+'Programming-Praxis'
+class ProgrammingPraxisTests usingPlatform: pf testFramework: tf = NewspeakObject (|
+ TestContext = tf TestContext.
+
+ excercises = pf ProgrammingPraxisExercises usingPlatform: pf.
+ E20110729 = excercises Exercise20110729.
+|)
+(
+class Exercise20110729 = TestContext (|
+ e = E20110729 new.
+|)
+('as yet unclassified'
+testFac = (
+ assert: 6 = (e factorialOf: 3).
+)
+testFactorsOf = (
+| fs10 = e factorsOf: 10.
+ fs20 = e factorsOf: 20.
+ fs100 = e factorsOf: 100. |
+ assert: fs10 size = 2.
+ assert: fs20 size = 3.
+ assert: fs100 size = 4.
+)
+testLi = (
+| li10 = e Li: 10.
+ li20 = e Li: 20. |
+ assert: li10 < 7.
+ assert: li10 > 5.
+ assert: li20 < 11.
+ assert: li20 > 9.
+)
+testLiR = (
+| li10v3 = e Li: 1000.
+ li10v6 = e Li: 1000000.
+ li10v9 = e Li: 1000000000.
+ li10v12 = e Li: 1000000000000.
+ r10v3 = e R: 1000.
+ r10v6 = e R: 1000000.
+ r10v9 = e R: 1000000000.
+ r10v12 = e R: 1000000000000. |
+ assert: li10v3 = 178.
+ assert: li10v6 = 78628.
+ assert: li10v9 = 50849235.
+ assert: li10v12 = 37607950281.
+ assert: r10v3 = 168.
+ assert: r10v6 = 78527.
+ assert: r10v9 = 50847455.
+ assert: r10v12 = 37607910542.
+)
+testMu = (
+| one = e mu: 1.
+ seven = e mu: 7.
+ ten = e mu: 10.
+ twenty = e mu: 20. |
+ assert: 1 = one.
+ assert: -1 = seven.
+ assert: 1 = ten.
+ assert: 0 = twenty.
+)
+testPrimesUntil = (
+| p10 = e primesUntil: 10.
+ p20 = e primesUntil: 20.
+ p100 = e primesUntil: 100. |
+ assert: 4 = p10 size.
+ assert: 8 = p20 size.
+ assert: 25 = p100 size.
+)
+testR = (
+| r10 = e R: 10.
+ r20 = e R: 20. |
+ assert: r10 = 4.
+ assert: r20 = 7.
+)) : ('as yet unclassified'
+TEST_CONTEXT = (
+
+)))
\ No newline at end of file
diff --git a/ProgrammingPraxisTestsConfigurations.ns3 b/ProgrammingPraxisTestsConfigurations.ns3
new file mode 100644
--- /dev/null
+++ b/ProgrammingPraxisTestsConfigurations.ns3
@@ -0,0 +1,6 @@
+Newspeak3
+'Programming-Praxis'
+class ProgrammingPraxisTestsConfigurations packageTestsUsing: ns = NewspeakObject (|
+ ProgrammingPraxisTests = ns ProgrammingPraxisTests.
+|)
+()
\ No newline at end of file