Hitting 137

[bonanova]

If I repeatedly throw a fair 6-sided die, what is the probability that the running total will at one point equal 137?

[bushindo]

If I repeatedly throw a fair 6-sided die, what is the probability that the running total will at one point equal 137?

With some recursive code, I get

0.2857143

[CaptainEd]

2 / 7

Edited January 14, 2013 by CaptainEd

[Prime]

It seems to stand the reason...

Since with each roll we add with equal probability between 1 and 6 to the running sum, the average step is 3.5. Then the probability would be 1/3.5 just like Bushindo calculated.

I'll try for exact formula later.

[BobbyGo]

I got an anwer of 0.2536043somethingsomethingmorenumbers

[bonanova]

Bushindo has seven decimal places; the Captain has it exactly, if surprisingly; and Prime has the insight.

A triple tag team solution! Good job all. So who gets the "solved" tag .... ?

The nod goes to Prime's explanation.

[Prime]

Thanks Bonanova. My explanation does look sound. But now, after I have taken some time to reflect, I must disprove and disown my solution.

Sure, the fraction that we found here is good for everyday gambling needs, but it is not the exact probability.

I suspect, Bushindo’s method would have produced the exact answer, had it not succumbed to rounding error.

Any number may or may not be an intermediate running total in this experiment. But there is one exception - zero! Zero running total will occur with 100% probability right before the very first roll.

Consequently, the probabilities for the first six numbers (1, 2, 3, 4, 5, and 6) to become intermediate totals are:
P₁= 1/6;
P₂= (1+1/6)/6 = 7/6²;
P₃ = (1+1/6+7/6²)/6 = 7²/6³;
And in the like manner,
P₄= 7³/6⁴;
P₅ = 7⁴/6⁵;
P₆ = 7⁵/6⁶;
Note, all the above probabilities are different from 2/7. First four are smaller, and the last two are higher.

From that point on we must change the method for probability calculation. Since a running total n can be obtained by a single roll from 6 preceding totals,
P_n = (P_n-1 + P_n-2 + P_n-3 + P_n-4 + P_n-5 + P_n-6)/6. Note, for P_n = 2/7, the sum of its six predecessors must be equal 12/7.

Let’s figure out the exact probability for P₇ using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6⁶, whereas the numerator of the sum becomes:
6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵. Note, the numerator is modulo 1 with respect to 6.
Thus P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁷.

For P₈ we add up P₂ through P₇ and divide it by 6. To bring P₂ through P₆ fractions to the common denominator of 6⁷, we must multiply their numerators by various powers of 6. Whereas the numerator of P₇ remains modulo 1 with respect to 6 and so will the numerator of P₈.

Thus by induction we know that the exact fraction for P₁₃₇ has 6¹³⁷ in its denominator and a very big who knows what in the numerator, which is modulo 1 with respect to 6, however. The numerator of that fraction is not divisible by 2 and its denominator is not divisible by 7. Therefore, it cannot be exactly equal to 2/7. That big fraction cannot be simplified at all - the numerator and denominator have no common factors.

Whoever finds the numerator - will have solved the problem.

In Excel spreadsheet, the probabilities for intermediate totals oscillated around 2/7, until the application ran out of precision having reached 15 digits past decimal point at the intermediate total of 108.

[CaptainEd]

Prime, your "disproof" notwithstanding, we should congratulate you on your insight that has identified the limit towards which any experiment to 137 should tend (IMH and Naive Opinion). I'm interested to understand about Bushindo's recursive code. My contribution was only to respond to Bushindo's numeric result, as it matches the cyclic stream of digits I learned in childhood.

[BobbyGo]

Thanks Bonanova. My explanation does look sound. But now, after I have taken some time to reflect, I must disprove and disown my solution.

Sure, the fraction that we found here is good for everyday gambling needs, but it is not the exact probability.

I suspect, Bushindo’s method would have produced the exact answer, had it not succumbed to rounding error.

Any number may or may not be an intermediate running total in this experiment. But there is one exception - zero! Zero running total will occur with 100% probability right before the very first roll.

Consequently, the probabilities for the first six numbers (1, 2, 3, 4, 5, and 6) to become intermediate totals are:

P₁= 1/6;

P₂= (1+1/6)/6 = 7/6²;

P₃ = (1+1/6+7/6²)/6 = 7²/6³;

And in the like manner,

P₄= 7³/6⁴;

P₅ = 7⁴/6⁵;

P₆ = 7⁵/6⁶;

Note, all the above probabilities are different from 2/7. First four are smaller, and the last two are higher.

From that point on we must change the method for probability calculation. Since a running total n can be obtained by a single roll from 6 preceding totals,

P_n = (P_n-1 + P_n-2 + P_n-3 + P_n-4 + P_n-5 + P_n-6)/6. Note, for P_n = 2/7, the sum of its six predecessors must be equal 12/7.

Let’s figure out the exact probability for P₇ using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6⁶, whereas the numerator of the sum becomes:

6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵. Note, the numerator is modulo 1 with respect to 6.

Thus P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁷.

For P₈ we add up P₂ through P₇ and divide it by 6. To bring P₂ through P₆ fractions to the common denominator of 6⁷, we must multiply their numerators by various powers of 6. Whereas the numerator of P₇ remains modulo 1 with respect to 6 and so will the numerator of P₈.

Thus by induction we know that the exact fraction for P₁₃₇ has 6¹³⁷ in its denominator and a very big who knows what in the numerator, which is modulo 1 with respect to 6, however. The numerator of that fraction is not divisible by 2 and its denominator is not divisible by 7. Therefore, it cannot be exactly equal to 2/7. That big fraction cannot be simplified at all - the numerator and denominator have no common factors.

Whoever finds the numerator - will have solved the problem.

In Excel spreadsheet, the probabilities for intermediate totals oscillated around 2/7, until the application ran out of precision having reached 15 digits past decimal point at the intermediate total of 108.

I'm glad I wasn't too far off in my thinking. I had a similar approach, but only considered 131 - 136 when trying to calculate the odds for 137. I had wrongly assumed each number 131 - 136 would have an equal likelyhood of being hit irrespective of of the likelyhood of any of the previous numbers.

I do have a question about one part of your disproof:

Let’s figure out the exact probability for P₇ using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6⁶, whereas the numerator of the sum becomes:

6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵. Note, the numerator is modulo 1 with respect to 6.

Thus P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁷.

If the common denominator for the first six probabilities is 6⁶, why does the equation for P₇ have a denominator of 6⁷?

Shouldn't the equation be:

P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁶

(Which equals my attempted answer of about .2536043952903521)

If this is right, I would assume that the common denominator would cap at 6⁶ as, eventually, all probabilities would be averages of probabilities with a 6⁶ denominator; including P₁₃₇.

[bushindo]

Prime, your "disproof" notwithstanding, we should congratulate you on your insight that has identified the limit towards which any experiment to 137 should tend (IMH and Naive Opinion). I'm interested to understand about Bushindo's recursive code. My contribution was only to respond to Bushindo's numeric result, as it matches the cyclic stream of digits I learned in childhood.

Here is the recursive code I used. The logic behind it is already described by Prime's excellent and insightful analysis.

Let P(N) be the probability that the total sum would eventually fall on number N. This code sets P(0) = 1, P( N ) = 0 for negative N, and then iterates recursively using a known formula as described in the following code

 
function P( N )

{

    if( N == 0 )

    {     return( 1 )    }    

    else if( N < 0 )

    {    return( 0 )    }

    else

    {

        A = 1/6*( P( N - 1 ) + P( N - 2 ) + P( N - 3 ) + P( N - 4 ) + P( N - 5 ) + P( N - 6 ) )

        return( A )

    }


}

[Prime]

...

I do have a question about one part of your disproof:

Let’s figure out the exact probability for P₇ using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6⁶, whereas the numerator of the sum becomes:
6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵. Note, the numerator is modulo 1 with respect to 6.
Thus P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁷.

If the common denominator for the first six probabilities is 6⁶, why does the equation for P₇ have a denominator of 6⁷?

Shouldn't the equation be:

P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁶

(Which equals my attempted answer of about .2536043952903521)

If this is right, I would assume that the common denominator would cap at 6⁶ as, eventually, all probabilities would be averages of probabilities with a 6⁶ denominator; including P₁₃₇.

The disproof stands.

In this instance, the sum of the six predecessors of P

₇ is a fraction with 6⁶ in the denominator. (That sum is greater than 1.) To get the probability of P₇ that sum must be divided by 6 resulting in 6⁷ in the denominator. (I made a shortcut. Instead of dividing individual probability of each predecessor by 6, I added them together, then divided by 6.)

I speculated, Bushindo's code could be something similar to the inductive step in my disproof.

This problem runs deeper than it appeared at the first glance. However, our tag team solution is practical. It must be exact for any intermediate sum past infinity. And 137, as it turns out, is a hefty step towards the infinity.

Edited January 15, 2013 by Prime

[BobbyGo]

Let’s figure out the exact probability for P₇ using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6⁶, whereas the numerator of the sum becomes:

6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵. Note, the numerator is modulo 1 with respect to 6.

Thus P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁷.

If the common denominator for the first six probabilities is 6⁶, why does the equation for P₇ have a denominator of 6⁷?

Shouldn't the equation be:

P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁶

(Which equals my attempted answer of about .2536043952903521)

If this is right, I would assume that the common denominator would cap at 6⁶ as, eventually, all probabilities would be averages of probabilities with a 6⁶ denominator; including P₁₃₇.

The disproof stands.

In this instance, the sum of the six predecessors of P

₇ is a fraction with 6⁶ in the denominator. (That sum is greater than 1.) To get the probability of P₇ that sum must be divided by 6 resulting in 6⁷ in the denominator. (I made a shortcut. Instead of dividing individual probability of each predecessor by 6, I added them together, then divided by 6.)

I speculated, Bushindo's code could be something similar to the inductive step in my disproof.

This problem runs deeper than it appeared at the first glance. However, our tag team solution is practical. It must be exact for any intermediate sum past infinity. And 137, as it turns out, is a hefty step towards the infinity.

I see where I went wrong. Somehow, I thought you were dividing the sum of the numerators by 6 and multiplying the denominator by 6. When I did mine, I worked the numerators first and then divided by the denominator to get a decimal number; opposed to your cleaner method of just multiplying the denominator and leaving it in fractal form. If that makes any sense whatsoever. I'm at work and it's hard to concentrate. (That's my excuse and I'm sticking to it)

[bonanova]

I see where I went wrong. Somehow, I thought you were dividing the sum of the numerators by 6 and multiplying the denominator by 6. When I did mine, I worked the numerators first and then divided by the denominator to get a decimal number; opposed to your cleaner method of just multiplying the denominator and leaving it in fractal form. If that makes any sense whatsoever. I'm at work and it's hard to concentrate. (That's my excuse and I'm sticking to it)

I'll believe your story.

But as I recall before retirement, being at work actually incented me to concentrate on something else.

[bonanova]

Prime, your analysis lays the groundwork for a great trivia question:

If I repeatedly roll a fair six-sided die, what number has the greatest

probability of occurring in the sequence of running totals?

It is a small number, (where the excursions around 2/7 are largest.)

[Prime]

Prime, your analysis lays the groundwork for a great trivia question:

If I repeatedly roll a fair six-sided die, what number has the greatest

probability of occurring in the sequence of running totals?

It is a small number, (where the excursions around 2/7 are largest.)

That is a trick question.

The correct answer is the running sum of zero has a probability of 1 (or 100%). It happens at the beginning of the experiment, right before the first roll. I guess that’s why Bonanova branded the question as “trivia” rather than math. (I nearly fell into the trap.)

The next highest probability is that of the running total 6. It is approximately 0.36.

Another math question for computer programmers is lurking in this thread. It has to do with Bushindo’s recursive code:

.......

Here is the recursive code I used. The logic behind it is already described by Prime's excellent and insightful analysis.

Let P(N) be the probability that the total sum would eventually fall on number N. This code sets P(0) = 1, P( N ) = 0 for negative N, and then iterates recursively using a known formula as described in the following code

 
function P( N )
{
    if( N == 0 )
    {     return( 1 )    }    
    else if( N < 0 )
    {    return( 0 )    }
    else
    {
        A = 1/6*( P( N - 1 ) + P( N - 2 ) + P( N - 3 ) + P( N - 4 ) + P( N - 5 ) + P( N - 6 ) )
        return( A )
    }
}

This computer program calculates the exact probability, until it uses up the allotted precision. And it is most economical in terms of code. However, it may not be so as far as execution time is concerned. Most of the running totals are re-calculated multiple times. Function P(n) calls itself 6 times for all n > 0. The math question is:

How many times the recursive function P(n) will be called for P(137)?

Edited January 19, 2013 by Prime

[bonanova]

Exponentially large number; hard to imagine P (137) was calculated in our Universe.

Some values of N, number of executions of P, and the value of P(N)

0 1 1

1 7 0.1666666667

2 13 0.1944444444

3 25 0.2268518519

4 49 0.2646604938

5 97 0.3087705761

6 193 0.3602323388 <== max

7 385 0.2536043953

8 763 0.2680940167

9 1513 0.2803689454

10 3001 0.289288461

11 5953 0.2933931222

12 11809 0.2908302133

13 23425 0.2792631923

14 46465 0.2835396585

15 92167 0.2861139321

16 182821 0.2870714299

17 362641 0.2867019247

18 719329 0.2855867251

19 1426849 0.2847128105

20 2830273 0.2856210802 2/7 = 0.2857142857142 ....

The formula is seen to be: executions of P to evaluate P(N) = 1 + 6 x 2^(N-1)

^{It's like 1 + 6 x {0 1 2 4 8 16 32 64 128 256 512 1024 ....}}

^{It gets multiplied by ~ 1 thousand for every increment of 10 in N.}

^{Check the numbers for P(0), P(9), P(19).}

For P(137) that's 1 + 6 x 2¹³⁶ ~ 10⁴² executions

Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10²⁵ years ~ 10¹⁵ Universe ages.

[Prime]

Exponentially large number; hard to imagine P (137) was calculated in our Universe.

Some values of N, number of executions of P, and the value of P(N)

0 1 1

1 7 0.1666666667

2 13 0.1944444444

3 25 0.2268518519

4 49 0.2646604938

5 97 0.3087705761

6 193 0.3602323388 <== max

7 385 0.2536043953

8 763 0.2680940167

9 1513 0.2803689454

10 3001 0.289288461

11 5953 0.2933931222

12 11809 0.2908302133

13 23425 0.2792631923

14 46465 0.2835396585

15 92167 0.2861139321

16 182821 0.2870714299

17 362641 0.2867019247

18 719329 0.2855867251

19 1426849 0.2847128105

20 2830273 0.2856210802 2/7 = 0.2857142857142 ....

The formula is seen to be: executions of P to evaluate P(N) = 1 + 6 x 2^(N-1)

^{It's like 1 + 6 x {0 1 2 4 8 16 32 64 128 256 512 1024 ....}}

^{It gets multiplied by ~ 1 thousand for every increment of 10 in N.}

^{Check the numbers for P(0), P(9), P(19).}

For P(137) that's 1 + 6 x 2¹³⁶ ~ 10⁴² executions

Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10²⁵ years ~ 10¹⁵ Universe ages.

I got a similar order; my table of numbers differs though.

At first glance, it may appear the number of executions of P(n) could be represented as a tree, where each branch splits into 6 more branches below. Thus at the bottom level, the number of nodes would be 6

¹³⁷. Add to that all the nodes from the above levels, and you get a very large number.

In reality, the number is a lot smaller than that. P(136) is called only once - from P(137). P(135) is called twice: from P(137) and P(136). P(134) is called 4 times: from P(137), P(136), and from the two instances of P(135). And so on.

The number of executions for each P(n) is a kind of 6-term Fibonacci sequence (I don’t know if there is an official name for it.) Each next number is obtained by adding up six of its predecessors. The table for n, P(n) and the total number of executions is as following:

137 ...... 1 .................. 1

136 ...... 1 .................. 2

135 ...... 2 .................. 4

134 ...... 4 .................. 8

133 ...... 8 .................. 16

132 .... 16 .................. 32

131 ..... 32 ................. 64

130 ..... 63 ................. 127

129 .... 125 ................ 252

128 .... 248 ................ 500

127 ... 492 ................. 992

126 .... 976 ................. 1968

125 ... 1936 ................. 3904

124 ... 3840 ................. 7744

123 .. 7617 .................. 15361

............................................................

1 ...... 1.48159*10^{40 ........} 2.98791*10⁴⁰

I am not including the terminal nodes P(0), P(-1),...,P(-5), where the exponential sequence changes. I think, I can see a closed-expression form for this sequence.

Closed-expression form, anyone?

[bonanova]

Exponentially large number; hard to imagine P (137) was calculated in our Universe.

Some values of N, number of executions of P, and the value of P(N)

0 1 1

1 7 0.1666666667

2 13 0.1944444444

3 25 0.2268518519

4 49 0.2646604938

5 97 0.3087705761

6 193 0.3602323388 <== max

7 385 0.2536043953

8 763 0.2680940167

9 1513 0.2803689454

10 3001 0.289288461

11 5953 0.2933931222

12 11809 0.2908302133

13 23425 0.2792631923

14 46465 0.2835396585

15 92167 0.2861139321

16 182821 0.2870714299

17 362641 0.2867019247

18 719329 0.2855867251

19 1426849 0.2847128105

20 2830273 0.2856210802 2/7 = 0.2857142857142 ....

The formula is seen to be: executions of P to evaluate P(N) = 1 + 6 x 2^(N-1)

^{It's like 1 + 6 x {0 1 2 4 8 16 32 64 128 256 512 1024 ....}}

^{It gets multiplied by ~ 1 thousand for every increment of 10 in N.}

^{Check the numbers for P(0), P(9), P(19).}

For P(137) that's 1 + 6 x 2¹³⁶ ~ 10⁴² executions

Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10²⁵ years ~ 10¹⁵ Universe ages.

I got a similar order; my table of numbers differs though.

At first glance, it may appear the number of executions of P(n) could be represented as a tree, where each branch splits into 6 more branches below. Thus at the bottom level, the number of nodes would be 6

¹³⁷. Add to that all the nodes from the above levels, and you get a very large number.

In reality, the number is a lot smaller than that. P(136) is called only once - from P(137). P(135) is called twice: from P(137) and P(136). P(134) is called 4 times: from P(137), P(136), and from the two instances of P(135). And so on.

The number of executions for each P(n) is a kind of 6-term Fibonacci sequence (I dont know if there is an official name for it.) Each next number is obtained by adding up six of its predecessors. The table for n, P(n) and the total number of executions is as following:

137 ...... 1 .................. 1

136 ...... 1 .................. 2

135 ...... 2 .................. 4

134 ...... 4 .................. 8

133 ...... 8 .................. 16

132 .... 16 .................. 32

131 ..... 32 ................. 64

130 ..... 63 ................. 127

129 .... 125 ................ 252

128 .... 248 ................ 500

127 ... 492 ................. 992

126 .... 976 ................. 1968

125 ... 1936 ................. 3904

124 ... 3840 ................. 7744

123 .. 7617 .................. 15361

............................................................

1 ...... 1.48159*10^{40 ........} 2.98791*10⁴⁰

I am not including the terminal nodes P(0), P(-1),...,P(-5), where the exponential sequence changes. I think, I can see a closed-expression form for this sequence.

Closed-expression form, anyone?

The given closed form shows an understandable accounting of the required executions, as N increases from zero.

The execution count includes:

1. One, for the initial execution, which directly returns 1, if N is zero

2. Additional executions, in Sets of six, comprising executions of the entire formula, when N is not zero.

3. The doubling of the number of Sets, as N increments, owing to recalculation of previous results.

4. The total, which is simply 1 plus 6 times the partial sum of the powers of 2.

Are you asking for a different closed form; one that gathers multiply-calculated results into 137 groups, then sums those numbers? Perhaps making those tables for a few smaller values of N will suggest the form of that expression.

Programming question: could execution time be drastically reduced, by storing previously calculated values of P and calling them from a table if needed again?

[Prime]

Exponentially large number; hard to imagine P (137) was calculated in our Universe.

Some values of N, number of executions of P, and the value of P(N)

0 1 1

1 7 0.1666666667

2 13 0.1944444444

3 25 0.2268518519

4 49 0.2646604938

5 97 0.3087705761

6 193 0.3602323388 <== max

7 385 0.2536043953

8 763 0.2680940167

9 1513 0.2803689454

10 3001 0.289288461

11 5953 0.2933931222

12 11809 0.2908302133

13 23425 0.2792631923

14 46465 0.2835396585

15 92167 0.2861139321

16 182821 0.2870714299

17 362641 0.2867019247

18 719329 0.2855867251

19 1426849 0.2847128105

20 2830273 0.2856210802 2/7 = 0.2857142857142 ....

The formula is seen to be: executions of P to evaluate P(N) = 1 + 6 x 2^(N-1)

^{It's like 1 + 6 x {0 1 2 4 8 16 32 64 128 256 512 1024 ....}}

^{It gets multiplied by ~ 1 thousand for every increment of 10 in N.}

^{Check the numbers for P(0), P(9), P(19).}

For P(137) that's 1 + 6 x 2¹³⁶ ~ 10⁴² executions

Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10²⁵ years ~ 10¹⁵ Universe ages.

The closed form expression 1+6*2^n-1 seems close,

It does not conform to the data in the table. E.g., for n=8, the table shows 763, whereas 1+6*2

⁷= 769.

The consequtive entries run off even further from the formula.

Yes, each next total in the table is twice its predecessor, but minus the 7th total back.

...

The given closed form shows an understandable accounting of the required executions, as N increases from zero.

The execution count includes:

1. One, for the initial execution, which directly returns 1, if N is zero

2. Additional executions, in Sets of six, comprising executions of the entire formula, when N is not zero.

3. The doubling of the number of Sets, as N increments, owing to recalculation of previous results.

4. The total, which is simply 1 plus 6 times the partial sum of the powers of 2.

Are you asking for a different closed form; one that gathers multiply-calculated results into 137 groups, then sums those numbers? Perhaps making those tables for a few smaller values of N will suggest the form of that expression.

Programming question: could execution time be drastically reduced, by storing previously calculated values of P and calling them from a table if needed again?

As for programming:

Of course, the execution time could be reduced by storing calculated results in an array and taking them from there when available. Recursive code seems most economical and simple, but it is dangerous. For this problem, I would use non-recursive code.

Modifying Bushindo's code to store results in array and do itterations instead of recursion we bring execution down to just 137 itterations:

Define Array P[143];

P[-5]=P[-4]=P[-3]=P[-2]=P[-1]=0;

P[0]=1;

FOR N=1 TO 137

P[N]=(P[N-1]+P[N-2]+P[N-3]+P[N-4]+P[N-5]+P[N-6])/6

PRINT P[N];

(Dont' ask me what language it is in.)

Execution time notwithstanding, recursive code gives rise to interesting math questions and Fibonacci like series.

Edited January 20, 2013 by Prime

[bonanova]

The given formula 1 + 6 x 2^(N-1) indeed discloses the order of magnitude, a

reasonable approximation, and an upper bound. Inspecting its divergence from

the actual count [i could not compute recursively past N=30 in reasonable time]

disclosed: the correction begins with the result from the seventh-preceding result.

It increases from that value going forward, exponentially, and always a factor 6, but

I could not find a closed form. So a closed form for the total answer remains to be found.

But execution efficiency for table look-up was dramatically better:

Whereas recursion prohibited going past N ~ 25 in reasonable time [a dinner break],

N= 100,000 with table look-up took only 20 seconds.

Convergence to the 2/7 value to 10 decimal places was achieved for N ~ 75.