This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
Some Self-Similar Integer Sequences

# Some Self-Similar Integer Sequences

## Michael Gilleland

It is well-known that certain integer sequences exhibit self-similarity. In Fractal Horizons (New York: St. Martin's Press, 1996), edited by Clifford A. Pickover, there is an essay by Manfred Schroeder entitled "Fractals in Music" (pp. 207-223). Under the headings "A Bit of Number Theory" (pp. 208-212) and "The Fractal Nature of Number-Theoretic Sequences" (pp. 214-218), Schroeder points out that A000120 (the "ones-counting sequence"), A001316 (Gould's sequence, which Schroeder calls the "Dress sequence" after Andreas Dress), and A010060 (Thue-Morse) are self-similar. If you take one of these sequences and underline every second term, you can reproduce the original sequence. In Schroeder's words, "Certain parts of the infinite sequence contain the entire sequence."

## Every Second Term

Mining the data in the On-Line Encyclopedia of Integer Sequences uncovers other sequences which appear to be self-similar. Here is a list of sequences which exhibit self-similarity if you take every second term. Many "false positives" (e.g. constant sequences, decimal expansions of fractions, very short sequences, etc.) have been intentionally excluded.

Sequence Name
A000120 Number of 1's in binary expansion of n.
A000161 Partitions of n into 2 squares.
A000377 Expansion of (1-x^(2n))(1-x^(3n))(1-x^(8n))(1-x^(12n))/(1-x^n)(1-x^(24n)).
A001285 Thue-Morse sequence: follow a(0), .., a(2^k -1) by its complement.
A001316 Gould's sequence: Sum_{k=0..n} (C(n,k) mod 2): number of odd entries in row n of Pascal's triangle (A007318).
A001826 Expansion of Sum x^(4n+1)/(1-x^(4n+1)), n=0..inf.
A001842 Expansion of Sum x^(4n+3)/(1-x^(4n+3)), n=0..inf.
A004011 Theta series of D_4 lattice; Fourier coefficients of Eisenstein series E_{gamma,2}.
A004018 Theta series of square lattice (or number of ways of writing n as a sum of 2 squares).
A005590 a(2n)=a(n), a(2n+1)=a(n+1)-a(n).
A008687 Number of 1's in 2's complement representation of -n.
A010059 Thue-Morse sequence: follow a(0), .., a(2^k - 1) by its complement.
A010060 Thue-Morse sequence: if A_k denotes the first 2^k terms, then A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 0's and 1's.
A011558 Expansion of (x+x^3)/(1+x+...+x^4) mod 2.
A011671 A binary m-sequence: expansion of reciprocal of x^6+x^5+x^4+x^2+1.
A011673 A binary m-sequence: expansion of reciprocal of x^6+x^5+1.
A011746 Expansion of (1+x^2)/(1+x^2+x^5) mod 2.
A011747 Expansion of (1+x^2+x^4)/(1+x^2+x^3+x^4+x^5) mod 2.
A011748 Expansion of (1+x^2+x^4)/(1+x+x^2+x^4+x^5) mod 2.
A011749 Expansion of 1/(1+x^3+x^5) mod 2.
A011750 Expansion of (1+x^2)/(1+x+x^2+x^3+x^5) mod 2.
A011751 Expansion of (1+x^4)/(1+x+x^3+x^4+x^5) mod 2.
A014578 Binary expansion of Thue constant.
A016725 Number of solutions to x^2+y^2+z^2 = n^2.
A016727 Inequivalent solutions to x^2+y^2+z^2 = n^2.
A020987 The Golay-Rudin-Shapiro sequence.
A025441 Partitions of n into 2 distinct nonzero squares.
A026492 a(n) = t(1+3n), where t = A001285 (Thue-Morse sequence).
A026517 t(1+5n), where t = A001285 (Thue-Morse sequence).
A028415 Stern's sequence.
A028928 Theta series of quadratic form [ 3, 1; 1, 5 ].
A030101 Base 2 reversal of n (written in base 10).
A033666 Base 2 digital convolution sequence, (with lowest digits).
A033715 Product theta3(q^d); d | 2.
A036555 Number of bits of 3n in base 2.
A037011 Baum-Sweet cubic sequence.
A038189 Bit to left of least significant bit in binary expansion of n.
A038573 Smallest number with same number of 1's in its binary expansion as n.
A046109 Number of lattice points (x,y) on the circumference of a circle of radius n with center at (0,0).
A046820 Number of 1's in binary expansion of 5n.
A050315 Main diagonal of A050314.
A053866 Parity of sum of divisors of n.
A054868 Sum of bits of sum of bits of n.
A057227 Smallest member of smallest set S(n) of positive integers containing n which satisfies "k is in S, iff 2k-1 is in S, iff 4k is in S".
A057334 In A000120, replace each entry k with the k-th prime and replace 0 by 1.
A063014 Number of solutions to n^2=b^2+c^2 [with c>=b>=0].
A063787 a(2^k) = k + 1 and a(2^k + i) = 1 + a(i) for k >= 0 and 0 < i < 2^k.
A064917 Iterate A064916 until a prime is reached.

## Every Third Term

In his book Fractals, Chaos, Power Laws (New York: W. H. Freeman, 1991; reprint 2000), Schroeder says "there is nothing magic about the number 2" (p. 266), and gives as an example A053838 (sum of digits of n written in base 3, modulo 3), which is also self-similar if you take every third term. Once again, an examination of the On-Line Encyclopedia of Integer Sequences reveals several more sequences which appear self-similar at every third term:

Sequence Name
A000377 Expansion of (1-x^(2n))(1-x^(3n))(1-x^(8n))(1-x^(12n))/(1-x^n)(1-x^(24n)).
A000989 3^a(n) divides C(2n,n).
A001817 Expansion of Sum x^(3n+1)/(1-x^(3n+1)), n=0..inf.
A001822 Expansion of Sum x^(3n+2)/(1-x^(3n+2)), n=0..inf.
A005812 Weight of balanced ternary representation of n.
A006047 Number of entries in n-th row of Pascal's triangle not divisible by 3.
A006287 Sum of squares of digits of ternary representation of n.
A006996 C(2n,n) mod 3.
A008653 Theta series of direct sum of 2 copies of hexagonal lattice.
A011558 Expansion of (x+x^3)/(1+x+...+x^4) mod 2.
A026600 a(n) is the n-th letter of the infinite word generated from w(1)=1 inductively by w(n)=JUXTAPOSITION{w(n-1),w'(n-1),w"(n-1)}, where w(k) becomes w'(k) by the cyclic permutation 1->2->3->1 and w"(k) = (w')'(k).
A030102 Base 3 reversal of n (written in base 10).
A033667 Base 3 digital convolution sequence, (with lowest digits).
A033716 Product theta3(q^d); d | 3.
A033733 Product theta3(q^d); d | 21.
A033751 Product theta3(q^d); d | 39.
A034896 Number of solutions to a^2+b^2+3*c^2+3*d^2=n.
A038574 Write n in ternary, sort digits into increasing order.
A038586 Write n in ternary then sort.
A046109 Number of lattice points (x,y) on the circumference of a circle of radius n with center at (0,0).
A049341 a(n+1) = iterated sum of digits of a(n) + a(n-1).
A049342 A049341/3.
A051329 A generalized Thue-Morse sequence.
A051638 Sum_{k=0..n} (C(n,k) mod 3).
A053735 Sum of digits of n written in base 3.
A053838 (Sum of digits of n written in base 3) modulo 3.
A061393 Number of appearances of n in sequence defined by b(k)=b(floor[k/3])+b(ceiling[k/3]) with b(0)=0 and b(1)=1, i.e. in A061392.
A062756 Number of 1's in ternary (base 3) expansion of n.
A063014 Number of solutions to n^2=b^2+c^2 [with c>=b>=0].

Note that the following sequences are self-similar in both ways (every second term and every third term):

• A000377
• A011558
• A046109
• A063014

## Every Other Pair of Terms

Finally, let's follow yet another hint by Schroeder (Fractals, Chaos, Power Laws, p. 265), who points out that A010060 (Thue-Morse) is also self-similar in a different way, if you take every other pair of terms. The On-Line Encyclopedia of Integer Sequences yields a few sequences of this type (a subset of the first list shown above):

Sequence Name
A000120 Number of 1's in binary expansion of n.
A001285 Thue-Morse sequence: follow a(0), .., a(2^k -1) by its complement.
A001316 Gould's sequence: Sum_{k=0..n} (C(n,k) mod 2): number of odd entries in row n of Pascal's triangle (A007318).
A010059 Thue-Morse sequence: follow a(0), .., a(2^k - 1) by its complement.
A010060 Thue-Morse sequence: if A_k denotes the first 2^k terms, then A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 0's and 1's.
A038573 Smallest number with same number of 1's in its binary expansion as n.
A050315 Main diagonal of A050314.
A054868 Sum of bits of sum of bits of n.
A063787 a(2^k) = k + 1 and a(2^k + i) = 1 + a(i) for k >= 0 and 0 < i < 2^k.

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.

Last modified November 21 15:52 EST 2018. Contains 317449 sequences. (Running on oeis4.)