6
\$\begingroup\$

The Riemann series theorem states that the terms of a conditionally convergent series can be permutated such that the resulting series converges to an arbitrary value.

The Challenge

Write a program or function that takes in three parameters via stdin (or equivalent) or as parameters:

  • The expression for the sequence x_n (with variable n). The exact format (e.g., whether a power is represented as ^, pow() or **) is irrelevant and may be chosen to fit your language. Alternatively you may pass a function directly as an argument. The definition of the function does not count towards the byte count.
  • A value S that we want to approach. Numerical values only are fine, you don't need to support mathematical expressions.
  • A threshold t>0. Numerical values only are fine here as well.

Your program/function must output (to stdout or equivalent) resp. return a space- or newline-separated list p_1, ..., p_N of indices.

Your output must satisfy the condition that the sum from k = 1..N over x_(p_k) differs from S no more than t in terms of the absolute difference. In other words, it must satisfy

| sum(1..N, x_(p_k)) - S | <= t

So far, since the output will be a finite number of indices, the order would not matter. Therefore, another restriction applies: with decreasing threshold t, you may only add indices to the output (assuming a fixed S).

In other words, for a fixed S, if t_1 < t_2 and [x_1, ..., x_N] is a solution for t_2, then a solution for t_1 must be of the form [x_1, ..., x_N, ..., x_M] with M >= N.

Details and Restrictions

  • The order of the arguments may be changed to suit your needs.
  • Provide an example call with the arguments from the example below. Ideally, post a link to an online interpreter/compiler.
  • eval and the like are explicitly allowed for the purpose of evaluating mathematical expressions.
  • Sequences are 1-based, so the first index is 1.
  • You don't need to take special care of big integers or floating point problems. There will be no extreme test cases such as using machine precision as the threshold.
  • Standard loopholes apply.
  • You may assume that the sequence passed to your program is conditionally convergent, i.e. that it is possible to solve the task with the given parameters.

Example

Say your program is in a file riemann.ext, then a call might be

./riemann.ext "(-1)^(n+1)/n" 0.3465 0.1

Scoring

This is code-golf. The shortest program in bytes (UTF-8 encoding) wins. In case of a tie, the earlier entry wins.

\$\endgroup\$
37
  • 1
    \$\begingroup\$ Why would you penalize answers for supporting expressions? :P \$\endgroup\$
    – Dennis
    Oct 10, 2014 at 5:20
  • \$\begingroup\$ @Dennis score in code golf is the code length. You want to minimize the score. \$\endgroup\$ Oct 10, 2014 at 5:22
  • \$\begingroup\$ @JanDvorak: Right, and subtracting -10 adds 10. \$\endgroup\$
    – Dennis
    Oct 10, 2014 at 5:23
  • \$\begingroup\$ I shall change the wording. ;) edit: done. \$\endgroup\$
    – Ingo Bürk
    Oct 10, 2014 at 5:24
  • \$\begingroup\$ Is it okay if we require such implementation crud in x_n as Javascript's Math.pow or Haskell's fromInteger for sequences that involve manipulating integers? (as in, assume the expression is eval-ready no matter how non-pseudocodey it is) \$\endgroup\$ Oct 10, 2014 at 5:33

3 Answers 3

4
\$\begingroup\$

Haskell, 161 158 144

because Haskell can deal with infinite lists, instead of doing the parsing stuff this solution receives an infinite list as the sequence.

r l s t=unwords[show$[i+1|i<-[0..],l!!i==x]!!0|x<-s%filter(>0)l$filter(<0)l]where(g%j@(p:o))y@(n:b)|abs g<t=[]|g<0=n:((g-n)%j)b|0<1=p:((g-p)%o)y

example output:

*Main> let harm = zipWith (*) (cycle [1,-1]) (map (1/) [1..]) -- the alternating harmonic numbers
*Main> r harm 3 0.001
"1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 2 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 193 195 197 199 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 303 305 307"
\$\endgroup\$
13
  • \$\begingroup\$ Damn it. And I thought my 162-character solution was kinda decent... \$\endgroup\$ Oct 10, 2014 at 9:25
  • \$\begingroup\$ @JanDvorak was yours in Haskell too? \$\endgroup\$ Oct 10, 2014 at 9:26
  • \$\begingroup\$ It was... I'm not done golfing, but don't think I can beat you. \$\endgroup\$ Oct 10, 2014 at 9:27
  • \$\begingroup\$ I think I'm going to steal something... \$\endgroup\$ Oct 10, 2014 at 9:28
  • \$\begingroup\$ @JanDvorak what is it that you are going to steal? \$\endgroup\$ Oct 10, 2014 at 9:28
3
\$\begingroup\$

Haskell, 206 characters

import Data.List
r t e f=unwords.map(show.snd)$(\(x,y:_)->x++[y])$span(\(s,_)->abs(t-s)>e)$m 0$partition(<(0,0))$zip f[1..] where m s(a@((b,c):d),w@((x,y):z))|s<t=(x+s,y):m(x+s)(a,z)|1>0=(b+s,c):m(b+s)(d,w)

The sequence itself is an implicit last argument. Usage:

r 2 0.001 [(-1)**(n+1) / n | n <- [1..]]

Beaten before even having been posted, but - oh well. Posted anyways. I also took the liberty of accepting an infinite list as my first argument.

readable version:

import Data.List
import Debug.Trace
riemannConverge :: (Integral ix, Num v, Ord v, Show ix, Show v) => (ix -> v) -> v -> v -> String
riemannConverge target maxError series = 
    unwords $
    map (show . \(_,ix) -> ix) $
    (\(xs,y:_) -> xs++[y]) $
    span (\(s,_) -> abs (target - s) > maxError) $
    map (\x -> traceShow x x) $
    mergeNP 0 $
    partition (\(x,_) -> x<0) $
    zip series [1..]
  where
    mergeNP s (nss@((nVal,nIx):ns), pss@((pVal,pIx):ps))
     | s < target = (pVal + s, pIx) : mergeNP (pVal + s) (nss,ps)
     | otherwise  = (nVal + s, nIx) : mergeNP (nVal + s) (ns,pss)
\$\endgroup\$
6
  • \$\begingroup\$ Unfortunately I don't know Haskell. Does this print the list of indices? Just asking since the other Haskell solution doesn't. \$\endgroup\$
    – Ingo Bürk
    Oct 10, 2014 at 14:14
  • \$\begingroup\$ It does. That's what the map snd $ ... $ zipWith [1..] is for. \$\endgroup\$ Oct 10, 2014 at 14:15
  • \$\begingroup\$ Do you require a string instead of a list of numbers? \$\endgroup\$ Oct 10, 2014 at 14:16
  • \$\begingroup\$ If Haskell automatically prints a list of numbers in the correct format (space or newline separated) without further modification then it's okay. \$\endgroup\$
    – Ingo Bürk
    Oct 10, 2014 at 14:34
  • \$\begingroup\$ @IngoBürk GHCi produces a comma-separated list. Buh oh well... here we go. \$\endgroup\$ Oct 10, 2014 at 14:37
1
\$\begingroup\$

Python – 88

def R(x,S,t):
 I=[0,0]
 while abs(S)>t:
    i=I[S>0]=I[S>0]+1
    if x(i)*S>0:S-=x(i);print i,

I stores the indices for positive and negative numbers and to reduce the number of variables, I do not sum up to 0 until I reach S, but subtract from S until I reach 0.

I am not entirely sure whether this complies with the restrictions on the input.

The used algorithm should be very nice for a stack-based language.

\$\endgroup\$
3
  • \$\begingroup\$ So, this adds positive number until it reaches S and then adds negatives until it reaches 0 again? I'm afraid that this doesn't follow the spec \$\endgroup\$ Oct 10, 2014 at 15:26
  • \$\begingroup\$ @proudhaskeller: No. If we forget about the subtraction trick, it either A) adds positive elements until the sum is larger than S B) adds negative elements until the sum is smaller than S. It alternatingly repeats those steps until the sum is sufficiently close to S. The subtraction trick is that instead of going from 0 to S by summation, I go from S to 0. \$\endgroup\$
    – Wrzlprmft
    Oct 10, 2014 at 15:34
  • \$\begingroup\$ oh I see. I should be able to use in my code. thanks. \$\endgroup\$ Oct 10, 2014 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.