All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Hexadecimal Hinder (Posted on 2016-06-19) Difficulty: 3 of 5
x is a randomly chosen hexadecimal real number on the interval (0, (10)16)

Determine the probability of each of the following:

(i) x and 3x have the same first digit.

(ii) x and x3 have the same first digit.

(iii) x3 and 3x have the same first digit.

(iv) x, x3 and 3x have the same first digit.

*** “First digit” denotes the first nonzero digit of the number when expressed in hexadecimal form.

No Solution Yet Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution part (iii) solution | Comment 4 of 6 |
(iii)

The first digit of x^3 goes through its entire cycle infinitely many times as x approaches 0 from the right. So lets consider a point where none of the cycles is cut off (a fraction of a cycle), as each cycle will have the same set of probabilities. The hex value 0.1 (1/16 in decimal) is at the end of the last (rightmost, highest) cycle in this infinite set. All the cycles will have the same probabilities. And further, 3^x will all begin with hex digit 1 in that range, as was previously said in part (i) for all x lower than  .A1849C... in hex.

So what amount of the number line below .1 hex has x^3 with 1 as its first non-zero digit?

In every range of x = 1 to x = 10 hex, (and its images .1 to 1, etc.), cuberoot(2)/15 decimal is the fraction occupied by numbers whose cube root starts with 1 in hex. This fraction is  .08399473665965822....  The portion of the number line in question is 1/16 of 1 unit, so that occupied by these numbers whose cube begins with 1 is  .00524967104122864.  Remember that since this is the actual portion of number line occupied, it still has to be divided by 16 at the end, together with all the other addends, to get the probability sought.

So we've found the portion of the number line below .1 hex that fits the criterion. The rest of the line from .1 to 10 hex now has to be evaluated and added in. It starts with a segment in which there is indeed a match, ending where x^3 no longer starts with 1 or where 3^x no longer starts with 1, whichever comes first.

It sounds like this calls for a computer program to keep track of the first digit changes up to 10 hex = 16 decimal and add in the portions where the digits match.


DefDbl A-Z
Dim crlf$, pwrref

Private Sub Form_Load()
 Form1.Visible = True
 
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 digx3 = 1: dig3x = 1
 pwrx3 = -3: pwr3x = 0
 x = 1 / 16
 valx3 = x ^ 3: val3x = 3 ^ x
 hexx3$ = hexreal(valx3): hex3x$ = hexreal(val3x)
 Text1.Text = Text1.Text & hexx3 & "  " & hex3x & crlf
 Text1.Text = Text1.Text & hexreal(digx3 * 16 ^ pwrx3) & " " & hexreal(dig3x * 16 ^ pwr3x) & crlf & crlf
 Do
   DoEvents
   newpwrx3 = pwrx3
   newdigx3 = digx3 + 1: If newdigx3 > 15 Then newdigx3 = newdigx3 - 15: newpwrx3 = newpwrx3 + 1
   newpwr3x = pwr3x
   newdig3x = dig3x + 1: If newdig3x > 15 Then newdig3x = newdig3x - 15: newpwr3x = newpwr3x + 1
   newvalx3 = newdigx3 * 16 ^ newpwrx3
   newval3x = newdig3x * 16 ^ newpwr3x
   newxForx3 = newvalx3 ^ (1 / 3)
   newxFor3x = Log(newval3x) / Log(3)
   nextx = newxForx3: used$ = "x3"
   If newxFor3x < nextx Then nextx = newxFor3x: used$ = "3x"
   If newxFor3x = newxForx3 Then used$ = "x33x"
   If 16 < nextx Then nextx = 16: used$ = "mx"
   span = nextx - x
   If digx3 = dig3x Then
     tot = tot + span: ct = ct + 1
     Text1.Text = Text1.Text & x & " " & hexreal(x) & "  "
     Text1.Text = Text1.Text & nextx & "  " & hexreal(nextx)
     Text1.Text = Text1.Text & "               " & span & crlf
     Text1.Text = Text1.Text & val3x & " " & hexreal(val3x) & "  "
     Text1.Text = Text1.Text & valx3 & " " & hexreal(valx3) & crlf
     Text1.Text = Text1.Text & 3 ^ nextx & " " & hexreal(3 ^ nextx) & "  "
     Text1.Text = Text1.Text & nextx ^ 3 & " " & hexreal(nextx ^ 3) & crlf & crlf
   End If
   x = nextx
   valx3 = x ^ 3: val3x = 3 ^ x
   hexx3$ = hexreal(valx3)
   digx3 = InStr("123456789abcdef", firstdig(valx3))
   pwrx3 = pwrref
   If InStr(used, "x3") > 0 Then
     digx3 = newdigx3
     pwrx3 = newpwrx3
   End If
   hex3x$ = hexreal(val3x)
   dig3x = InStr("123456789abcdef", firstdig(val3x))
   pwr3x = pwrref
   If InStr(used, "3x") > 0 Then
     dig3x = newdig3x
     pwr3x = newpwr3x
   End If
 Loop Until Abs(nextx - 16) < 0.000000000001
 
 Text1.Text = Text1.Text & crlf & ct & crlf & tot & crlf
  
End Sub

Function firstdig$(n)
  s$ = hexreal$(n)
  hexpt = InStr(s, ".")
  For i = 1 To Len(s$)
    If InStr("123456789abcdef", Mid(s, i, 1)) > 0 Then Exit For
  Next i
  firstdig$ = Mid(s, i, 1)
  pwrref = hexpt - i - 1: If pwrref < 0 Then pwrref = pwrref + 1
End Function

Function hexreal$(n)
  intpart = Int(n)
  fracpart = n - intpart
  h$ = "."
  While intpart > 0
    q = Int(intpart / 16)
    r = intpart - q * 16
    intpart = q
    h = Mid("0123456789abcdef", r + 1, 1) + h
  Wend
  While fracpart > 0
    m = fracpart * 16
    d = Int(m)
    fracpart = m - d
    h = h + Mid("0123456789abcdef", d + 1, 1)
  Wend
  hexreal$ = h
End Function

Function mform$(x, t$)
  a$ = Format$(x, t$)
  If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
  mform$ = a$
End Function


The results take some explaining.  There are three lines to each segment so we'll take one at a time. Let's take the first segment below:

In decimal the first valid segment extends from .0625 to 0.078745... (note E-02 means x10^-2). In hex that's .1 to .1428a....
The last number on line one is the span in decimal, i.e., the space occupied on the number line: 0.078745... - .0625 = 0.016245....  There turn out to be 18 such segments and the total span is shown at the bottom.

Line 2 shows the values at the start of the span: 3^x = 1.07107548307291 decimal or 1.123200bb58774 hex and x^3 = 0.000244140625 decimal or .001 hex.

The last of the three lines shows the values that terminate the segment. In this case it's that the value of x^3 becomes .002 in hex at the end of the interval.  Note that there are rounding problems throughout.  Here, the extraneous zeros and digit 6 in .0020000000000006 don't upset the programming too much.  Programming had to be done to work around in such cases as the last of the segments below, where d00000 is converted as cfffff.ffffff78 and e00000 as  dfffff.ffffff88: the first a seeming mismatch to d0f.957ffd96468, and the second a seeming match to d3d.09c7e740fb.


0.0625 .1  7.87450656184296E-02  .1428a2f98d728c               1.62450656184296E-02
1.07107548307291 1.123200bb58774  0.000244140625 .001
1.09036259486235 1.172200c5b729e  0.00048828125 .0020000000000006
0.157490131236859 .285145f31ae516  0.198425131496025  .32cbfd4a7adc7a               4.09350002591658E-02
1.18889058827495 1.305b223329c27  0.00390625 .01
1.24357747691624 1.3e5b17f165bef  0.0078125 .020000000000002
0.39685026299205 .6597fa94f5b8f4  0.5  .8               0.10314973700795
1.54648494109336 1.8be66fe5c0a1f  0.0625 .10000000000001
1.73205080756888 1.bb67ae8584caa  0.125 .2
2.0800838230519 2.14805f98f253  2.09590327428938  2.188d1df2a6f82               1.58194512374803E-02
9.82770707891505 9.d3e49c729b9a  9 9.
10 9.ffffffffffff8  9.2069059840103 9.34f7ca62abc2
2.15443469003188 2.278908270e09e  2.18265833864414  2.2ec2b266d179e               2.82236486122542E-02
10.6641582839993 a.aa0646fd24fd  10 a.0000000000008
11 b.  10.3981787011419 a.65ef0a135e4
2.22398009056932 2.3956c25bf348a  2.26185950714291  2.430939835353c               3.78794165735994E-02
11.510870586235 b.82c86a2c5e228  11 a.ffffffffffff
12 b.ffffffffffff  11.5716923061382 b.925a6d4e3d06
2.28942848510666 2.4a17fc36105ea  2.33471751947279  2.55b00c1f88ace               0.045289034366129
12.3690114459331 c.5e7788bc21db  12 c.
13 d.  12.7263254917658 c.b9f077a962a28
2.35133468772076 2.59f111f1b605c  2.40217350273288  2.66f4d7b98e344               5.08388150121224E-02
13.2395052594758 d.3d503778ab278  13 c.ffffffffffff
14 e.  13.8615921511138 d.dc914d9f86208
2.41014226417523 2.68ff155b570a8  2.46497352071793  2.77088130fd4e4               5.48312565426974E-02
14.1231021770879 e.1f839fd0a8b88  14 d.fffffffffffe8
15 e.ffffffffffff8  14.9774119479579 e.fa37ab5f32dc8
2.46621207433047 2.7759acac3feba  2.51984209978975  2.85145f31ae516               5.36300254592765E-02
15.0204242456681 f.053a85fb30a3  15 e.fffffffffffe8
15.9319973076973 f.ee9760248517  16 10.
2.52371901428583 2.86127306a6a7a  3.15464876785729  3.27970fc850518               0.630929753571457
16 f.ffffffffffff8  16.0739642992686 10.12ef53066e23
32 1f.fffffffffffe  31.394461522009 1f.64fb6e288f1c
3.1748021039364 3.2cbfd4a7adc78  3.52371901428583  3.86127306a6a7a               0.348916910349431
32.7164040647631 20.b76641bce0fc  32 1f.fffffffffffe
48 2f.fffffffffffe  43.7525943313296 2b.c0aa05a83738
3.63424118566428 3.a25da15e344fc  3.78557852142874  3.c91bac89f9fb6               0.151337335764465
54.1968086954604 36.32620dfe9216  48 2f.fffffffffffc
64 3f.fffffffffffa  54.2496295100315 36.3fe7b835b3b4
7.57115704285749 7.92375913f3f6c  8  7.ffffffffffffc               0.428842957142511
4096 fff.fffffffffc8  433.997036080252 1b1.ff3dc1ad9da
6560.99999999999 19a0.fffffffff9  512 1ff.ffffffffffd
8.20208679642895 8.33bbf5d59da08  8.57115704285749  8.92375913f3f68               0.369070246428542
8191.99999999999 1fff.fffffffff4  551.78905571083 227.c9ff8e18bca
12288 2fff.ffffffffe8  629.677764111656 275.ad81f2e5f74
11.7258058107148 b.b9ce68dc4448  11.8661198063047  b.ddba07127f288               0.140313995589965
393215.999999999 5ffff.fffffffcc  1612.23406396067 64c.3beb9da0444
458751.999999999 6ffff.fffffffcc  1670.8066172931 686.ce7e788e46
14.8804545785721 e.e16578a494998  14.930044627269  e.ee176799f0da               4.95900486969294E-02
12582912 bfffff.ffffff9  3294.94823194994 cde.f2bf543dff8
13287449.4577502 cac019.752f1e08  3328 cff.fffffffffe8
14.9533125909019 e.f40c4b40c9f28  15.020768574162  f.055116dacf7a               6.74559832600874E-02
13631488 cfffff.ffffff78  3343.58398423117 d0f.957ffd96468
14680064 dfffff.ffffff88  3389.03820653283 d3d.09c7e740fb


There are 18  segments totalling 2.63329868149249 on the number line.

We need to add in that .00524967104122864 calculated at the beginning for the stretches before .1 hex. The total is  2.638548352533718, which is to be divided by 16, giving  .1649092720333574 as the probability sought for part (iii).


  Posted by Charlie on 2016-06-20 09:01:51
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information