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