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

Home > Numbers > Sequences
Slow growing sequence (Posted on 2011-10-20) Difficulty: 2 of 5
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.)
Solution 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  .6666666666666666
2             12  .4615384615384616
3             52  .3584905660377358
4             212  .3004694835680751
5             852  .2637749120750293
6             3432  .2382755607340518
7             13736  .2191890514668414
8             55976  .2041552780606321
9             223912  .1918825615305945
10            895656  .181605235039753
11            998696  .1601106241432587
12            999248  .1161822528719068
13            999376  .068123440903683
14            999408  3.177177712027809D-02
15            999416  1.150670841100362D-02
16            999420  3.117805209216136D-03
17            999422  5.943429358739993D-04
18            983038  7.12077547279406D-05
19            983039  4.069010416666667D-06
20            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 #5
1             2  .6666666666666666
2             12  .4615384615384616
3             52  .3584905660377358
4             212  .3004694835680751
5             852  .2637749120750293 (225/853--see text)
6             3432  .2382755607340518
7             13736  .2191890514668414
8             55976  .2041552780606321
9             223912  .1918825615305945
10            895656  .181605235039753
11            1993384  .1700890695976944
12            1998152  .1381325654241692
13            1998736  9.214969253083322D-02
14            1998816  4.994704367633455D-02
15            1998832  2.163912643027206D-02
16            1998840  7.312237441597405D-03
17            1998844  1.856071881511573D-03
18            1998846  3.326917968208672D-04
19            1966078  3.763836549802932D-05
20            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
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 (0)
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