Some Self-Similar Integer Sequences
Some Self-Similar Integer Sequences
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. |
|