Riemann Series Theorem

Question

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

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.

Answer 1

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"

Answer 2

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)

Answer 3

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.