[math-fun] Re: Number of ones in the binary expansion of 3^n
At 10:36 PM 12/3/02 -0500, you wrote:
I saw your name listed by information about the number of ones in the binary expansion of 3^n. Do you know any way of getting an analytic formula or references to any material relating to a formula for this?
Gershon Bialer I assume you are talking about my credit on Sloane's Encyclopedia of Integer Sequences, sequence A011754. I had written a program to display the powers of 3 as a bit-raster (a rather interesting display, it turns out) and it was cheap to count the ones. So I did, and it turned out that Sloane didn't have that one, so I got credit.
If you actually look at the bit-map (this is probably a three-line program in Mathematica, or you can look at the picture in the given reference at EIS), you will see why I think there will be no easy formula for this sequence. I'd bet that the cheapest way to calculate the nth element of the sequence will always be to actually compute 3^n and just count. I have taken the liberty of cc-ing this answer to a list of recreational math enthusiasts, one of whom may have more insight. -A
In Mathematica, Table[Apply[Plus, IntegerDigits[3^n, 2]], {n, 0, 50}] 1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15... I doubt the claim "a(n)/n seems to tend to 1/2" in A011754, so I ran a check out to 3^20000. Out of the first 20000 data points: Mean = .793084, Median = .792596, Mode = .8 In the range 10000 to 20000 Min[a(n)/n] = .772763 Max[a(n)/n] = .813410 Since the data is strongly bounded away from 1/2, I doubt very much that it could be the limit. --Ed Pegg Jr, www.mathpuzzle.com --- "Allan C. Wechsler" <acw@alum.mit.edu> wrote:
At 10:36 PM 12/3/02 -0500, you wrote:
I saw your name listed by information about the number of ones in the binary expansion of 3^n. Do you know any way of getting an analytic formula or references to any material relating to a formula for this?
Gershon Bialer I assume you are talking about my credit on Sloane's Encyclopedia of Integer Sequences, sequence A011754. I had written a program to display the powers of 3 as a bit-raster (a rather interesting display, it turns out) and it was cheap to count the ones. So I did, and it turned out that Sloane didn't have that one, so I got credit.
If you actually look at the bit-map (this is probably a three-line program in Mathematica, or you can look at the picture in the given reference at EIS), you will see why I think there will be no easy formula for this sequence. I'd bet that the cheapest way to calculate the nth element of the sequence will always be to actually compute 3^n and just count.
I have taken the liberty of cc-ing this answer to a list of recreational math enthusiasts, one of whom may have more insight.
a(n)/n tends to Log[3]/(2 Log[2]) = 0.792481 The Sum over the Length tends to 1/2. --Ed Pegg Jr. --- ed pegg <ed@mathpuzzle.com> wrote:
In Mathematica, Table[Apply[Plus, IntegerDigits[3^n, 2]], {n, 0, 50}]
1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15...
I doubt the claim "a(n)/n seems to tend to 1/2" in A011754, so I ran a check out to 3^20000. Out of the first 20000 data points: Mean = .793084, Median = .792596, Mode = .8
In the range 10000 to 20000 Min[a(n)/n] = .772763 Max[a(n)/n] = .813410
Since the data is strongly bounded away from 1/2, I doubt very much that it could be the limit.
--Ed Pegg Jr, www.mathpuzzle.com
--- "Allan C. Wechsler" <acw@alum.mit.edu> wrote:
At 10:36 PM 12/3/02 -0500, you wrote:
I saw your name listed by information about the number of ones in the binary expansion of 3^n. Do you know any way of getting an analytic formula or references to any material relating to a formula for this?
Gershon Bialer I assume you are talking about my credit on Sloane's Encyclopedia of Integer Sequences, sequence A011754. I had written a program to display the powers of 3 as a bit-raster (a rather interesting display, it turns out) and it was cheap to count the ones. So I did, and it turned out that Sloane didn't have that one, so I got credit.
If you actually look at the bit-map (this is probably a three-line program in Mathematica, or you can look at the picture in the given reference at EIS), you will see why I think there will be no easy formula for this sequence. I'd bet that the cheapest way to calculate the nth element of the sequence will always be to actually compute 3^n and just count.
I have taken the liberty of cc-ing this answer to a list of recreational math enthusiasts, one of whom may have more insight.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15...
I doubt the claim "a(n)/n seems to tend to 1/2" in A011754...
More likely, a(n)/n should tend to log_2(3)/2 = 0.79248+, since a bit is equally likely to be 0 or 1. (Well, the first and last bits are ones; I meant the other bits.) -- Don Reble djr@nk.ca
participants (3)
-
Allan C. Wechsler -
Don Reble -
ed pegg