Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * - 1 votes

Hitting 137


Best Answer Prime, 14 January 2013 - 09:32 PM

It seems to stand the reason...

Spoiler for just a guess

Go to the full post


  • Please log in to reply
19 replies to this topic

#11 Prime

Prime

    Senior Member

  • Members
  • PipPipPipPip
  • 872 posts
  • Gender:Male
  • Location:Illinois, US

Posted 15 January 2013 - 06:23 PM

...

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

 

 

Spoiler for Question

The disproof stands.

Spoiler for Probabilities

 

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 by Prime, 15 January 2013 - 06:26 PM.

  • 0

Past prime, actually.


#12 BobbyGo

BobbyGo

    Advanced Member

  • Members
  • PipPipPip
  • 130 posts
  • Gender:Male

Posted 15 January 2013 - 10:45 PM

 

 

Spoiler for Question

The disproof stands.

Spoiler for Probabilities

 

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)


  • 0

#13 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5840 posts
  • Gender:Male
  • Location:New York

Posted 16 January 2013 - 01:02 PM


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. :unsure:


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#14 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5840 posts
  • Gender:Male
  • Location:New York

Posted 19 January 2013 - 01:42 AM

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?

 

Spoiler for Since 2/7 holds for large numbers
   


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#15 Prime

Prime

    Senior Member

  • Members
  • PipPipPipPip
  • 872 posts
  • Gender:Male
  • Location:Illinois, US

Posted 19 January 2013 - 07:26 AM

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?

 

Spoiler for Since 2/7 holds for large numbers
   

 

That is a trick question.

Spoiler for two answers

 

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.

Spoiler for

 

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 by Prime, 19 January 2013 - 07:35 AM.

  • 0

Past prime, actually.


#16 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5840 posts
  • Gender:Male
  • Location:New York

Posted 19 January 2013 - 12:15 PM

Spoiler for How many times does P(137) execute P?

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#17 Prime

Prime

    Senior Member

  • Members
  • PipPipPipPip
  • 872 posts
  • Gender:Male
  • Location:Illinois, US

Posted 19 January 2013 - 11:46 PM

Spoiler for How many times does P(137) execute P?

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

Spoiler for Fibonacci?


  • 0

Past prime, actually.


#18 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5840 posts
  • Gender:Male
  • Location:New York

Posted 20 January 2013 - 01:00 AM


Spoiler for How many times does P(137) execute P?

I got a similar order; my table of numbers differs though.
Spoiler for Fibonacci?
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?
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#19 Prime

Prime

    Senior Member

  • Members
  • PipPipPipPip
  • 872 posts
  • Gender:Male
  • Location:Illinois, US

Posted 20 January 2013 - 04:32 AM

Spoiler for How many times does P(137) execute P?

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

Spoiler for however...

 

...

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 by Prime, 20 January 2013 - 04:36 AM.

  • 0

Past prime, actually.


#20 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5840 posts
  • Gender:Male
  • Location:New York

Posted 21 January 2013 - 11:47 AM

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.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users