Some SelfSimilar Integer Sequences
Some SelfSimilar Integer Sequences
It is wellknown that certain integer sequences exhibit selfsimilarity.
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. 207223). Under the headings
"A Bit of Number Theory" (pp. 208212) and "The Fractal Nature of
NumberTheoretic Sequences" (pp. 214218), Schroeder points out that
A000120 (the "onescounting sequence"),
A001316 (Gould's sequence, which Schroeder calls the "Dress sequence"
after Andreas Dress), and A010060 (ThueMorse) are selfsimilar.
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 OnLine Encyclopedia of Integer Sequences
uncovers other sequences which appear to be selfsimilar.
Here is a list of sequences which exhibit selfsimilarity 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 (1x^(2n))(1x^(3n))(1x^(8n))(1x^(12n))/(1x^n)(1x^(24n)). 
A001285

ThueMorse 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)/(1x^(4n+1)), n=0..inf. 
A001842

Expansion of Sum x^(4n+3)/(1x^(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

ThueMorse sequence: follow a(0), .., a(2^k  1) by its complement. 
A010060

ThueMorse 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 msequence: expansion of reciprocal of x^6+x^5+x^4+x^2+1. 
A011673

A binary msequence: 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 GolayRudinShapiro sequence. 
A025441

Partitions of n into 2 distinct nonzero squares. 
A026492

a(n) = t(1+3n), where t = A001285 (ThueMorse sequence). 
A026517

t(1+5n), where t = A001285 (ThueMorse 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

BaumSweet 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 2k1 is in S, iff 4k is in S". 
A057334

In A000120, replace each entry k with the kth 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 selfsimilar if you
take every third term. Once again, an examination of the
OnLine Encyclopedia of Integer Sequences
reveals several more sequences which appear selfsimilar at every
third term:
Sequence 
Name 
A000377

Expansion of (1x^(2n))(1x^(3n))(1x^(8n))(1x^(12n))/(1x^n)(1x^(24n)). 
A000989

3^a(n) divides C(2n,n). 
A001817

Expansion of Sum x^(3n+1)/(1x^(3n+1)), n=0..inf. 
A001822

Expansion of Sum x^(3n+2)/(1x^(3n+2)), n=0..inf. 
A005812

Weight of balanced ternary representation of n. 
A006047

Number of entries in nth 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 nth letter of the infinite word generated from w(1)=1
inductively by w(n)=JUXTAPOSITION{w(n1),w'(n1),w"(n1)},
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(n1). 
A049342

A049341/3. 
A051329

A generalized ThueMorse 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 selfsimilar 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 (ThueMorse) is
also selfsimilar in a different way, if you take every other pair of terms.
The OnLine 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

ThueMorse 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

ThueMorse sequence: follow a(0), .., a(2^k  1) by its complement. 
A010060

ThueMorse 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. 
