# Original Pure Math Question **URL:** \ **Category:** Factual Questions\ **Created:** [May 23, 2000, 10:29am UTC](https://boards.straightdope.com/t/original-pure-math-question/20267 "2000-05-23T10:29:55Z")\ **Posts on this page:** 8\ **Page:** 2
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 26, 2000, 3:44am UTC](https://boards.straightdope.com/t/original-pure-math-question/20267/21 "2000-05-26T03:44:52Z")
And by the way, let me be the first to welcome (Tim) to the board! We can always use more mathematicians here. Feel free to stop by other threads, too… We could really have used you for some of tony1234’s [probability threads](http://boards.straightdope.com/sdmb/showthread.php?threadid=15701). As for a d23, I would use a d12 and a d2 to simulate a d24 (or a d4 and a d6) and then apply method alpha. ---
**Author:** ![\_Tim](https://avatars.discourse-cdn.com/v4/letter/_/e47c2d/32.png) [@\_Tim](https://boards.straightdope.com/u/_Tim)\ **Post date:** [May 26, 2000, 6:47pm UTC](https://boards.straightdope.com/t/original-pure-math-question/20267/22 "2000-05-26T18:47:18Z")
Achernar, your simplification is valid, but as you say it still isn’t readily solvable. I wouldn’t know how to go about solving it analytically. Also, one reason why my formula is similar to yours is that we’re describing the same thing. 😉 However, this form is amenable to numeric approximation. I suspect that after the first thousand or so terms it’ll be close to the correct answer, and that should be fairly quick with modern computers. It will only be a lower bound on the actual number. It would also help assume all 1-p(k\>=1) ends on the final number examined, rather than letting that be 0 by ignoring it… I think I’ll code this when I have time. Chronos, thanks for the welcome. I’m afraid that I’m not a mathematician, just an amateur who had seen a similar problem in the past. Now, if you have any chemistry problems… :rolleyes: I will look around the site sometime soon. I will mention that an ISD would crush the Enterprise. 🙂 About the d23- a first hint is that it’s never efficient to use any die other than a d8, d12,or d20. (a d2, d4, d6, or d10 is a factor in one or more of these) I’ll give you the first two steps in a more efficient strategy for the d23: First, use 2d20 to generate a base 400 random number. Assign 23 groups of 17 to the numbers, giving an answer 391/400 of the time. Next, use the base 9 number from the possible outcomes above, and a d8 to generate a base 72 number. Assign groups of three to get a number 69/72 of the time. Then you can use a d8 again to assign the answer 23/24 of the time. Lather, Rinse, Repeat. This way, you only fail to assign the d23 within 4 rolls 1/25600 of the time. This may not even be optimal, I didn’t check thouroughly. You see, you have to evaluate all the combinations of the 3 useful dice each roll. It gets even more complicated when you realize that there are times when it’s advisable to take a lower chance of success on the kth roll in order to get a better random seed for use in the (k+1)th roll. Anyhow, it’s a somewhat similar problem, but was discussed at length some time ago in rec.puzzles, so I’m not really asking the question. Feel free to think about it if you find it interesting though. 🆒 ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [May 26, 2000, 7:39pm UTC](https://boards.straightdope.com/t/original-pure-math-question/20267/23 "2000-05-26T19:39:11Z")
“I suspect that after the first thousand or so terms it’ll be close to the correct answer.” Yeah, but how are you planning on **getting** the first thousand terms? Let me give you an example. Suppose that N = 5 and you’re computing the 200th term, Ie: k = 200. Starting inside the parentheses, you’ll need 2[sup]200[/sup]. Okay. That’s: 1.6069380442589902755419620923412×10[sup]60[/sup] Now you need to divide it by 5. No sweat: 3.2138760885179805510839241846823×10[sup]59[/sup] Now you need to take the greatest integer. Uh-oh. You don’t even know this number all the way to the decimal point. How are you going to do that? And this calculation **has** to be accurate for this to work. I did this all up on a computer, using 8-byte doubles, and I found that it tended to break down around 2[sup]60[/sup], which makes sense, since 2[sup]64[/sup] would be 8 bits. I used my formula, but even I couldn’t get any farther, I think, than N = 57, because around there, d \> 60. But at least I could Exp(5). About that dice-rolling problem. Yow, that is definitely more complicated that I originally thought. I would have made the same mistake **Chronos** did; I think since I’ve been posting on this thread long enough I’ve started making the unconscious assumption that the efficiency of something can be determined solely by the number of random numbers it generates. True when you only have one die (or one coin, or whatever) but not so when you have multiple ones. Maybe if I weren’t so consumed in this problem, I’d take a good long look at yours, **(Tim)**. 🙂 ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 26, 2000, 11:44pm UTC](https://boards.straightdope.com/t/original-pure-math-question/20267/24 "2000-05-26T23:44:37Z")
(Tim): It depends on you definition of efficiency. If you’re trying to minimize the expected number of die rolls, then yes, your answer is (I presume) more efficient. If, on the other hand, you’re trying to minimize the expected value of the total computation time, then it depends on the efficiency of each step, not just the rolls. For the type of computer most likely to be rolling D&D dice (i.e., a person 🙂 ), my method is far more efficient. I mean, really, how quickly can YOU find a number between 1 and 400 modulo 17? And don’t worry, we can use chemists here, too. Just as long as you’re not a relativistic physicist, I don’t want the competition 😉 ---
**Author:** ![\_Tim](https://avatars.discourse-cdn.com/v4/letter/_/e47c2d/32.png) [@\_Tim](https://boards.straightdope.com/u/_Tim)\ **Post date:** [May 27, 2000, 12:54am UTC](https://boards.straightdope.com/t/original-pure-math-question/20267/25 "2000-05-27T00:54:48Z")
Chronos: Oh, so you actually want to _use_ the method… 🙂 Archernar: The ‘first thousand’ answer was a bit flippant; note that the error will be less than N/2^k. 100 flips gives you about 30 digits of accuracy, which is enough for most purposes. (Incidentally, it is possible to do ‘arbitrary’ precision arithmatic in fortran, for example; I don’t think it’s necessary here, though.) I did do a bit of coding; I used a slightly modified but still recognizable version of the formula we’ve been kicking around. I used a variable for the remainder, and only added that k\*2^n if it subtracted from the remainder. This is analogous to your binary expansion of the fraction. My code is fortran, and I don’t know how to make this posting method keep the spacing, sorry… * * * ``` integer*8 N,rmdr,rmdr2 real*16 ANR,k ANR=0. rmdr=1 read(5,3) N ``` ## 3 format(i5) do 1 k=1.,100.,1. rmdr=rmdr_2 if(rmdr.ge.N) then rmdr=rmdr-N ANR=ANR+(k/(2.\*\*k)) endif 1 continue ANR=ANR_real(N) ANR=ANR+((k+1.)\*real(rmdr)/2.\*\*(k+1.)) write(6,2) ANR 2 format(1f50.47) end A few results: 5: 3.59999999999999999999999999993838996331810815173 7: 3.42857142857142857142857142845005668645468068245 9: 4.66666666666666666666666666624686118829212270203 11: 4.84848484848484848484848484842225356728436597570 13: 4.70769230769230769230769230750706494730012255501 15: 4.26666666666666666666666666660453072271756621307 17: 5.76470588235294117647058823433152172838396031073 19: 5.72319688109161793372319688007000077362192541370 21: 5.42857142857142857142857142761307526602400336454 23: 5.70200293111871030776746458219062505371315224563 25: 5.55121951219512195121951219505880194204822930688 27: 5.61403508771929824561403508621472598457475272459 29: 5.43631370155630149527006408149858214009936070223 31: 5.16129032258064516129032258058231961275038735345 37: 6.79005130748250014305060176546841002744441744084 41: 6.55024390243902439024390243896045287515805133831 43: 6.94573643410852713178294573618342198492495738812 47: 6.75069889434562854118687405301920185848825899695 (early ones are known) 11: 4 28/33 13: 4 46/65 15: 4 4/15 17: 5 13/17 19: 5 371/513 21: 5 3/7 23: 5 1437/2047 25: 5 113/205 27: 5 35/57 29: 5 7149/16385 31: 5 5/31 37: 6 207108/262145 41: 6 564/1025 43: 6 122/129 47: 6 6297318/8388607 The fractions aren’t guarenteed to be correct; I used the following code for the harder ones: * * * ``` real*16 k,n,kn integer*4 c read(5,3) k ``` ## 3 format(f50.47) c=1 do 1 n=1.,10000000.,1. kn=k\*n if((kn-real(int(kn))).gt.(.99999999))kn=real(int(kn))+1. if((kn-real(int(kn))).lt.(.00000001)) then write(6,2) k,n,kn 2 format(3f30.15) if(c.eq.10) goto 4 c=c+1 endif 1 continue 4 end Somehow, I’m doubting a pattern is going to jump out at anyone. But, please surprise me. 🙂 ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [May 27, 2000, 1:13am UTC](https://boards.straightdope.com/t/original-pure-math-question/20267/26 "2000-05-27T01:13:43Z")
Alright, I guess I should learn Fortran, then. 🙂 In the meantime, I’m stuck with C++, but I think that’s okay, because I should be able to write a class which allows me to do arbitrarily large integer arithmetic. I won’t post it here, because my code tends to be… inefficient. I guess “showy” would be a better word. Anyway, if you don’t mind, I’ll use my method, which lends itself better to integer arithmetic, since it sets (2[sup]d[/sup] - 1)[sup]2[/sup] as an upper limit on the denominator. I concede that if I were a reasonable person, I would accept your solution, **(Tim)**, but I just don’t like approximations. 🙂 Also, I was working it out, and I began to wonder… Do these things get arbitrarily efficient as they get bigger? That is, I suppose, does lim (Exp(N)/log[sub]2[/sub]N) exist, and is it (gasp!) 1? ---
**Author:** ![\_Tim](https://avatars.discourse-cdn.com/v4/letter/_/e47c2d/32.png) [@\_Tim](https://boards.straightdope.com/u/_Tim)\ **Post date:** [May 27, 2000, 8:59pm UTC](https://boards.straightdope.com/t/original-pure-math-question/20267/27 "2000-05-27T20:59:12Z")
Don’t bother learning fortran, I hear C++ is generally a much better language. I only learned fortran because I was modifying and adding to preexisting fortran code in grad school. The only formal programming course I took was in C. 🙂 I strongly suspect that someone has written code for arbitrary-precision arithmatic in C++ too, you might try a web search. I agree that this numeric solution is unsatisfying. I do find it more satisfying than no solution, however. 😉 You mention a (2^d-1)^2 denominator, but my code uses a 2^d denominator, which seems logical given the 2^d possible combinations of outcomes. As to your limit, the it is indeed 1. Given a number between 2^n and 2^n+1: The upper limit of the chance of requiring more than n+1 throws is 1/2. The upper limit of the chance of requiring more than n+2 throws is 1/4. Etc. The summation of 1/2+1/4+1/8… = 1. Therefore, the expected value of the number of throws needed is bounded by n+2. In the limit as N approaches infinity, the 2 will be negligible w.r.t. the log2N denominator. EXP(2^n+1) is asymptotic to n+2 as n increases, e.g. for 65537: 17.99975586310023345591040175666865435886125931148 Now, I don’t know if I would call this arbitrarily efficient, but does become so as you’ve defined it, w.r.t. log2N. Tim ---
**Author:** ![\_Tim](https://avatars.discourse-cdn.com/v4/letter/_/e47c2d/32.png) [@\_Tim](https://boards.straightdope.com/u/_Tim)\ **Post date:** [June 1, 2000, 8:44pm UTC](https://boards.straightdope.com/t/original-pure-math-question/20267/28 "2000-06-01T20:44:15Z")
Okay, after long delay, the analytic solution: First, generate the binary expansion of the repeating binary representation of 1/N (see, Achernar, you were right 🙂 ) let k be the number of digits which are repeated and i be a position of a particular 1 within the repeating unit. Each one in the repeating unit represents an infinite geometric series. The expected number of outcomes is equal to the probability of each one (N times 2^-number of flips) times the number of flips. The average number of flips will be N times the infinite summation for each of the ones in the binary expansion: N\*(sum over all i where digit is 1) of: i\*x^i + (i+k)x^(i+k) + (i+2k)x^(i+2k) … Now, to solve this infinite series, start with the most simple geometric one: 1 + x + x^2 + x^3 … = 1/(1-x) Note that x will be 1/2 throughout. Substitute x^k for x. 1 + x^k + x^2k + … = 1/(1-x^k) Multiply both sides by x^i x^i + x^(i+k) + x^(i+2k) … = x^i/(1/x^k) Now the trick- differentiate both sides. i_x^(i-1) + (i+k)x^(i+k-1) + (i+2k)x^(i+2k-1) … = ix^(i-1)/(1/x^k)+x^i_x^(k-1)\*(1/x^k)^2 Multiply both sides by x and simplify: i\*x^i + (i+k)x^(i+k) + (i+2k)x^(i+2k) … = {ix^i+(k-i)x^(k+i)}/(1-x^k)^2 The average number of flips required is therefore equal to N times the sum of {ix^i+(k-i)x^(k+i)}/(1-x^k)^2 over all i’s in the binary expansion of 1/N. I’ve coded this, and to works… sometimes. ( I think I’m exceeding limits on integers.) Anyhow, here are some exact results. The format is N, numerator, denominator. 3 8 3 5 18 5 7 24 7 9 14 3 11 160 33 13 306 65 15 64 15 17 98 17 19 2936 513 21 38 7 23 11672 2047 25 1138 205 27 320 57 29 89074 16385 31 160 31 33 226 33 35 27592 4095 37 4669510380151843082 -137438953471 39 600 91 41 6714 1025 43 896 129 45 9274 1365 47 10107193409760 1497206965967 49 1985714 299593 51 328 51 53 -2957180271666859382 -9007199254740991 55 91048 13981 57 1118 171 59 7387341914293869920 -576460752303423487 61 8924378185174938962 -2305843009213693951 63 128 21 65 514 65 67 -5149539208175850664 1 69 32740246 4194303 71 79853147459949752 -1963413621 73 554 73 75 1621984 209715 77 8215881550 1073741823 79 23778824631758272 -35468117025 81 7898475704543561282 -36028797018963967 83 7301213462461240952 1 85 626 85 87 2117196184 268435455 89 15942 2047 91 704 91 93 7822 1023 95 -1452444394240966176 -137438953471 97 -8550538500261448030 -562949953421311 99 82792 10923 This shows that the formula is sound, even if my implementation of it is flawed for some numbers (e.g. 37) Tim [Previous page](https://boards.straightdope.com/t/original-pure-math-question/20267.md?page=1)