little problem just thought of (evil numbers)

[imfatandugly]

I was just reading this stupid thing that said that the hard square entropy constant is evil because the first x digits of it sum to 666. So I was thinking that wasnt a very remarkable property...
In particular what is the probabilty that if you have an infinate string of random numbers from 1 to B that the first however many numbers sum to n.
For instance if B=10 then p(1)=1/10, p(2)=1/10 + 1/100.

[T50_Omaha8]

I'm just scanning right now and don't have the time to look for the solution exactly, but here's my gut:

I think for any finite string of n random digits, given the string of n digits sums to a number greater than N and N is relatively large (666 should easily do), the probability the first m digits sum exactly to N should be right around 2/9.

I say this because the expected value of any digit is 4.5, so the sum of n digits should be very close to 4.5n (as the average digit value converges to 4.5); that is, as the digits are added up to eventually reach a value close to 4.5n, exactly n of the numbers less than or equal to 4.5n will have been part of the partial sum of the string of numbers. That gives 1/4.5 = 2/9.

Catch my drift?

[HP]

T50,

however we can assume there are no 0's, since if there was it wouldn't matter

so now the average digit is 5, which would change your answer...

[imfatandugly]

[ QUOTE ]

Catch my drift?

[/ QUOTE ]
I feel you. Your both a little bit off though if we are using 1,2,...,10. If 1,...9 then second guy is right. the average of 1,2,3,...,B is (B+1)/2. So does that mean that p(n)-> 2/(B+1) as n-> infinity? I dont think so.....its much complicated than that.

I'll use B=2 and see if we come up with anything.
p(1)=1/2
p(2)= 1/2+1/2*p(1)=3/4
p(3)= p(2)*1/2 +p(1)*1/2= 3/8+1/4=5/8

so maybe p(n)=(p(n-1)+p(n-2))/2, can anyone confirm this? which is a linear recurrance equation ( http://mathworld.wolfram.com/LinearR...eEquation.html )
from which we can see that p(n)/p(n-1)--->some constant involving square roots. and we can actually get an explicit formula. But then again I have no idea if that implicit formula is correct. If it is I think in general p(0)=1, p(1)=1/B, p(n)=(p(n-1)+p(n-2))/2 but this is just a shot in the dark.

[imfatandugly]

[quote ] edit. If it is I think in general p(0)=1, p(1)=1/B, p(n)=(p(n-1)+p(n-2)+...+p(n-B))/B but this is just a shot in the dark.

[/ QUOTE ]

[imfatandugly]

Also it might be better to think of the measure of the set of the numbers between 0 and 1 that have this property(digits add up to n). Although you'll get a different answer i imagine.
so for n=1, any numbers it the intervals, [.1,.2),[.01,.02), [.001,.002),....,
this set has size .1+.01+.001+...+=1/9

if n=2
[.2,.3),[.02,.03),...
or [.11,.112),[.011, .0112),
so it has size .1+.02+.002+...+=.1222222222222222=2/90+1/10=11/90

I think this is the problem that should be solved as we are interested in the probability that some number is evil, and this will give it to us. FYI it looks like as n->infinity the measure of this set will not be rational.

[pzhon]

First, let's look at the probability that a number uniformly chosen from [0,1] is evil, that some partial sum of the digits is 666.

As T50 Omaha8 and HP pointed out together, en route to a partial sum of about 5n, n distinct partial sum values occur, and 4n are missed. You should expect that 666 is hit close to 1/5 of the time.

More precisely, I'd use a recurrence relation to compute and analyze the probability that a number is evil. Let P(k) be the probability that some partial sum of the digits is k. Then P(k)=1/9 P(k-9)+1/9 P(k-8)+ 1/9 P(k-7)+...+1/9 P(k-1)), since the event that some partial sum is k is made up of the disjoint events that some partial sum is k-9 and the next nonzero digit is 9, that some partial sum is k-8 and the next nonzero digit is 8, etc. The initial condition of this recursion can be taken to be that P(-8)=P(-7)=...=P(-1)=0 and P(0)=1.

This is enough to get the value of P(666). You can do this easily in Excel or a computer algebra package.

P(666) = 0.199999999999999999999999999999999999999999999999 99999999
99999997833777316286476055279462594065133327756...
=
67072003957152089994007282402178293562659723859308 07941737
80101479173085047914089564589801155880985448323529 34205821
16278550963485230993377867380331702382242879075141 05646309
12732675226130221195954583832518116062232132317527 11518628
79661599283627354161178286320855627805912128721785 40320655
39680528781319793043800059600198463801207184151822 02364564
58532490490308655415665938712316701573324633224832 42228589
38609140020461008848721246944601062210937797646744 39120107
02635350532532421896020217903938470201131126776317 92990635
38588479967204114608449603102519994141366640807202 89901923
82350330021997851952577975389933766102755019571739 00000
/
33536001978576044997003641201089146781329861929654 03970868
90051102818783559222290456531308601170092436024376 12444487
98537924945220856459819880495994427577330654943353 48281417
66751608597294633585525219647708472718792410231524 90826991
16949466672374409303877609901968360690960798797733 20769764
50879896380110511593645777350483201299534733376700 32234611
08489362979794884294210397848614880456752725324127 10014736
23765153187946181590579926578816758899445283328759 11168011
94019662325595357343349509899602153788515299927791 41186684
94378546689326217730448030081107100187515580027879 55858973
30179481023083090946366577527764009296902618035044 877841

If you want to approach this theoretically, then this is a linear recurrence relation, and all of the usual methods for these recurrences work. The probability P(m) can be expressed as a sum c_1 lambda_1^m + c_2 lambda_2^m + ... + c_9 lambda_9^m. This is because you can express the transformation (P(k-9),P(k-8),...P(k-1)) --> (P(k-8),...,P(k)) as a matrix M. You'd like to apply the 666th power of M to (0,0,...,0,1), which is easier if you express (0,0,...,0,1) as a sum of eigenvectors v_i so that vM is lambda_i * v_i, and vM^666 = lambda_i^666 * v_i. The lambda_i are the roots of the characteristic polynomial x^9 - 1/9(x^8+x^7+...+x+1).

The largest roots of the characteristic polynomial are 1 and two complex roots of magnitude 0.804394... As these have a nonzero contribution, the difference between P(n) and 1/5 oscillates and shrinks as c * 0.804394^n. 0.804394^n is about 10^-63 when n=666.

Second, note that this is not really the probability that a randomly encountered number is evil. A better model would produce a higher probability of having 1 as a leading digit than 9. The unique multiplication-invariant distribution has probability log_10(2) of starting with 1, probability log_10(n+1)/n of starting with n from 1 to 9. Subsequent digits are not quite uniformly distributed. See Benford's Law (Newcomb).

This has a microscopic effect on the probability that a number is evil.

If you wanted the probability that a particular partial sum is 666, this is a surprisingly difficult value to compute exactly, but not that bad. You can count the ways n nonnegative integers can add up to 666, or any integer. Then use inclusion-exclusion to determine the number of ways none of these nonnegative integers is over 9.

[imfatandugly]

phzon, thanks again, your input is always spot on. Any idea how to approach this for continued fractions?

[pzhon]

[ QUOTE ]
phzon, thanks again, your input is always spot on. Any idea how to approach this for continued fractions?

[/ QUOTE ]
Honestly, I'd start with a Monte Carlo method. Choose random numbers to about 1000 digits of precision, and determine whether 666 is a partial sum. Simple continued fractions present a lot of technical difficulties for this type of analysis. It's much more of a pain than dealing with the decimal digits.

As k->infinity, I believe the probability that a random number in [0,1] has k as a partial sum of the scf coefficients is 0. That's because the expected value of the nth coefficient is infinite, as the probability that the value is t is about c/t^2. For a more exact limiting distribution, see this exposition.

[imfatandugly]

[ QUOTE ]

As k->infinity, I believe the probability that a random number in [0,1] has k as a partial sum of the scf coefficients is 0. That's because the expected value of the nth coefficient is infinite, as the probability that the value is t is about c/t^2. For a more exact limiting distribution, see this exposition.

[/ QUOTE ]

I thought the majority of partial quotients are 1's and 2's...and the probability that a given partial quotient is n drops off rather quickly as n gets large. So intuitively, your summing a bunch of small numbers together...it would be hard to continually "miss" the sum your looking for.