## Recessive recursion

Posted by luv2fap on April 26, 2011 – 11:14 pm

An incredibly wealthy man offers you a 6 week job contract with his company. Being a generous man he also gives you choice as to how you will be paid: You can either get 1 million dollars each working day (Monday-Friday) for the entire 6 months OR he can start by paying you 1c on the first day and every working day after that doubles the previous number and adds it to your previous days pay. For example: day1 = 1c, day2 = (2+1)c, day3 = (4+3)c, day 5 = (8+7)c day6 = (16+15)c ….etc for the entire 6 month period. Define a recursive formula for the latter oayment method and work out how much more money you’d get if you chose the second option.

April 27th, 2011 at 12:05 am

At a million a day for 6 months of weekdays I get $1m x 5 x 26 = $130,000,000.

This would be about equal to a Wall St banker’s annual salary.

Being paid the other way I get 1c on day 1, 3c on day 2, 7c on day 3, and so on. If we add ic a day to this series we get 2 + 4 + 8 + … + 2^130

= 2(1 + 2 + 4 + 8 + … + 2^129) = 2(2^130 – 1)

= 2.72 x 10^39 cents less the 130 cents we added to make the power series.

= 2.72 x 10^37 dollars

This would be about the total wealth of all the Arab oil sheikhs in the Middle East, plus a bit over.

Definitely I should take the second option.

April 27th, 2011 at 12:17 am

Hmm you’ve definitely got the right order of magnitude. Why did you double the 2^(130-1)? I get 1.36E39 when I use excel. Also, there’s a very elegant recursive formula that defines this payment method see if you can get it.

*Bonus points if you can write a ‘for’ loop which will calculate your payment after n days.*

April 27th, 2011 at 12:49 am

but he only offered you a 6 week contract….

April 27th, 2011 at 4:20 am

Hi luv2fap. You started with 6 weeks, then said 6 months.

April 27th, 2011 at 4:46 am

Hi luv2fap. Taking your examples to override the words, it is obvious that on working day n that you’d get $10

^{6}n or $(2^{n}-1)/100, where I’ve assumed that you accidentally said day 5 instead of day 4 etc.That cannot be solved for n. Even the break-even critical point equation cannot be solved for n, so number crunching is required, just as you requested.

I’ve gotta go.

April 27th, 2011 at 7:47 am

Still unclear. The samples given in the problem definition skips day 4. I’m not clear on the formula.

If f[day n] = N, then f[day n+1] = 2n + N ????

April 27th, 2011 at 8:31 am

If f[day n] = 2^(n-1) + f(day n-1) = (2^n – 1)/100

SUM(all days up to n) = 2*f[n] – n/100

= 2* [(2^n - 1)/100] – n/100

= (2^(n+1) – 2 – n) / 100

and we compare this to 1,000,000n.

At day 30 (last day of 6 weeks)

$30,000,000 > $21,474,836.16

At day 31

$31,000,000 < $42,949,672.95

For a 6 week job, I'll take the $1m/day.

For anything longer, I'll take method 2 of payment.

April 27th, 2011 at 8:54 am

For luv2fap ,if you want the ‘for’ loop here’s a simple VBA macro for Excel:

Option Explicit

Dim rt As Double ‘running total

Dim d As Integer ‘day number

Dim da As Double ‘day (doubling) amount

Dim dp As Double ‘day’s pay

Dim n As Integer ‘number of days

Sub Calculate_Pay()

‘ Number of days must be entered in cell E1

n = Range(“E1″).Value

Columns(“A:D”).ClearContents

Range(“A1″).Value = “Day Number”

Range(“B1″).Value = “Double Amount”

Range(“C1″).Value = “Day’s Pay”

Range(“D1″).Value = “Running Total”

dp = 0

rt = 0

da = 0.01

For d = 1 To n

Range(“A” & d + 1).Value = d

Range(“B” & d + 1).Value = da

Range(“C” & d + 1).Value = dp + da

dp = dp + da

rt = rt + dp

da = da * 2

Range(“D” & d + 1).Value = rt

Next

End Sub

April 27th, 2011 at 4:22 pm

Let n be the number of days you will get paid.

Total pay = 2^(n-1) + 2^(n-1)-1

This works for any value n > 1. Day 1 evaluates to 1.5 and not 1.

if n=3

2^(3-1) + 2^(3-1) – 1 =

4 + 2 – 1 = 5

if n=4

2^(4-1) + 2^(4-1) – 1 =

8 + 8 – 1 = 15

if n=5

2^(5-1) + 2^(5-1) – 1 =

16 + 16 – 1 = 7

this can be written as

2 * 2^(n-1) – 1

and further written as

2^n – 1

6 Weeks of pay at 1 million per weekday = $30 million

6 Weeks of pay at 1 cent per day doubling each day and adding to previous day’s pay = 2^30 – 1 = 1,073,741,824 pennies or 10,737,418.24 for the last day.

Recursive Formula (sorry don’t know how to do superscripts or subscripts)

A1 = 1

An = A(n-1) + 2^(n – 1)

Solve for n = 2

A2 = A1 + 2^(2 – 1) = 1 + 2 = 3

Solve for n = 3

A3 = A2 + 2^(3-1) = 3 + 4 = 7

Solve for n = 4

A4 = A3 + 2^(4-1) = 7 + 8 = 15

This gives each days pay only and therefore needs a method to total all previous day’s pay along with the current day’s pay. I get a bit stuck here and not sure how to get a total pay of $.26 through day 4 (1 + 3 + 7 + 15).

I believe this could be written in a Summation where it is the Sum of 2^n – 1 where n starts at 1 and ends with the number of days. Sorry don’t know how to do greek Sigma symbols either.

Perhaps one of you gurus could rewrite my post.

April 27th, 2011 at 5:00 pm

For special symbols, charmap is a good start. I keep a lot in a notepad file.

°º¹²³ⁿ αβγδΔεζηθξρσφλμπωΣΩΓ»«☺♠♣♥♦●•∙♪♫ћ√→∞≈≠≡≤≥‖│± ´ ∂‼∫⇄⇋∛∷ ¼ ½ ¾ ⅓ ⅔ ⅛ ⅜ ⅝ ⅞ ₁ ₂ ₃ ₄□■¬

Also MS Reference Sans Serif 9 point regular seems to be a good match to the font used on this site. I do a lot of my editing in notepad and have a ruler in there to get the width and layout right.

April 27th, 2011 at 6:44 pm

its just

2u(n-1)+1

u(however many days cause idk)*.01

April 27th, 2011 at 8:27 pm

Working in cents, the total pay to day n (inclusive) is A

_{n}= 2^{n+1}-(n+2).The iterator is A

_{n+1}= 2A_{n}+n +1On that basis, at end of day 30 he will have earnt $21,474,836.16 (or $30,000,000) and at the end of day 31 he will have earnt $42,949,672.63 (or $31,000,000). As the song says, “what a difference a day makes”.

April 28th, 2011 at 9:15 am

I agree with Chris and think my formula for sum-up-to-day-n is correct. However, I had wrong totals.

The formula results match Chris’ results.

f[day n] = 2^(n-1) + f(day n-1) = (2^n – 1)/100

SUM(all days up to n)

= 2*f[n] – n/100

= 2* [(2^n - 1)/100] – n/100

= (2^(n+1) – 2 – n) / 100