Connection between integer sequence and binary counting?
mike3
Consider this procedure to generate an infinite list of integer
strings. Start with 2. This is the first string. Now add 1 to it to
get 3. Put this at the end of the string. Now we have a string 2, 3.
Now repeat with this string. It is the second string. Add 1 to each
element, to get 3, 4. Put this at the end of the string to get 2, 3,
3, 4. This is the third string. And keep repeating this process.
This gives the following strings:
n = 1: 2
n = 2: 2, 3
n = 3: 2, 3, 3, 4
n = 4: 2, 3, 3, 4, 3, 4, 4, 5
n = 5: 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
...
Apparently, each row is the number of "1" bits in a binary counting
sequence given by counting up to 2^(n+1) - 1 from 2^(n+1) - 2^(n-1),
using information from the oeis.org website (enter any row shown
above, especially the last one, in there and you'll find some stuff
about "number of 1s" function). But why is this? How does the
procedure I described mimic binary counting filtered by the "number of
1s" function?
Tim Little
> But why is this? How does the procedure I described mimic binary
> counting filtered by the "number of 1s" function?
It's easier to see if you count from 0 to 2^(n-1) - 1 instead:
(empty string)
0 1
00 01 10 11
000 001 100 101 110 111
... etc.
Each line, you prepend a 0 for the first half and 1 for the second
half. Obviously then, the number of 1 bits in the first half half is
unchanged from the previous line, and the second half is one greater.
You have started with 2, which we can think of as prepending the
binary digits 11 to everything in the above sequences:
11
110 111
1100 1101
11000 11001 11010 11011 11100 11101 11110 11111
... etc.
The binary numbers remain consecutive, and so are counting in some
range. Prepending "11" corresponds to adding 3*2^(n-1), which gives
the range described once you simplify the formula.
--
Tim
mike3
Hmm. I think I see how this works now. If we started with
n = 0: 0
and indexed each term starting from 0, we'd have
n = 1: 0 1
n = 2: 0 1 1 2
n = 3: 0 1 1 2 1 2 2 3
n = 4: 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4
...
Now, j = 0 has 0 1 bits. We increment that by 1 to get the
value for j = 1. This has a single 1 bit. Now the next 2
j-values, j = 2 and j = 3, are like j = 0 and j = 1 but
with a 1 bit prepended. So the number of 1 bits in them
is equal to the number of 1 bits in j = 0 and j = 1 plus 1.
Then for the next set of js, j = 4, 5, 6, 7, that is like
the previous 4 js, only with yet another 1 bit prepended.
So, the number of 1 bits in them would be equal to the number
of 1 bits in j = 0, 1, 2, 3, plus 1. And we can keep on
going, and this is just the process described in my original
post...
Now it makes sense. Thanks for the aid.
mike3
(P.S. "j" is the horizontal index.)
Butch Malahide
Moreover, if you take residues modulo 2, you get
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 . . .
a rather famous sequence of 0's and 1's.
Gottfried Helms
>
> Moreover, if you take residues modulo 2, you get
> 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 . . .
> a rather famous sequence of 0's and 1's.
To give a hint: ...
- - - --- --- --- - - - - - - --- --- --- - - - ... ;-)
<G>
Gottfried Helms
Yepp. An additional impulse.
Assume for n-> the sequence numbers as coefficients of a powerseries in
x
So
f(x) = 0 + 1x + 1x^2 + 2x^3 + 1x^4 + 2x^5 + 2x^6 + 3x^7 + ...
and then
g(x,y) = <using the definition of f(x) and only that terms where y=coefficient>
so
g(x,1) = 1 x + 1 x^2 + 1 x^4 + 1 x^8 + ...
g(x,2) =1/2*( 2 x^3 + 2 x^5 + 2 x^6 + 2 x^10 + ...)
g(x,3) =1/3*( 3 x^7 + 3 x^11 + 3 x^12 + 3 x^14 + ...)
...
Now, g(1/2,1)~ 0.816421509022 is known to be transcendental.
Also we know, that
h(1/2) = g(1/2,1) + g(1/2,2) + g(1/2,3) + ... = 1/(1-1/2) = 2
which is even integer.
Question: are all g(1/2,k), k=1..inf transcendental?
Using Pari/GP:
g(1/2,1) = 0.816421509022...
g(1/2,2) = 0.175061285686...
g(1/2,3) = 0.00848655779265...
g(1/2,4) = 0.0000306470339388...
g(1/2,5) = 0.000000000465668422876
----------------------------------
1.00000000000.......
Gottfried Helms
mike3
Ah yes, the Thue-Morse sequence, with bits all
concatenated together :) I was wondering if it
could be found here given the similarity of
this process to the construction process for the
original sequence.
Actually, this makes sense, since addition mod 2
is equivalent to XOR, and taking a binary sequence
and applying a bitwise XOR of all ones with it, which
the "increment" would be equivalent to, is the same
as negating it (taking bitwise NOT). Thus, when
viewed mod 2, the process is equivalent to the
Thue-Morse process.
mike3
that is, the TM sequence, oops.
mike3
? Equals 2? But below you have it equaling 1:
Gottfried Helms
> On Jan 22, 8:04 am, Gottfried Helms <he...@uni-kassel.de> wrote:
>> so
>> g(x,1) = 1 x + 1 x^2 + 1 x^4 + 1 x^8 + ...
>> g(x,2) =1/2*( 2 x^3 + 2 x^5 + 2 x^6 + 2 x^10 + ...)
>> g(x,3) =1/3*( 3 x^7 + 3 x^11 + 3 x^12 + 3 x^14 + ...)
>> ...
>>
>> Now, g(1/2,1)~ 0.816421509022 is known to be transcendental.
>> Also we know, that
>>
>> h(1/2) = g(1/2,1) + g(1/2,2) + g(1/2,3) + ... = 1/(1-1/2) = 2
>>
>> which is even integer.
>>
>
> ? Equals 2? But below you have it equaling 1:
Ooops - one index shift in the h(1/2)-formula, sorry.
Maybe I had somehow the g(1/2,0)-element in mind and didn't check
this really and ended in confusing the indexes...
Gottfried
mike3
Thanks for the correction.