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

 Slow growing sequence (Posted on 2011-10-20)
Continue this sequence:

0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2...

Starting at the left, as you add terms, when and how big is the largest proportion of each number? For example 3 of the first 5 terms are 1s.

Show that as the sequence is continued indefinitely, no number appears with a proportion greater than 0.

 No Solution Yet Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer exploration and solution Comment 1 of 1

The sequence is Sloane's OEIS's A000120 (http://oeis.org/A000120), the number of 1's in n when n is expressed in binary.

DEFDBL A-Z
maxbit = 20

DIM bit(maxbit)
DIM hiPos(maxbit), hiProp(maxbit), numCt(maxbit)

FOR n = 1 TO 2000000
FOR bPos = 0 TO maxbit
IF bit(bPos) = 0 THEN
bit(bPos) = 1
bitCt = bitCt + 1
EXIT FOR
ELSE
bit(bPos) = 0
bitCt = bitCt - 1
IF bPos = maxbit THEN PRINT "*****": END
END IF
NEXT bPos
numCt(bitCt) = numCt(bitCt) + 1
ratio = numCt(bitCt) / (n + 1)  ' +1 to account for zero
IF ratio > hiProp(bitCt) THEN
hiPos(bitCt) = n
hiProp(bitCt) = ratio
END IF
NEXT n
FOR i = 1 TO maxbit
PRINT i, hiPos(i); hiProp(i)
NEXT

The above was run twice: the first time with the limit of n as 1000000 instead of 2000000, and the second time with the 2000000:

`# of 1's      N   fraction at this N (the max)1             2  .66666666666666662             12  .46153846153846163             52  .35849056603773584             212  .30046948356807515             852  .26377491207502936             3432  .23827556073405187             13736  .21918905146684148             55976  .20415527806063219             223912  .191882561530594510            895656  .18160523503975311            998696  .160110624143258712            999248  .116182252871906813            999376  .06812344090368314            999408  3.177177712027809D-0215            999416  1.150670841100362D-0216            999420  3.117805209216136D-0317            999422  5.943429358739993D-0418            983038  7.12077547279406D-0519            983039  4.069010416666667D-0620            0  0`

Note the exponential D notation used for the smallest numbers, representing the negative powers of 10.

`# of 1's      N   fraction at this N  (example max ratio)                                        shown for #51             2  .66666666666666662             12  .46153846153846163             52  .35849056603773584             212  .30046948356807515             852  .2637749120750293 (225/853--see text)6             3432  .23827556073405187             13736  .21918905146684148             55976  .20415527806063219             223912  .191882561530594510            895656  .18160523503975311            1993384  .170089069597694412            1998152  .138132565424169213            1998736  9.214969253083322D-0214            1998816  4.994704367633455D-0215            1998832  2.163912643027206D-0216            1998840  7.312237441597405D-0317            1998844  1.856071881511573D-0318            1998846  3.326917968208672D-0419            1966078  3.763836549802932D-0520            1966079  2.034505208333333D-06`

The ratios continued to increase from the first run to the second run for the number of 1's being 11 or above, so we can't trust that the maximum ratio has been reached, but for 10 and below, there was no higher ratio seen be increasing the numbers tested between one and two million, so I'd trust those as being the maximum: for example the highest ratio of 5's among the partial sequence is .2637749120750293, occurring when the sequence has reached 853 elements (counting the 0 at the beginning) at N=852 (1101010100), with 225 of them being 5.

In a binary number of b or fewer digits (i.e., b digits with leading zeros allowed), the fraction with a given number, n, of 1's is C(b,n)/2^b, which is

b!/(n!*(b-n)!*2^b).

For a given value of n, the n! in the formula of course remains constant as b increases. At the same time, b!/(b-n)! remains under b^n, thus increasing polynomially, while 2^b of course increases exponentially, leading to the limit of zero for any given number of 1's' proportion in the binary representations.

 Posted by Charlie on 2011-10-20 12:47:42

 Search: Search body:
Forums (0)