# Alternating sum

A frog is at the bottom of a 30 metre well. Each day it climbs 5 metres up the side, but it then slips back 3 metres each night. How long does it take to reach the top of the well?

Is there an easier /more direct way to make an alternating sum than this?

y = 14; Flatten[Transpose[{Table[2 x + 5, {x, 0, y - 1}],
Table[2 x, {x, 1, y}]}]]


# Update

Not automated, but simple and more direct than first attempt:

Accumulate[Table[If[OddQ[n], 5, -3], {n, 1, 27}]]

• This problem will make some of our most active users very happy, +1. – Leonid Shifrin Mar 23 '14 at 9:26
• If you're just looking for a compact and efficient way to get the partial sum list (per your update), Array[2-2(-1)^#+#&,27] is the way to go... – ciao Mar 23 '14 at 23:59

Not sure whether this is simpler, but it more directly follows the problem, and you don't have to compute the number of iterations in advance:

Rest[
NestWhileList[{First@# + If[EvenQ[Last@#], 5, -3], Last@# + 1} &, {0, 0}, First@# < 30 &]
][[All, 1]]

(*
{5, 2, 7, 4, 9, 6, 11, 8, 13, 10, 15, 12, 17, 14, 19, 16, 21,
18, 23, 20, 25, 22, 27, 24, 29, 26, 31}
*)


Here, each iteration produces a list of two elements, where the first one is the total distance climbed so far, and the last one is simply the number of the step. When the top is reached, iteration stops.

A more readable form of this code would be:

ClearAll[nextStep];
nextStep[{distance_, index_?EvenQ}] := {distance + 5, index + 1};
nextStep[{distance_, index_?OddQ}] := {distance - 3, index + 1};


and then

Rest[NestWhileList[nextStep, {0, 0}, First@# < 30 &]][[All, 1]]

• A nice solution :) Still trying to get to grips with @ and # - think this simple code may help me on my way. Also, I think NestWhileList is what I was probably searching for here :) – martin Mar 23 '14 at 9:45
• @martin Well, you can use Last[#], First[#], etc, instead of the prefix form, if it is more readable for you - the user of @ is a purely stylistic matter. – Leonid Shifrin Mar 23 '14 at 9:47
• I see that [[All]] is short form of Part too :) – martin Mar 23 '14 at 9:48
• @martin Well, [[All,index]] is a compact and fast way to extract a given column from a nested list. See also my edit for a more readable version of this code. – Leonid Shifrin Mar 23 '14 at 9:51

Using a recurrence equation :-

height = -30;
slip = 3;
climb = 5;

sol = RSolve[{a[n + 1] == a[n] - slip + climb,
a == height + slip}, a, n]


{{a -> Function[{n}, -27 + 2 n]}}

f = First[a /. sol];
n = 0; While[f[n] < 0, ++n]
Print["Frog reaches the top on day ", n]


Frog reaches the top on day 14

• neat and the answers with days not steps +1 :) – ubpdqn Mar 23 '14 at 12:53
• It looks pedestrian, but this is a very readable solution. :) – J. M. will be back soon May 9 '15 at 15:02

Just for fun and a little ugly:

f[x_, c_] := {x + (3 + 2 Mod[c, 2]) (-1)^(Mod[c, 2] + 1), c + 1}
ans = NestWhileList[f @@ # &, {-30, 1}, First@# < 0 &];


The number of steps is Length@ans-1. Visualizing: This was animated gif made from:

{pos, steps} = Transpose[ans];
ListPlot[pos[[1 ;; #1]], Epilog -> Inset[Framed[#2], {5, -10}],
PlotRange -> {{0, Length@pos + 1}, {-35, 2}}, Joined -> True,
ImageSize -> 300, BaseStyle -> 20] &, {Range[2, Length@pos],
Most@steps}];

froggy[wellHeight_Integer] := Switch[EvenQ[wellHeight], True, wellHeight - 3, False,
wellHeight - 4];

(* 30 Meter well *)
froggy

(* 27 *)


I will wager this is the highest performing solution ;-}

An actual tailorable method:

up = 5;
down = 3;
height = 30;
moves = 0;

While[Sum[Boole[OddQ[x]] up - Boole[EvenQ[x]] down, {x, 1, moves}] <height, moves++];

moves

(* 27 *)


A neat and concise way to get the steps is via a linear recurrence (indexed to zero move):

LinearRecurrence[{1, 1, -1}, {0, 5, 2}, 28]

(* {0, 5, 2, 7, 4, 9, 6, 11, 8, 13, 10, 15, 12, 17, 14, 19, 16, 21, 18, 23, 20,
25, 22, 27, 24, 29, 26, 31} *)

• A very concise solution! Struggling with Switch though ... where does the -4 come from? – martin Mar 23 '14 at 10:02
• @martin: I am just goofing with L.S. et al, the constants are derived from your particular example, so if height is even integer, it takes heght-3 moves, if odd, height-4 moves. I'll add a "real" alternative that is responsive to the question. – ciao Mar 23 '14 at 10:10
• @martin: syntax & semantics of Switch can be found in the docs: basically, do a test (the EvenQ part in my case), followed with a series of value pairs, first that matches test result means next is the result value. Also, note the site you're on: any frog here is smart enough to wait for some heavy rain and float out sans any effort :P – ciao Mar 23 '14 at 10:17

Quite obviously the frog will reach the top while on a 5-meter-up move. It is the easier to assume that it first goes down 3 meters and then up 5 meters, for a total of 2 meters up.

Now, starting from -30, go up 5 to -25 (day 1) and then repeat the above (-3+5=2) steps. The number of days is thus

$1+\lceil 25/2 \rceil = 14$

(sorry, no Mathematica!)

• Why floor? $13\frac{1}{2}$ is correct (so reaches the top on the 14th day). – martin Mar 23 '14 at 23:22
• @Martin you are correct, error fixed. – A.G. Mar 23 '14 at 23:56

Just in the spirit of fun I post this as another: just a variant.

res=NestWhileList[Function[{x,j},{1+4 Cos[Pi j]+ x,j+1}]@@#&,{-30,0},First@#<0&]


As before the number of steps is Length@res-1 and number of days Ceiling[Length@res/2-1/2].

• Nice - shows step numbers! :) – martin Mar 23 '14 at 16:44