A003602: Fractal
1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, 1, 9, ...
Fractals! Remove every second number, or alternately and equivalently, remove the first appearance of each positive integer. That's right, alternating terms are just the integers. What do you have left? 1, 1, 2, 1, 3, 2, 4, 1, ... The same sequence! Which means if you remove every second number again, you get the same sequence. Over and over. But this also means that if you look only at every fourth term, starting at the fourth number, you get the same sequence. And eighth, etc. Sk[n]=S[n*2^k]=S[n], as long as we start indexing from 1.
How fast does this grow? Well, it keeps going back to 1, so let's ask instead how fast its sum grows. Since every second term is the integers, the sum T[n=2k] is at least k^2/2+k/2. And since the other terms are the sequence, T[n=2k] = k^2/2 + k/2 + T[k], and T[n=2k+1] = k + 1 + T[2k].
To make it easy, we'll just find T[n=2^k]=(n/2)^2/2+(n/2)/2+T[n/2]. It happens to be 2^(k-1) + 2^(2k-1)/3 + 1/3. Divide by 2^k to get the average of the first n terms: Ave[n]=1/2+(1/2)^n/3+n/6~=n/6.
What if instead we said S[n*3^k]=S[n], filling in unused numbers with ascending integers as with A003602? We'd get 1,2,1,3,4,2,5,6,1,7,8,3,9,10,4,11,12,2,13,14,5,... with similar properties. Its average value? Ave[n=3k]~=((2k)^2/2/3k+Ave[k]/3=(2/3)(n/3)+(1/3)Ave[n/3]. That's (2/9)(9/8)n = n/4.
In general, then. For the S_z[n*z^k]=S_z[n] function, the average value is Ave[n=zk]=n*(z-1)^2/2z^2+Ave[n/z]/z=(n/2)(z-1)^2/(z^2-1).
1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, 1, 9, ...
Fractals! Remove every second number, or alternately and equivalently, remove the first appearance of each positive integer. That's right, alternating terms are just the integers. What do you have left? 1, 1, 2, 1, 3, 2, 4, 1, ... The same sequence! Which means if you remove every second number again, you get the same sequence. Over and over. But this also means that if you look only at every fourth term, starting at the fourth number, you get the same sequence. And eighth, etc. Sk[n]=S[n*2^k]=S[n], as long as we start indexing from 1.
How fast does this grow? Well, it keeps going back to 1, so let's ask instead how fast its sum grows. Since every second term is the integers, the sum T[n=2k] is at least k^2/2+k/2. And since the other terms are the sequence, T[n=2k] = k^2/2 + k/2 + T[k], and T[n=2k+1] = k + 1 + T[2k].
To make it easy, we'll just find T[n=2^k]=(n/2)^2/2+(n/2)/2+T[n/2]. It happens to be 2^(k-1) + 2^(2k-1)/3 + 1/3. Divide by 2^k to get the average of the first n terms: Ave[n]=1/2+(1/2)^n/3+n/6~=n/6.
What if instead we said S[n*3^k]=S[n], filling in unused numbers with ascending integers as with A003602? We'd get 1,2,1,3,4,2,5,6,1,7,8,3,9,10,4,11,12,2,13,14,5,... with similar properties. Its average value? Ave[n=3k]~=((2k)^2/2/3k+Ave[k]/3=(2/3)(n/3)+(1/3)Ave[n/3]. That's (2/9)(9/8)n = n/4.
In general, then. For the S_z[n*z^k]=S_z[n] function, the average value is Ave[n=zk]=n*(z-1)^2/2z^2+Ave[n/z]/z=(n/2)(z-1)^2/(z^2-1).
posted by Guy Srinivasan at 9:49 AM
0 Comments:
Post a Comment
<< Home