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

Offset: 1

Author

R. K. Guy, Tom Halverson (halverson(AT)macalester.edu)

Keywords

• nonn
• easy
• nice

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

Examples

			a(6)=4 since 6-1=[i+j*tau] for these (i,j): (5,0), (4,1), (2,2), (1,3). - _Clark Kimberling_, Jun 18 2002
		

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.

Crossrefs

Cf. A001622, A019444, A019445, A026351, A026352, A005206.

Programs

GAP

a:=[1];; for n in [2..80] do a[n]:=n+1-a[a[n-1]]; od; a; # Muniru A Asiru, Aug 30 2018

Haskell

a019446 n = a019446_list !! (n-1)
a019446_list = 1 : zipWith (-) [3..] (map a019446 a019446_list)
-- Reinhard Zumkeller, Feb 02 2012

Maple

A019446:=n->ceil(2*n/(1+sqrt(5))); seq(A019446(n), 1..100); # Wesley Ivan Hurt, Jan 19 2014

Mathematica

Ceiling[Range[80]/GoldenRatio] (* Harvey P. Dale, Aug 02 2011 *)

Python

from math import isqrt
def A019446(n): return (n+isqrt(5*n**2)>>1)-n+1 # Chai Wah Wu, Aug 09 2022

Formula

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

a(n) = A005206(n-1) + 1. - Reinhard Zumkeller, Feb 02 2012; corrected by Primoz Pirnat, Dec 28 2020

a(n) = A019445(n) / n. - Sean A. Irvine, Mar 17 2019

Extensions

Better name from David Radcliffe and John Rickard, Dec 12 2000

Edited by Dean Hickerson, Nov 09 2002