I think the answer is around 20%. This is a game of summing throws of a nine-sided die (nine-sided because you can leave out all zeroes from the number) until you get at or over the number 666, and winning if you hit 666. A variant of it is known as black jack. Let p(n,b) be the probability that you eventually arrive at n using a b-sided die. Then: [1] p(n,b) = 0 for all n < 0 [2] p(0,b) = 1 [3] p(n,b) = sum( i in [1, b], p(n-i,b)/b) (once at distance n, you will get at each of the distances n-i with probability 1/b) From these, we get (for b > 3): [4] p(1,b) = p(0,b)/b = 1/b [5] p(2,b) = p(1,b)/b + p(0,b)/b = 1/b^2 + 1/b [6] p(3,b) = p(2,b)/b + p(1,b)/b + p(0,b)/b = (1/b^3 + 1/b^2) + 1/b^2 + 1/b = 1/b^3 + 2/b^2 + 1/b [7] p(4,b) = p(3,b)/b + p(2,b)/b + p(1,b)/b + p(0,b)/b = (1/b^4 + 2/b^3 + 1/b^2) + (1/b^3 + 1/b^2) + 1/b^2 + 1/b = 1/b^4 + 3/b^3 + 3/b^2 + 1/b Pascal's triangle forms here. That pattern will break once we get at a stage were we no longer sum all p(i,b) for i < n. From numerical simulation, this series appears to converge to 2/(b+1). For base 9, I get: p( 0, 9) = 1 p( 1, 9) = 0.111111 p( 2, 9) = 0.123457 p( 3, 9) = 0.137174 p( 4, 9) = 0.152416 p( 5, 9) = 0.169351 p( 6, 9) = 0.188168 p( 7, 9) = 0.209075 p( 8, 9) = 0.232306 p( 9, 9) = 0.258117 p( 10, 9) = 0.175686 p( 11, 9) = 0.182861 p( 12, 9) = 0.189462 p( 13, 9) = 0.195271 p( 14, 9) = 0.200033 p( 15, 9) = 0.203442 p( 16, 9) = 0.205139 p( 17, 9) = 0.204702 p( 18, 9) = 0.201635 p( 19, 9) = 0.195359 p( 20, 9) = 0.197545 p( 21, 9) = 0.199176 p( 22, 9) = 0.200256 p( 23, 9) = 0.20081 p( 24, 9) = 0.200896 p( 25, 9) = 0.200613 p( 26, 9) = 0.20011 p( 27, 9) = 0.1996 p( 28, 9) = 0.199374 p( 29, 9) = 0.19982 p( 30, 9) = 0.200073 p( 31, 9) = 0.200172 p( 32, 9) = 0.200163 p( 33, 9) = 0.200091 p( 34, 9) = 0.200002 p( 35, 9) = 0.199934 p( 36, 9) = 0.199914 p( 37, 9) = 0.199949 p( 38, 9) = 0.200013 p( 39, 9) = 0.200035 p( 40, 9) = 0.20003 p( 41, 9) = 0.200015 p( 42, 9) = 0.199998 p( 43, 9) = 0.199988 p( 44, 9) = 0.199986 p( 45, 9) = 0.199992 p( 46, 9) = 0.200001 p( 47, 9) = 0.200007 p( 48, 9) = 0.200006 p( 49, 9) = 0.200003 p( 50, 9) = 0.199999 p( 51, 9) = 0.199998 p( 52, 9) = 0.199998 p( 53, 9) = 0.199999 p( 54, 9) = 0.2 p( 55, 9) = 0.200001 p( 56, 9) = 0.200001 The 'oscillating' behavior surprises me, so there may be something wrong with this. Please let me know if that is the case. Reinder Verlinde ---------------------------------------------------------- I'm an engineer, so 0.2 is close enough for me. It's accurate to at least 60 digits, but I don't suppose that's good enough for you. Chris Lusby Taylor ----------------------------------------------------- It seems high, but I get a probability of 1/5 of hitting 666. If I keep adding random digits until the sum is 666 or greater, I can end at 666, 667, ..., 674 but not higher. There is only 1 way to end at 674, to have 665 and draw a 9, but there are 2 ways to end at 673; to have 665 and draw 8, or have 664 and draw a 9, etc, and 9 ways to end at 666: to have 665 and draw a 1, or have 664 and draw 2, etc. If these 45 ways of ending are equiprobable, 9/45=1/5 of them end at 666. Thanks, I love your puzzles. Earl Gose -------------------------------------------------------- What an amazing gem of a problem. I tried all sorts of things before pulling it all together to find the solution. The probability requested is *very* close to .2 First idea: Try to find the probabilities for smaller targets. target = 1: To get 1, the decimal must start with .1, .01, .001, ... This implies a probability of 1/10 + 1/100 + 1/1000 + ... for a total of 1/9 target = 2: To get 2, the deciamls start with .2, .11, .02, .101, .011, .002, .1001, etc This implies a probability of 1/10 + 2/100 + 3/1000 + ... for a total of 10/81 target = 3 the numerators in the probability are 1, 3, 6, 10, ... (the triangular numbers -- we have pascals triangle diagonals) the toal probability is 100/729 This implies a formula for target = t p(t) = 10^(t-1)/9^t which works for a while but eventually exceeds 1, so obviously it is not always correct. It works for t up to 9 because these are base 10 decimals. This formula could be extended to any base, but will only be accurate for targets smaller than the base. For example in a base 1000 system the probability would be 1000^665/999^666 = .0019470847 Not good enough... Second idea: Try to find the probabilites for smaller targets and smaller bases. In base 2 we are guaranteed to hit any target. That isn't helpful. In base 3 I got somewhere. Target = 1 probability = 1/2 Target = 2 probability = 3/4 Target = 3 consider the first digit if it is a 2, the next digits must give 1 so prob. = (1/3)(1/2) if it is a 1, the next digits must give 2 so prob. = (1/3)(3/4) if it is a 0, look at the second digit if it is a 2, the next digits must give 1 so prob. = (1/9)(1/2) if it is a 1, the next digits must give 2 so prob. = (1/9)(3/4) if it is a 0, look at the 3rd digit... The sum of these probabilites is (1/2 + 3/4)(1/3 + 1/9 + 1/27 + 1/81 + ...)= (5/4)(1/2) = 5/8 = .635 Target = 4 same reasoning gives probability (3/4 + 5/8)(1/3 + 1/9 + 1/27 + 1/81 + ...)= (11/8)(1/2)= 11/16 = .6875 Target = 5 probability = 21/32 = .65625 Target = 6 probability = 43/64 = .671875 These numbers jump up and down but converge upon 2/3. This implies that for very large targets the probability is very close to 2/3. Aha! Time to combine these ideas: Back to base 10 we know the probabilities for targets 1 through 9. The probability for 10 is the sum of the first nine probabilities time 1/9. In general p(t) = (sum of previous 9 probabilities)(1/9) So this is can generate a recursive sequence. A quick program shows that this probability converges to .2 rather quickly. A further observation: The probability in a given base, b, converges to 2/b for large targets. -Jeremy Galvagni ------------------------------------------------------------------------------------- Hello Ed, as I am currently playing with probabilities (in other context, though), your following question immediately catched my interest: ====================================== It is known that the first 144 digits of Pi equals 666. Ilan Honig points out that the first 146 digits of the golden ratio equals 666. That led me to wonder -- given a random irrational number, what is the probability that 666 will be hit exactly by taking successive digits? Send Answer. ====================================== Intuitively I thought it must be clearly above 1/9, but intuition might mislead one... irrationality ensures independence of numbers draws, it seems, ... ... so that I set some recursive equations into Excel and got oscillating system stabilizing slowly at the probability going to 1/5 for any sufficiently high sum, for 666 the error is of order 1E-16. I also noticed, that the sum that is the most likely to appear, is 9, more than 1/4 probablity. ... if my equations were not wrong, of course. :-) I am eager to see some more sophisticated approach, proof ... Best wishes, Juraj Lorinc ----------------------------------------------------------------------- Hello, You can compute the probability P(m) that taking the sum of successive digits of a random real between 0 and 1 (i.e. each digit is random between 0 and 9, uniformly and independently) gives a given number m. Letting P(0)=1 (an empty sum always gives 0) and P(m)=0 for all m<0, you have the following equation: P(n) = ( 1/10 P(n) + 1/10 P(n-1) + 1/10 P(n-2) + ... + 1/10 P(n-9) ) which is based on enumerating all 10 possible cases for the first digit. This implies the linear recurrence P(n) = ( P(n-1) + P(n-2) + P(n-3) + ... + P(n-9) ) / 9 which gives P(666) approximately equal to 0.2 (actually, 2-P(666) is around 2e-64). It is in fact possible to show that P(n) converges to 0.2 with exponential speed (email me if you are interested in the details). For example, P(10) is already equal to 2.025, and P(25) to 0.20061. This result can be very easily interpreted intuitively (each digit 1-9 contributes on average 5 to the sum, so that one out of five integers can be reached). And the result can be generalized to base-k numbers, where the limiting probabilty is 2/k. Regards, François Glineur ----------------------------------------------------------------------- For sufficiently great n, the probability of reaching a integer is asymptotly 1/5. (Sent image http://www.mathpuzzle.com/666.gif/ ) Jordi Domènech ----------------------------------------------------------------------- The probability that the sum of a uniformly distributed string of digits 0-9 will exactly equal an arbitary number k before exceeding it approaches 1/5 rapidly as k increases. More generally, the probability that the sum of a string of random positive integers uniformly selected from a set [x1,x2...xn] with no common factors will equal an arbitrary constant k before exceeding it approaches n/sum(x1,x2...xn) as k increases. In the case of [1,2...9], 9/45 = 1/5. Andrew Juell ----------------------------------------------------------------------- Ed, You recently posed a problem where given a random irrational number that the digits (I'm assuming beginning with the digit after the decimal place) sum up exactly to 666 at some point. Assuming that by "random irrational" is meant an irrational with random sequence of digits after the decimal point, the answer is 1/5 (.2). To get there, I look at the general case of a sum of N. We're looking for the probability that a random string of decimal digits at some point adds up to N. Let's call this p(N). For N >= 10, you can only reach a sum of N by 1st reaching a sum of some (N - d) (for 0 < d < 10) and then getting the digit d, or the digit 0 any number of times followed by d. The probability of a d, or 0d, or 00d, ... is .111... = 1/9. So p(N) = (1/9) p(N - 1) + (1/9) p(N - 2) ... + (1/9) p(N - 9) or p(N [N >= 10]) = [Sum (for k = 1 to 9) of p(N - k)]/9 For N < 10, there's also the case of the digit 'N' being the 1st of which the probability is 1/10, so the complete recurrence can be stated as p(N) = [Sum (for k = 1 to 9) of p(N - k)] / 9 + (N < 10) (1/10) where the term (N < 10) equals 1 if the conditions is true and 0 otherwise. I didn't try very hard to solve this recurrence, but calculating it out for small values of N I get: N p(N) p(N) approximation ====================================================================== 0 1/10 .100000 1 1/9 (10^0 / 9^1) .111111 2 10/81 (10^1 / 9^2) .123456 3 100/729 (10^2 / 9^3) .137174 4 1000/6561 (10^3 / 9^4) .152415 5 10000/59049 (10^4 / 9^5) .169350 6 100000/531441 (10^5 / 9^6) .188167 7 1000000/4782969 (10^6 / 9^7) .209075 8 10000000/43046721 (10^7 / 9^8) .232305 9 100000000/387420489 (10^8 / 9^9) .258117 10 612579511/3486784401 .175686 11 5738374621/31381059609 .182861 12 53509541320/282429536481 .189461 13 496353364300/2541865828329 .195271 14 4576113154000/22876792454961 .200032 15 41886926650000/205891132094649 .203442 16 380127217600000/1853020188851841 .205139 17 3413851687000000/16677181699666569 .204701 18 30264311980000000/150094635296999121 .201634 19 263901070900000000/1350851717672992089 .195359 20 2401684855296999121/12157665459056928801 .197544 21 21793684651236981541/109418989131512359209 .199176 22 197206153848009709930/984770902183611232881 .200255 23 1779764075366195956600/8862938119652501095929 .200809 24 16024760757819947260000/79766443076872509863361 .200896 25 144019753972749340750000/717897987691852588770249 .200613 ... 50 .199999 51 .199997 52 .199997 53 .199998 54 .200000 55 .200001 ... The function appears to be converging to .2 in an oscillatory manner. But since for large N (let's say 60 or above), p(N) = 1/9 [(.200 + e(1)) + (.200 + e(2)) + ... + (.200 + e(9))] = .2 + 1/9 [ Sum of e(i)] where e(i) are the small oscillatory error terms. This tells me that the difference of .2 and p(N) is decreasing as N increases, so I will go out on a limb and say that p(N) converges to .2 Monte Carlo runs have provided further evidence for these numbers. In performing some earlier Monte Carlo investigations, I ran the trial of summing up random digits until the sum exceeded some threshold and then incremented count[sum - threshold]. For threshold >> 10, a typical 10000 rep run would have these statistics: 0 : 2001 1 : 1769 2 : 1498 3 : 1365 4 : 1166 5 : 898 6 : 656 7 : 431 8 : 216 Of course, from our earlier analysis, the threshold value should come up .2 of the number of trials and it does here. For a value that is k higher than the threshold, it is robbed of a chance to get to thresh + k by going through thresh, or thresh - 1, ... so for 0 <= k <= 8 p(k) = .2 ( 1 - k/9). 0 : .2 1 : .17777... 2 : .15555... 3 : .13333... 4 : .11111... 5 : .08888... 6 : .06666... 7 : .04444... 8 : .02222... As a check, these should add up to 1. Sum (k = 0 to 8) .2 (1 - k/9) = .2 * 9 - .2 * (1 + 2 + .. + 8)/9 = 1.8 - .2 * (36/9) = 1.8 - .8 = 1 And they do. Clark Cooper ----------------------------------------------------------------------- I'm assuming the problem refers to the *first* N digits of the number, not *any* set of consecutive digits. At some point you'll hit a sum in the range [657-665], since you cannot go from 656 (or below) to 666 (or beyond) in one shot (at least, not in base 10). If several small digits occur in a row, you might have several "stops" in the range. Eventually, you'll hit 666 or go over, never to have another chance. One of these will occur: (X = fail, ! = success) 657 + 9 ! 658 + 9 X, +8 ! 659 + 9 X, +8 X, +7 ! 660 + 9 X, +8 X, +7 X, +6 ! 661 + 9 X, +8 X, +7 X, +6 X, +5 ! 662 + 9 X, +8 X, +7 X, +6 X, +5 X, +4 ! 663 + 9 X, +8 X, +7 X, +6 X, +5 X, +4 X, +3 ! 664 + 9 X, +8 X, +7 X, +6 X, +5 X, +4 X, +3 X, +2 ! 665 + 9 X, +8 X, +7 X, +6 X, +5 X, +4 X, +3 X, +2 X, +1 ! 45 possible 'critical situations', 9 successes = 1/5. (If you get a smaller number, than shown after a +, you try again on the same (0) or a different row.) Since probability is not my forté, that is 'probably' wrong, but I thought I'd take a stab. (And maybe all the incorrect solutions are interesting in themselves.) Toby Gottfried ----------------------------------------------------------------------- Probability of 666 digit sums: Assume that the numbers are chosen with uniform distribution over some interval between powers of 10. Then all digits 1-9 are equally likely at any point and the zeroes don't matter. For very small sums, you can compute the probability directly. So to reach a sum of 1, you have to start with a 1, so 1/9. To reach 2, you must start with 11 or 2, so 1/9 + 1/81 = 10/81. To reach 3, it must start with 111, 12, 21, or 3, so 1/9 + 2/81 + 1/729 = 100/729. This pattern of multiplying by 10/9 continues up to a sum of 9 because the numbers of possible sequences of each length are simply the binomial coefficients, and multiplying them by powers of 1/9 is the equivalent of calculating x(x+1)^sum for x = 1/9. This pattern of necessity breaks (because the value would eventually exceed 1), and in this case does so at a sum of 10 because a single digit equal to 10 is not available. For larger sums, consider the sum of the numbers immediately before the one which gives us our desired sum. We could reach n by reaching n-1 and then getting a 1, or by reaching n-2 and getting a 2, and so on. So for n>9, this probability is simply 1/9 the sum of the previous 9 terms -- the average of the previous 9 terms. Naturally, this means the sequence approaches a limit. It is quickly apparent that the limit is 1/5, and before you reach a sum of 200, the probability is within less than 10^-10 of this value. ----------------------------------------------------------------------- Hello Ed, To this question I would answer : the probability converges towards (number of non-zero digits / sum of digits). In base 10, it gives 9/(1+2+3+4+5+6+7+8+9) = 20% From the random rational, we can remove all zeros as they don't contribute to reaching new integers. The other digits being equiprobable, we can reason on the number 0,1234567891234567891234... Every time we run through a range of 45 integers, only 9 are hit. But that is only correct if the targeted integer is big 'enough'. Indeed, the probability to reach integer 1 is 1/9 : if the first non-zero digit is 1. There is obviously a markov-chain thing somewhere.... eheh Tell me if I am wrong ;-) Bye, Antony Boucher