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

Home > Numbers
West Side Story (Posted on 2004-02-15) Difficulty: 4 of 5
Does 9 appear as the leftmost digit in the decimal representation of any power of 2?

Does 7 appear as the leftmost digit in the decimal representation of any power of 37?

Is it possible to find a power of any counting number that has a given digit as its leftmost digit?

Also, is it possible to find a power of any counting number that begins with a given series of digits (e.g., is there a power of 24 that begins with 937)?

Prove that this is possible, or give a counter-example.

Bonus: What percentage of the powers of 2 have 1 as their leftmost digit?

Note: In finding the powers of "any counting number," exclude powers of ten, whose leftmost digit is always 1.

No Solution Yet Submitted by DJ    
Rating: 3.2500 (8 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution | Comment 1 of 8
2^53 = 9007199254740992 (thus beginning with 9)

37^35 is 7710105884424969623139759010953858981831553019262380893 (thus beginning with 7)

One would expect that the leading digits of powers of numbers would follow Benford's Law, a topic that came up in discussing Bascule's Book. It was problematic when applied there, due to the limited sizes of books, but here we have an unlimited number of powers of a given number.

The following program evaluates as many powers of 2 and of 37 as the internal representation will allow and compares the distribution of leading digits to Benford's Law, which states that the fraction of numbers that have leading digit n is log(n+1)/log(n) using base-10 logs for base-10 number representations.

DEFDBL A-Z
ON ERROR GOTO fin
CLS
DIM ct(10)
n = 1
DO
  pwr = pwr + 1
  n = 2 * n
  n$ = LTRIM$(STR$(n))
  d = VAL(LEFT$(n$, 1))
  ct(d) = ct(d) + 1
  IF d = 9 AND pwr < 60 THEN PRINT pwr, n
  tot = tot + 1
LOOP
fin:
FOR i = 1 TO 9
 PRINT USING \"###.## \"; tot * (LOG(i + 1) - LOG(i)) / LOG(10);
NEXT
PRINT
FOR i = 1 TO 9: PRINT USING \" ### \"; ct(i); : NEXT
PRINT : PRINT tot
RESUME fini
fini:
PRINT : PRINT


ON ERROR GOTO fin2
n = 1: pwr = 0: tot = 0: ERASE ct
DO
  pwr = pwr + 1
  n = 37 * n
  n$ = LTRIM$(STR$(n))
  d = VAL(LEFT$(n$, 1))
  ct(d) = ct(d) + 1
  IF d = 7 AND pwr < 60 THEN PRINT pwr, n
  tot = tot + 1
LOOP
fin2:
FOR i = 1 TO 9
 PRINT USING \"###.## \"; tot * (LOG(i + 1) - LOG(i)) / LOG(10);
NEXT
PRINT
FOR i = 1 TO 9: PRINT USING \" ### \"; ct(i); : NEXT
PRINT : PRINT tot
RESUME fini2


fini2:
PRINT
FOR i = 1 TO 9
 PRINT USING \"###.## \"; 100 * (LOG(i + 1) - LOG(i)) / LOG(10);
NEXT

END
For the first 1023 powers of 2, the statistics are:

--------

307.95 180.14 127.81 99.14 81.00 68.49 59.33 52.33 46.81
307 181 127 100 81 70 57 55 45


where the top line shows the theoretic number based on 1023 trials, and the bottom line shows the number actually found, for the leading digits 1 through 9.

For the first 196 powers of 37, the distribution is:

59.00 34.51 24.49 18.99 15.52 13.12 11.37 10.03 8.97
62 31 27 18 17 15 8 8 10

------------
I'll leave to others to do Chi-square tests to see the goodness of fit, but it looks good to me.

As specifically applied to powers of given numbers, the distribution law (which also applies to not just the leftmost single digit, but the leftmost n digits) depends on the property of the logarithm of the base number being not only irrational, but normal. (A description of that is at http://mathworld.wolfram.com/NormalNumber.html).

The logarithm of a power of a number is the logarithm of that number multiplied by the power. Here are the common logarithms of the first few powers of 2:

1 0.301029995663981195213738894724492
2 0.602059991327962390427477789448986
3 0.903089986991943585641216684173479
4 1.204119982655924780854955578897972
5 1.505149978319905976068694473622465
6 1.806179973983887171282433368346958
7 2.107209969647868366496172263071451
8 2.408239965311849561709911157795945
9 2.709269960975830756923650052520438
10 3.010299956639811952137388947244931
11 3.311329952303793147351127841969424
12 3.612359947967774342564866736693917
13 3.91338994363175553777860563141841
14 4.214419939295736732992344526142904
15 4.515449934959717928206083420867397
16 4.81647993062369912341982231559189
17 5.117509926287680318633561210316383
18 5.418539921951661513847300105040876
19 5.719569917615642709061038999765369
20 6.020599913279623904274777894489862
21 6.321629908943605099488516789214356
22 6.622659904607586294702255683938849
23 6.923689900271567489915994578663342
24 7.224719895935548685129733473387835
25 7.525749891599529880343472368112328
26 7.826779887263511075557211262836821
27 8.127809882927492270770950157561315
28 8.428839878591473465984689052285808
29 8.729869874255454661198427947010301
30 9.030899869919435856412166841734794

----
Well actually, these are only approximations to numbers that go on forever.

Seeking, say, a 9 as the leading digit of the power is equivalent to asking that the mantissa (that's the part to the right of the decimal in the logarithm), be greater than or equal to .95424250943932487459005580651023....

If the common logarithm of 2 is normal, rather than contrived so that when you multiply by various integers you get an uneven distribution of numbers after the decimal, you will be getting the equivalent of Benford's Law. In fact, the multiplication process may make even such contriving impossible, and make it not even necessary for the log(2) to be normal. I'll leave that for someone else to show, if it's true.

But this applies to sets of leading digits as well as single digits. For a power of 24 to begin 937, the mantissa of its log should be between log(9.37) and log(9.38) (again, common logarithms), which is, between .971739590887778263027576732122158 and .972202838379064460075086782543197. Doing the arithmetic, about 1 out of 2159 powers of 24 (or any number other than a power of 10) should begin 937.

Thus this UBASIC program finds powers of 24 that start with 937 if they are below 24^80000:

5 point 7
10 A=log(9.38)/log(10)
20 B=log(9.37)/log(10)
40 I=1:Lps=log(24)/log(10):Lp2=Lps
50 for I=2 to 80000
60 Lp2=Lp2+Lps
70 Mant=Lp2-int(Lp2)
80 if Mant<A and Mant>B then print I,Lp2,using(1,15),10^Mant:HCtr=HCtr+1
90 next
100 print HCtr

--------
It finds the following:

8198 11314.971759551746176031333127739615413 9.370430669854714
9997 13797.971783390925411293637140523656415 9.370945043204185
11796 16280.971807230104646555941153307697416 9.371459444789278
13595 18763.971831069283881818245166091738418 9.371973874611544
15394 21246.971854908463117080549178875779419 9.372488332672533
17193 23729.97187874764235234285319165982042 9.373002818973794
18992 26212.971902586821587605157204443861422 9.373517333516877
20791 28695.971926426000822867461217227902423 9.374031876303334
22590 31178.971950265180058129765230011943425 9.374546447334714
24389 33661.971974104359293392069242795984426 9.375061046612568
26188 36144.971997943538528654373255580025427 9.375575674138447
27987 38627.972021782717763916677268364066429 9.376090329913900
29786 41110.97204562189699917898128114810743 9.376605013940479
31585 43593.972069461076234441285293932148431 9.377119726219735
33384 46076.972093300255469703589306716189433 9.377634466753218
35183 48559.972117139434704965893319500230434 9.378149235542480
36982 51042.972140978613940228197332284271436 9.378664032589071
38781 53525.972164817793175490501345068312437 9.379178857894542
40580 56008.972188656972410752805357852353438 9.379693711460445
49383 68158.971749444240230660566460986268355 9.370212590681410
51182 70641.971773283419465922870473770309357 9.370726952059808
52981 73124.971797122598701185174486554350358 9.371241341673171
54780 75607.971820961777936447478499338391359 9.371755759523049
56579 78090.971844800957171709782512122432361 9.372270205610992
58378 80573.971868640136406972086524906473362 9.372784679938551
60177 83056.971892479315642234390537690514364 9.373299182507275
61976 85539.971916318494877496694550474555365 9.373813713318715
63775 88022.971940157674112758998563258596366 9.374328272374421
65574 90505.971963996853348021302576042637368 9.374842859675943
67373 92988.971987836032583283606588826678369 9.375357475224833
69172 95471.972011675211818545910601610719371 9.375872119022639
70971 97954.972035514391053808214614394760372 9.376386791070915
72770 100437.972059353570289070518627178801373 9.376901491371209
74569 102920.972083192749524332822639962842375 9.377416219925073
76368 105403.972107031928759595126652746883376 9.377930976734058
78167 107886.972130871107994857430665530924378 9.378445761799714
79966 110369.972154710287230119734678314965379 9.378960575123594
37

------
It shows i, common log(24^i) (to a limited accuracy), and the antilog of the mantissa of that logarithm. At the end it shows that 37 numbers satisfying the criterion have been found in the 80000 powers of 24. That's about 1 in 2162, close to the 1 in 2159 expected on average.

The purpose of the antilog of the mantissa of the logarithm is to show the first several digits of the power. Don't trust the last one as is could be rounded up based on the subsequent digit (nor trust the next-to-last if the last is a zero, etc.).

An interesting note is the recurrence of powers at an interval of 1799, due to the first five digits of 24^1799 being "10000". The error does build up, and there is one "correction" power of 8803 (between 40580 and 49383) which power of 24 begins "998989". It was such a "gap" at the beginning of the run that made me extend the search first to 8,000 and then to 80,000 powers of 24. This could be considered a lack of normality in the log of 24--I'm not sure--but as seen here, it doesn't affect the overall distribution in the long run.

But in any event, this gives us a clue to the proof that all sets of beginning digits will eventually be reached. In order for that not to happen, the mantissas would have to constantly cycle in a limited set, repeating every so often. But in order for that to happen, some power of the number in question must also be a power of 10. That is, say in the example of the preceding paragraph, if the match of mantissas every 1799 powers of 24 had been exact, that would have meant that 24^1799 was a power of 10. But that's impossible, as 24 is not a power of ten and is an integer and therefore not a power of a root of 10. Thus, for any integer other than powers of 10, the mantissas of the logarithms of its powers must increase (or decrease) up to a certain point, and then cycle through the unit length at a different offset each time, and thus eventually approaching any point within the unit line to any desired degree of accuracy.
Edited on February 15, 2004, 11:05 am
  Posted by Charlie on 2004-02-15 10:34:43
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 (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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