A019446 - OEIS

A019446

a(n) = ceiling(n/tau), where tau = (1+sqrt(5))/2.

1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 10, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, 17, 17, 18, 18, 19, 20, 20, 21, 22, 22, 23, 23, 24, 25, 25, 26, 26, 27, 28, 28, 29, 30, 30, 31, 31, 32, 33, 33, 34, 34, 35, 36, 36, 37, 38, 38, 39, 39, 40, 41, 41, 42, 43, 43, 44, 44, 45, 46, 46

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Average of first n terms of A019444, which is defined to be a permutation of the positive integers, p_1, p_2, ..., such that the average of each initial segment is an integer, using the greedy algorithm to define p_n.

Number of pairs (i,j) of nonnegative integers such that n-1=floor(i+j*tau). - Clark Kimberling, Jun 18 2002

The terms that occur exactly once are 1,3,6,8,..., given by A026352(n)=n+1+floor(n*tau). - Clark Kimberling, Jun 18 2002

The number n appears A001468(n) times. - Reinhard Zumkeller, Feb 02 2012

It seems that the indices of the terms that occur exactly once are listed in A276885. - Ivan N. Ianakiev, Aug 30 2018

From Michel Dekking, Oct 13 2020: (Start)

Here is a proof of the conjecture by Ivan N. Ianakiev. Let b = (b(n)) be the sequence of occurrences of the "singleton terms" in (a(n)). We have to show that b = A276885.

In the following phi := (1+sqrt(5))/2 (so phi = tau).

By its definition, the sequence (a(n)) is a generalized Beatty sequence with terms a(n) = floor(phi*n)-n+1, since 1/phi = phi-1. So by Lemma 8 in the paper by Allouche and Dekking, its sequence of first differences Delta = 1011010110..., given by Delta(n) = a(n+1)-a(n), is equal to y, where y = A005614 is the binary complement of the Fibonacci word. By definition, y is the fixed point of the morphism nu: 0->1, 1->10.

The crucial observation is that a term occurs exactly once in (a(n)) if and only if the word 11 of length 2 occurs in Delta (with an exception for a(1)=1). So to obtain the sequence b of occurrences of these "singleton terms", we have to study the return words of 11 in y. (The return words of 11 in y are the words occurring in y that start with 11, and having no other occurrences of 11.)

The return words of 11 are the words A:=11010, and B:=110. Since

nu(A) = nu(11010) = 10101101, nu(B) = nu(110) = 10101,

the morphism nu induces a descendant morphism tau given by

tau(A) = BA, tau(B) = A.

So tau is nothing else but the Fibonacci morphism on the alphabet {B,A}.

Since the words A and B have lengths 5 and 3, the first differences b(n+1)-b(n) are given by the fixed point z = 5353353533... of the Fibonacci morphism on the alphabet {5,3}.

From Lemma 8 in the paper by Allouche and Dekking we then obtain that the sequence b is a generalized Beatty sequence

V(n) = (5-3)*floor(phi*n)+(2*3-5)*n+r = 2*floor(phi*n)+n+r, for some integer r.

Starting at the value 4, filling in n=1, we obtain that r=1, and so V(n) = 2*floor(phi*n)+n+1. To incorporate also the first "singleton term" a(1)=1, we take

b(n) = V(n-1) = 2*floor(phi*(n-1))+n-1+1 = 2*floor(phi*(n-1))+n.

Then, indeed, b(n) = A276885(n), for n=1,2,... (see my Comment in A276885).

(End)

It seems that the indices of the records are listed in A026351. - Ivan N. Ianakiev, Mar 25 2021

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

J.-P. Allouche and F. M. Dekking, Generalized Beatty sequences and complementary triples, arXiv:1809.03424 [math.NT], 2018.

Problem of the week, Problem 818

J. Rickard, Rearrangement of the natural numbers [Broken link]

J. Shallit, Proving properties of some greedily-defined integer recurrences via automata theory, arXiv:2308.06544 [cs.DM], August 12 2023.

FORMULA

a(1)=1; a(n) = n+1 - a(a(n-1)). - Benoit Cloitre, Nov 06 2002