login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Some divide-and-conquer sequences with (relatively) simple ordinary generating functions

Some divide-and-conquer sequences with (relatively) simple ordinary generating functions

Version 2004-01-1
Ralf Stephan <ralf(at)ark.in-berlin.de>

Introduction

In the following, about 100 sequences are collected that are generated by ordinary generating functions of form 1/(1-x)^m * sum(k=0, inf, C^k*R(x^2^k)), where m=0,1,2, C is integer, and R is a rational function. That the given recurrences are indeed generated by the mentioned functions (and that most of the sequences are fractal) is clarified in the section below.

For all recurrences, a link into their OEIS entry, as well as, where possible, a mnemonic and a 'closed form' is given. Parentheses around a link means the entry can be derived from the recurrence by an elementary operation like shift. Used abbreviations are [log2(n)] for A000523(n), v2(n) for A007814(n), e1(n) for A000120(n), and e0(n) for A023416(n). Where the parameter is left out, it is understood to be n. Recurrence start value a(0) is always 0.

Of form a(2n) = C*a(n) + P(n), a(2n+1) = Q(n) (1)

Here and thereafter, P and Q are functions of n expressible by a rational generating function, C integer.

Recurrences of form a(2n) = C*a(n) + P(n), a(2n+1) = Q(n)
a(2n) = a(2n+1) = form mnemonic
A007814 a(n)+1 0 v2 2-adic valuation, 2^a(n) divides n
A001511 a(n)+1 1 v2+1 2^a(n) divides 2n
A037227 a(n)+2 1 2v2+1
A088705 a(n)-1 1 1-v2 diff(A000120)
(A059139) a(n)+3 4 3v2+4 hierarchical sequence
(A036987) a(n) [n==0] [n==2^k] n is power of two
A089263 a(n)+1 -1+[n==0] v2-1+[n==2^k] diff(A023416)
A006519 2a(n) 1 2^v2 highest power of 2 div. n
A038712 2a(n)+1 1 2^(v2+1)-1 nim-sum
A061393 3a(n)-2 2 3^v2+1
A085296 3a(n)+3 3 (3^(v2+2)-1)/2-1 Catalan mod 3
A065916 4a(n)+3 7 8*4^v2-1 denominator of a sigma expr.
A035263 -a(n)+1 1 (1-(-1)^v2)/2 v2(2n) mod 2
(A003602) a(n) n (n/2^v2+1)/2 fractal sequence
A000265 a(n) 2n+1 n/2^v2 largest odd divisor of n
A089265 a(n)+1 2n v2+n/2^v2-1 diff(A005576)
A086799 2a(n)+1 2n+1 n+2^v2-1 switch trailing 0s
A038189 a(n) n%2 (1-(-1)^A025480)/2 bit left of lsb/paperfolding seq.
(A082392) a(n) 2^n 2^((n/2^v2-1)/2)2^A025480
A055975 2a(n) (-1)^n (see entry) diff(Gray code)
A002516 2a(n) f(n)* *with f(n)=3n+1/2-(n-5/2)(-1)^n
A045674 a(n)+2^(n-1) 2^n 2n-bead balanced bin. strings
A091512 2a(n)+2n 2n+1 n*v2+n 2^a(n) divides (n)^(n)
A091519 2a(n)+(2n)^2 (2n+1)^2 2n^2-n^2/2^v2

Of form a(2n) = C*a(n) + P(n), a(2n+1) = C*a(n) + Q(n) (2)

The sequences are all partial sums of sequences of the previous form (1), and start with a(0)=0.

The case C=1
Recurrences of form a(2n) = a(n) + P(n), a(2n+1) = a(n) + Q(n)
P(n) Q(n) form mnemonic
A000120 0 1 e1(n) ones-counting function
A023416 1 0 e0(n) zeros-counting function
A070939 1 1 [log2(n)]+1 binary length
(A061313) 2 1 2e0+e1 a stopping problem
A056791 1 2 2e1+e0 binary weight + length
A037861 1 -1 e0-e1
A057427 0 [n==0] [n>0] sign(n)
A000523 1 1-[n==0] [log2(n)]
(A086694) [n==1] 0 runs of 2^k 1s and 0s
A011371 n n n-e1 v2(n!)
A000027 n n+1 n
A080804 n+1 n+2-[n==0] n+[log2(n)] cube subgraphs
A083058 n-1 n n-1-[log2(n)] eigenvalues
A005187 2n 2n+1 2n-e1 v2((2n)!)
A049039 2n-1 2n+1 2n-1-[log2(n)] Connell sequence
A071413 2n -2n-1
A004134 3n 3n+2 3n-e1 denom. in (1-x)^(-1/4)
A050487 3n-2 3n+1 3n-2-[log2(n)] Connell sequence
A005766 n^2 n^2+2n minimum cost addition chain
A069010 0 [n even] runs of ones
A033264 [n odd] 0 counting '10'
A014081 0 [n odd] counting '11'
A033265 1 [n odd] increasing spots in bin. repr.
A056973 [n even] 0 counting '00'
(A037809) [n even] 1 decreasing spots in bin. repr.
A037800 0 [n>0 even] counting '01'
A005811 [n odd] [n even] e1(Gray code of n)
A014082 0 [n=3 mod 4] counting '111'
A014083 0 [n=7 mod 8] counting '1111'
The case C=2
Recurrences of form a(2n) = 2a(n) + P(n), a(2n+1) = 2a(n) + Q(n)
P(n) Q(n) form mnemonic
A053644 0 [n==0] 2^[log2(n)] msb
A062383 0 2[n==0] 2*2^[log2(n)]
(A035327) 1 0 -n-1+2*2^[log2(n)] interchange 0s and 1s
A054429 1 [n==0] -n-1+3*2^[log2(n)] permutation of N
(A010078) 1 2[n==0] -n-1+4*2^[log2(n)] -n in 2's complement
A000027 0 1 n
A005843 0 2 2n
A004754 0 1+[n==0] n+2^[log2(n)] starts '10'
A004755 0 1+2[n==0] n+2*2^[log2(n)] starts '11'
A080079 0 -1+2[n==0] -n+2*2^[log2(n)] longest carry sequence
A004756 0 1+3[n==0] n+3*2^[log2(n)] starts '100'
A079946 0 2+4[n==0] 2n+4*2^[log2(n)] Aronson-like
A003817 1 1 2*2^[log2(n)]-1 a(n-1) OR n
A089262 [n==1] 0 2^flg(n)-2^flg(2/3n)
(A079251) 4-3[n==1] 6-5[n==0] 3*2^flg(n*2/3)+2n-2 Aronson-like
A062050 -1 [n==0] n+1-2^[log2(n)] runs of 1...2^k
A006257 -1 1 2n+1-2^[log2(n)] Josephus problem
A076877 -1 -1+4[n==0] 1+2*2^[log2(n)]
A003188 [n odd] [n even] Gray code
A038554 [n odd] [n>0 even] 'derivative' of n
(A006520) n n+1 part. sums of 2^v2
A080277 2n 2n+1 part. sums of 2^(v2+1)-1
A048724 0 2(-1)^n+1 reversing bin. repr. of -n
Other cases
Recurrences of form a(2n) = Ca(n) + P(n), a(2n+1) = Ca(n) + Q(n)
C P(n) Q(n) mnemonic
A005836 3 0 1 ternary repr. contains no 2
A005824 3 0 2 ternary repr. contains no 1
A081601 3 0 3 3 does not divide C(2k,k)
(A055246) 3 0 6 related to Cantor set
A083904 3 1 0
A000695 4 0 1 Moser-de Bruijn sequence
A001196 4 0 3 double bitters
A065359 -1 0 1 alternating bit sum
A083905 -1 1 0
A030300 -1 1 1 runs of length 2^k
A030301 -1 1 1-[n==0] [log2(n)] mod 2
A068639 -1 n n+1 part. sums of (-1)^v2
A076902 -1 n n+[n==0]
A050292 -1 2n 2n+1 double-free subsets of N
(A079420) -1 2n+1 2n+2-[n==0]
(A022441) -1 9n+3 9n+6-[n==0]
A053985 -2 0 1 replace 2^k with (-2)^k in binary
A063695 -2 2n 2n remove even-pos. bits
A063694 -2 2n 2n+1 remove every 2nd bit
A057300 -2 5n 5n+2 binary counter

Of form a(2n) = C*(a(n)+a(n-1)) + P(n), a(2n+1) = 2C*a(n) + Q(n) (3)

P and Q are functions of n expressible by a rational generating function, C integer. The sequences are all partial sums of sequences of the previous form (2), a(0)=0.

Recurrences of form a(2n) = C(a(n)+a(n-1)) + P(n), a(2n+1) = 2Ca(n) + Q(n)
C P(n) Q(n) mnemonic
A080776 1 [n==1] 0 oscillating sequence
(A060973) 1 0 [n==0]
(A006165) 1 [n==1] [n==0] Josephus problem
(A007378) 1 [n==1] 3[n==0] a(a(n)) = 2n
A000027 1 1 1 n
(A079945) 1 3-2[n==1] 3-3[n==0]
(A059015) 1 n n part. sums of e0
A000788 1 n n+1 part. sums of e1
A078903 1 n-1 n fractal generator
A076178 1 2n-2 2n Legendre pol. expansions
(A061168) 1 2n-1 2n part. sums of [log2(k)]
A001855 1 2n 2n+1 binary insertion sort comparisons
(A003314) 1 2n+1 2n+2 binary entropy
(A033156) 1 2n+2 2n+3
(A067699) 1 2n+2 2n+4 quicksort comparisons
(A077071) 1 2n^2+n 2n^2+3n+1
(A063915) 2 1 1
(A073121) 2 2[n==1] 4[n==0] concerning a regex algorithm
A006581 2 n 0 sum(k AND n-k)
A006582 2 4n-4 6n sum(k XOR n-k)
A006583 2 5n-4 6n sum(k OR n-k)
A022560 2 n^2+n (n+1)^2
(A048641) 2 2*ceil(n/2) n+1 part. sums of Gray code
A005536 -1 n n+1 Koch curve
A087733 -1 n^2+n n^2+2n+1 sum(sum((-1)^v2))

Theory

Lemma. Let A(z) an infinite sum of rational functions of form A(z) = sum (k=0, inf, C^k * B(z^(2^k))), B rational, C integer. Then A(z) generates an integer sequence of divide-and-conquer type satisfying a(0)=0, a(2n) = Ca(n)+b(2n), a(2n+1) = b(2n+1), where b(n) is the sequence generated by B(z).

The summation term with k=0 fills both bisections of a(n) since C^k and 2^k reduce to 1. Any other term contributes only to a(2n) as all exponents to z are even. Moreover, other subsequences from single terms of the sum are increasingly sparse (spread out by a factor of 2), and have values multiplied with C, with respect to each other. This is essentially the reason for the fractality of a(n).

Note the proof of the lemma is easy because having no reference to a(n) in the odd bisection of the recurrence amounts to a cutoff of the recursion, leaving computation of v2(n) steps in the even bisection. Additional insight might be gained from the collection of generating functions in this Postscript file (6 pages). An open question would be whether all sequences here discussed are 2-regular.

References:

Ph. Dumas, Divide-and-conquer.

Valid HTML 4.01!


Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 20 07:35 EDT 2018. Contains 304313 sequences. (Running on oeis4.)