Families of Essentially Identical Sequences.
N. J. A. Sloane (njasloane@gmail.com)
March 24 2021
Abstract:
There are many examples in the On-Line Encyclopedia of Integer Sequences (OEIS) where a sequence appears in several different forms, differing from each by simple transformations such as taking differences, adding a constant to each term, and so on. Here we describe four such families.
The first is based on the Golden Ratio, and consists of sequences which can be derived from A000201 by simple transformations. The second is based on sqrt(2) (the "Silver Ratio") and A003151, and the third on Euler's totient function and A000010. The fourth is based on counting regions in the complete bipartite graph K_{n,n} and A115004.
Any sequence on these lists can be regarded as "solved".
0. Introduction.
----------------
It is not always clear from looking at an entry in the OEIS whether it is "easy" or "hard", although that is often the most basic question. All these are "easy".
These sequences can all be obtained from one of the parent sequences (A000201, A003151, ...) by a series of essentially invertible transformations. The transformations that are considered are combinations of operations like the following and their inverses.
Assume A is "known", and we are given B. Then we consider that B is "known" if:
: B = first differences or partial sums of A
: B is obtained by adding or deleting an initial term to or from A
: B is obtained by adding a constant (or simple function of n) to the terms of A
: B is obtained by multiplying or dividing A by a constant (or simple function of n)
: If A is strictly increasing, and B is the complement of A in the natural numbers
: If A is over a finite alphabet and B is obtained by a permutation of the letters
: B is obtained from A by one of the standard invertible transforms, such as the binomial or Moebius transforms.
: B is the characteristic function of A
There are also cases where B is known to be the same as A as a result of a nontrivial theorem.
Furthermore, we also allow:
:* B is a bisection of A
* Transformations marked with an asterisk (*) are not invertible.
Notes:
------
This project is not intended to be too formal. Our goal here is understanding.
These operations should be applied in moderation, or else "essentially identical to" will become "distant cousin of".
We only consider infinite sequences
These lists are certainly not complete and need checking.
Please send any corrections, additions, or suggestions for similar lists, to njasloane@gmail.com
In the following lists, the entries can be derived from those higher in the list.
In a couple of cases the dependency is only conjectural (and is indicated as such).
R. J. Mathar has kindly made graphical visualizations of each of these families: they can be seen in the Links sections of entries A000010, A000201, A003151, and A115004.
1. The A000201 or Golden Ratio family.
--------------------------------------
A000201 a(n) = floor(n*phi), a Beatty sequence, the Lower Wythoff sequence:
1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, 30, ...
A001950 a(n) = floor(n*phi^2), Upper Wythoff sequence, complement of A000201
A001468 = first differences of A000201 = Fibonacci word on {2,1} with 1 in front
A022342 = subtract 1 from terms of A000201
A001030 = swap 1's and 2's in A001468
A014675 = Fibonacci word on {1,2} = drop first term of A001468
A003622 a(n) = A022342(n)+n
A004641 = subtract 1 from terms of A001030
A003849 = Fib. word on {0,1} = subtract 1 from terms of A014675
A003842 = swap 1's and 2's in A014675
A088462 = partial sums of A004641
A005614 = swap 0's and 1's in A003849
A124841 = inverse binomial transform of A000201, also of A005614
A096270 = A005614 with an initial term
A114986 = characteristic function of A000201 with an initial term
A276854* = A000201(2*n)
A342279* = A000201(2*n+1)
A001962* = A001950(2*n)
A001966* = A001950(2*n+1)
A001961* = complement of A001962
2. The A003151 or Silver Ratio family.
--------------------------------------
A003151 = [n*(1+sqrt(2)], a Beatty sequence
2, 4, 7, 9, 12, 14, 16, 19, 21, 24, 26, 28, 31, 33, 36, 38, 41, 43, 45, ...
A003152 = complement of A003151
A276862 = first differences of A003151
A097509 = add initial term to A276862 (Theorem)
A082844 = drop initial term from A276862 (conjecture)
A245219 = A097509 (conjecture)
A001951 = [n*sqrt(2)] = A003151(n)-n
A001952 = complement of A001951
A006337 = first differences of A001951 = subtract 1 from A276862 = Hofstadter eta-sequence
A159684 = subtract 1 from A006337 = subtract 2 from A276862
A080763 = swap 1's and 2's in A006337
A188037 = 0 followed by A159684
A197878* = A003151(2*n)
A215247* = A003151(2*n-1)
A001954* = A003152(2*n+1)
A001953* = complement of A001954
A022842* = A001951(2*n)
A342281* = A001951(2*n+1)
A187393* = A001952(2*n)
A342280* = A001952(2*n+1)
A187394* = complement of A187393
3. Sequences based on the Euler totient (or phi) function A000010.
------------------------------------------------------------------
A000010 = phi(n) = number of numbers <= n and relatively prime to n
1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, ...
A057000 = first differences of phi(n)
A002088 = partial sums of phi(n)
A092249 = A002088 without leading term
A109606 = phi(n)-1
A039649 = phi(n)+1
A051953 = n-phi(n)
A140434 = 2*phi(n) for n>1
A023022 = phi(n)/2 for n>1
A127473 = phi(n)^2
A005728 = A002088(n)+1
A063985 = partial sums of A051953
A062790 = Moebius transform of A051953
A018805 = partial sums of A140434
A049643 = A005728 with a different first term
A062570* = A000010(2*n)
A037225* = A000010(2*n+1)
4. A115004 and counting regions in the complete bipartite graph K_{n,n}.
-----------------------------------------------------------------
A115004: z(n) = Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j)
1, 8, 31, 80, 179, 332, 585, 948, 1463, 2136, 3065, 4216, 5729, 7568, ...
A088658 = 4*z(n-1)
A114043 = 2*z(n-1)+2*n^2-2*n+1
A114146 = 2*A114043(n)
A115005 = z(n-1)+n*(n-1)
A141255 = 2*z(n-1)+2*n*(n-1)
A290131 = z(n-1)+(n-1)^2
A306302 = z(n)+n^2+2*n
A331771 = 4*A115005
A331759* = z(2*n+1)
A331760* = z(2*n)/4
(End)