cp's OEIS Frontend

The sequence would remain the same if A060143 in the definition were replaced with A066096, i.e., if points (k, floor(k*phi)) were considered instead of (k, floor(k/phi)).

Rule for finding n-th term: a(n) = An, where An denotes the Fibonacci antecedent to (or right shift of) n, which is found by replacing each F(i) in the Zeckendorf expansion (obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains) by F(i-1) (A1=1). For example: 58 = 55 + 3, so a(58) = 34 + 2 = 36. - Diego Torres (torresvillarroel(AT)hotmail.com), Nov 24 2002

From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start)

A recursively built tree structure can be obtained from the sequence (see Hofstadter, p. 137):

14 15 16 17 18 19 20 21

\ / / \ / \ / /

9 10 11 12 13

\ / / \ /

6 7 8

\ / /

\ / /

\ / /

4 5

\ /

\ /

\ /

\ /

\ /

3

/

2

\ /

1

To construct the tree: node n is connected with the node a(n) below

n

/

a(n)

For example, since a(7) = 4:

7

/

4

If the nodes of the tree are read from bottom to top, left to right, one obtains the positive integers: 1, 2, 3, 4, 5, 6, ... The tree has a recursive structure, since the construct

/

x

\ /

x

can be repeatedly added on top of its own ends, to construct the tree from its root: e.g.,

/

x

/ \ /

x x

\ / /

x x

\ /

\ /

x

When moving from a node to a lower connected node, one is moving to the parent. Parent node of n: floor((n+1)/tau). Left child of n: floor(tau*n). Right child of n: floor(tau*(n+1))-1 where tau=(1+sqrt(5))/2. (See the Sillke link.)

(End)

The number n appears A001468(n) times; A001468(n) = floor((n+1)*Phi) - floor(n*Phi) with Phi = (1 + sqrt 5)/2. - Philippe Deléham, Sep 22 2005

Number of positive Wythoff A-numbers A000201 not exceeding n. - N. J. A. Sloane, Oct 09 2006

Number of positive Wythoff B-numbers < A000201(n+1). - N. J. A. Sloane, Oct 09 2006

From Bernard Schott, Apr 23 2022: (Start)

Properties coming from the 1st problem proposed during the 45th Czech and Slovak Mathematical Olympiad in 1996 (see IMO Compendium link):

-> a(n) >= a(n-1) for any positive integer n,

-> a(n) - a(n-1) belongs to {0,1},

-> No integer n exists such that a(n-1) = a(n) = a(n+1). (End)

For n >= 1, find n in the Wythoff array (A035513). a(n) is the number that precedes n in its row, using the preceding column of the extended Wythoff array (A287870) if n is at the start of the (unextended) row. - Peter Munn, Sep 17 2022

See my 2023 publication on Hofstadter's G-sequence for a proof of the equality of (a(n)) with the sequence A073869. - Michel Dekking, Apr 28 2024

From Michel Dekking, Dec 16 2024: (Start)

Focus on the pairs of duplicate values, i.e., the pairs (a(n-1),a(n)) with a(n-1) = a(n). Directly from Theorem 1 in Kimberling and Stolarsky (2016) one derives that the m-th pair of duplicate values (a(n-1),a(n)) occurs at n = U(m), where U = 2,5,7,10,... is the upper Wythoff sequence. For example, (3,3) is the second pair, and occurs at U(2) = 5.

This property can be used to give a simple construction for (a(n)) -- ignoring the superfluous a(0) = 0.

Let 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,... be the sequence of positive natural numbers. Double all the elements of the lower Wythoff sequence (L(n)) = 1,3,4,6,8,9,11,....:

(x(n)) := 1,1, 2, 3,3, 4,4, 5, 6,6, 7, 8,8, 9,9, 10,....

Claim: the result is (a(n)). This follows since because of the doubling, the m-th pair of duplicate values (a(n-1),a(n)) occurs in x at n = L(m) + m = U(m). The second equality by a well-known formula.

It follows from this by Theorem 1 of K&S, that a(n-1) = x(n-1), and a(n) = x(n) if n = U(m), for all m. But since L and U are complementary sequences, a(n) = x(n) will also hold if n = L(k), for all k. For example, L(4) = 6, and a(6) = x(6) = 4.

Corollary: for n >= 2 replace every pair of duplicate values (a(n-1),a(n)) by 0, and all the remaining elements of (a(n)) by 1. Then the result is the Fibonacci word 0,1,0,0,1,0,1,0,0... This is implied by the fact that L gives the positions of the 0s, and U the position of the 1's in the Fibonacci word. (End)

For all n >= 0, a(n) <= A005374(n), as proved in Letouzey-Li-Steiner link. Last equality occurs at n = 12, while a(n) < A005374(n) afterwards. - Pierre Letouzey, Feb 20 2025

a(n) is the smallest number different from a(i) and a(i)+i for i < n.

The losing positions in the game of Wythoff-Nim are precisely the pairs (a(n), a(n)+n).

From T. D. Noe, Jul 27 2007: (Start)

This is similar to A000123 and A005704, which both have a recursion a(n)=a(n-1)+a([n/k]), where k is 2 and 3, respectively. Those sequences count "partitions of k*n into powers of k". For the present sequence, k=phi. Does A006336(n) count the partitions of n*phi into powers of phi?

Answering my own question: If the recursion starts with a(0)=1, then I think we obtain "number of partitions of n*phi into powers of phi" (see A131882).

Here we need negative powers of phi also: letting p=phi and q=1/phi, we have

n=0: 0*p = {} for 1 partition,

n=1: 1*p = p = 1+q for 2 partitions,

n=2: 2*p = p+p = 1+p+q = 1+1+q+q = p^2+q for 4 partitions, etc.

So the present sequence, which starts with a(1)=1, counts 1/2 of the "number of partitions of n*phi into powers of phi". (End)

Self-inverse when considered as a permutation or function, i.e., a(a(n)) = n. - Howard A. Landman, Sep 25 2001

That each initial segment has an integer average is trivially equivalent to the sum of the first n elements always being divisible by n. - Franklin T. Adams-Watters, Jul 07 2014

Also, a lexicographically minimal sequence of distinct positive integers such that all values of a(n)-n are also distinct. - Ivan Neretin, Apr 18 2015

Comments from N. J. A. Sloane, Mar 29 2025 (Start):

Let d(n) = number of 1 <= i <= n such that a(i) < i. The d(i) sequence begins 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, ..., and appears to be A060144 without its initial term.

Let r(n) = 1 if a(n) < a(n+1), otherwise 0, and let f(n) = 1 if a(n) > a(n+1), otherwise 0. Then R = partial sums of r(n) and F = partial sums of f(n) count the rises and falls, respectively, in the present sequence. It appears that R and F are essentially A060143 and A060144 (again).

If a(n) is the k-th term in a monotonically strictly increasing rum of terms, set R(n) = k. It appears that the sequence R(n), n>=1, is essentially A270788.

For other sequences derived from the present one, see A382162, A382168, and A382169.

(End)

The cyclic pattern (and numerator of the gf) is computed using Euclid's algorithm for GCD.

a(n) + A183137(n) = A000217(n) (the triangular numbers).

This sequence has similarities with A022290, and is related to negaFibonacci representations.

Every positive integer occurs exactly once, so that, as a sequence, a(n) is a permutation of the positive integers.

Descending from the root node 1, generate tree by outer composition of L(n) = n + F(Finv(n)) and R(n) = n + F(Finv(n) + 1), respectively, according to left or right branching, where F(n) = A000045(n) are the Fibonacci numbers and Finv(n) = A130233(n) is the 'lower' Fibonacci inverse. This produces each number by maximal Fibonacci expansion (cf. example below of Method 2, entry A343152, and links).

(Level of tree): The number of terms in this expansion of n is the level of the tree on which n appears, A112310(n-1) + 1 = A200648(n+1). The number of terms in the expansion of a(n) is floor(log_2(n)) + 1 = A113473(n) = A070939(n) = A029837(n+1).

"Maximal Fibonacci expansion" maximizes the sum of coefficients over all Fibonacci numbers (of positive index), allowing both F(1) = 1 and F(2) = 1. Thus, it is just an expansion and not a representation (like "greedy" and "lazy"), as it "breaks the rule" by using two bits that correspond to elements of equal value, rather than using distinct basis elements (link). This reveals connections to the cf. sequences: Binary strings that emerge in lexicographic order from "maximal Fibonacci gaps" (example), binary trees of the positive integers, and I-D arrays "harvested" from the trees. To define the expansion uniquely, always include F(1), so that the expansion of positive integer n equals F(1) for n = 1 and F(1) prepended to the lazy Fibonacci representation of n-1 for n > 1. Hence, a(1) = 1, and for n > 1, a(n) = A095903(n-1) + 1. The "redundant" expansion arranges the positive integers in the single binary tree {T(n,k)}, rather than the two trees at A255773 and A255774 that result from representation (see link).

(Left-to-right order in tree): Each F(t)-sized block (F(t+1), ..., F(t+2) - 1) of successive positive integers ("Fibonacci cohort" t) appears in right-to-left order in the tree as reordered in A343152, where elements of each cohort appear consecutively (see link).

Descending from the root node 1, generate tree by the inner composition of A026351 and A026352, that is, one plus the sequences of lower and upper Wythoff numbers, A000201 and A001950, respectively, according to left or right branching (see example below of Method 1 and links).

Generate tree from (one plus) the number of (initial) zeros on the positive integers for the outer composition of sequences, A060143 and A060144, respectively, according to left or right branching descending from the identity (c.f example below of Method 3 and links).

The lower Wythoff numbers, A000201, appear exclusively in the 1st, 3rd, 5th, ... right clades of the tree, while the upper Wythoff numbers A001950, appear exclusively in the 2nd, 4th, 6th, ... right clades of the tree. Here, the k-th right clade comprises the nodes at positions 2^(k+1) and 2^k + 1, together with all descendants of the latter (link).

(Duality with tree A232560, and related arrays): Consider the labeled binary trees a(n) = A232560(A059893(n)) and A232560(n) = a(A059893(n)). Labels along maximal straight paths that always branch left in a(n) give rows of array A345252, while labels along maximal straight paths that always branch left in A232560 give rows of array A083047.

Sorting the labels from each successive right clade of the binary tree a(n) gives the successive columns of A083047, while sorting labels from each successive right clade of A232560 gives each successive column of A345252. This makes the trees a(n) and A232560 "blade-duals," blade being a contraction of branch-clade (see entry for A345254 and link). A200648(n)+1 gives the level of the tree on which elements of array first-columns A345252(n,1) and A083047(n,1) appear.

(Palindromes and coincidence of elements): Trees a(n) and A232560 coincide when the sequence of left and right branching is a palindrome: a(A329395(n)) = A232560(A329395(n)). As Kimberling notes (cf. A059893), this happens at fixed points of A059893(n) or, equivalently, at n for which A081242(n) is a palindrome.

The inverse permutation of a(n) as a sequence can be read from a "tetrangle" or "irregular triangle" tableau with F(t) (Fibonacci number) entries on each row t, for t = 1, 2, 3, ..., in which an entry on row t is 2*x the entry x immediately above it on row t-1, if such exists, or otherwise 2*x + 1 the entry x in the corresponding position on row t-2 (thus generating new rows as in A243571 but without sorting the numbers into increasing order, linked reference):

1,

2,

3, 4,

5, 6, 8,

7, 9, 10, 12, 16,

11, 13, 17, 14, 18, 20, 24, 32,

...

With the right-justified tableau substituted by a left-justified tableau, the same procedure yields the inverse permutation for the "minimal Fibonacci tree," A048680(A059893(n)), the "cohort-dual" tree of a(n), where "cohort" t is the F(t)-sized block of successive entries in the tableau (see entry for A345252, linked reference).

(Coincidence of elements): a(A020988(n)) = A048680(A059893(A020988(n))) = A099919(n) and a(A020989(n)) = A048680(A059893(A020989(n))) = A049651(n). Collectively, a(A061547(n)) = A048680(A059893(A061547(n))) = union(A049651(n), A099919(n)).

With two types of duality, the tree forms a quartet of binary-tree arrangements of the positive integers, together with its blade dual A232560, its cohort dual A048680(A059893), and blade dual A048680 of the latter.

Order in the tree is "memory-less": Let a(n) and a(m) label nodes at positions n and m, respectively. Let d1 and d2 be two descending paths, i.e., sequences branching left or right from a starting node. (Nodal positions for the left and right children of the node at position p are given by 2*p and 2*p + 1, resp., and d1 and d2 are compositions of these.) Then a(d1(n)) < a(d2(n)) if and only if a(d1(m)) < a(d2(m)) (linked reference).

a(n) + b(n) = n and as n -> +infinity, a(n)/b(n) converges to Pi. For all n, a(n)/b(n) < Pi.