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.
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.
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. 
“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).
(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
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
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
Somehow, I’m doubting a pattern is going to jump out at anyone. But, please surprise me.
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?
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
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.
ix^(i-1) + (i+k)x^(i+k-1) + (i+2k)x^(i+2k-1) … = ix^(i-1)/(1/x^k)+x^ix^(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