Subscribe via feed.

## 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.

Tags:
This post is under “Tom” and has 13 respond so far.

### 13 Responds so far- Add one»

1. 1. Wizard of Oz Said：

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.

2. 2. luv2fap Said：

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.*

3. 3. nonrobuster Said：

but he only offered you a 6 week contract….

4. 4. Chris Said：

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

5. 5. Chris Said：

Hi luv2fap. Taking your examples to override the words, it is obvious that on working day n that you’d get \$106n or \$(2n -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.

6. 6. cazayoux Said：

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 ????

7. 7. cazayoux Said：

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.

8. 8. JB Said：

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

9. 9. John24 Said：

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.

10. 10. Chris Said：

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.

11. 11. xXxVatchXxX Said：

its just

2u(n-1)+1

u(however many days cause idk)*.01

12. 12. Chris Said：

Working in cents, the total pay to day n (inclusive) is An = 2n+1 -(n+2).

The iterator is An+1 = 2An +n +1

On 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”.

13. 13. cazayoux Said：

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

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0