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

%I #95 Aug 05 2024 04:04:44

%S 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,

%T 18,18,19,20,20,21,22,22,23,23,24,25,25,26,26,27,28,28,29,30,30,31,31,

%U 32,33,33,34,34,35,36,36,37,38,38,39,39,40,41,41,42,43,43,44,44,45,46,46

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

%C 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.

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

%C 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

%C The number n appears A001468(n) times. - _Reinhard Zumkeller_, Feb 02 2012

%C It seems that the indices of the terms that occur exactly once are listed in A276885. - _Ivan N. Ianakiev_, Aug 30 2018

%C From _Michel Dekking_, Oct 13 2020: (Start)

%C 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.

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

%C 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.

%C 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.)

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

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

%C the morphism nu induces a descendant morphism tau given by

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

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

%C 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}.

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

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

%C 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

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

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

%C (End)

%C It seems that the indices of the records are listed in A026351. - _Ivan N. Ianakiev_, Mar 25 2021

%H Reinhard Zumkeller, <a href="/A019446/b019446.txt">Table of n, a(n) for n = 1..10000</a>

%H J.-P. Allouche and F. M. Dekking, <a href="https://arxiv.org/abs/1809.03424">Generalized Beatty sequences and complementary triples</a>, arXiv:1809.03424 [math.NT], 2018.

%H Problem of the week, <a href="http://stanwagon.com/potw/fall96/p818.html">Problem 818</a>

%H J. Rickard, <a href="http://mathforum.org/epigone/sci.math/crorquusnand/v2j*WWuJo%40news.cam.virata.com">Rearrangement of the natural numbers</a> [Broken link]

%H J. Shallit, <a href="https://arxiv.org/abs/2308.06544">Proving properties of some greedily-defined integer recurrences via automata theory</a>, arXiv:2308.06544 [cs.DM], August 12 2023.

%F a(1)=1; a(n) = n+1 - a(a(n-1)). - _Benoit Cloitre_, Nov 06 2002

%F a(n) = A005206(n-1) + 1. - _Reinhard Zumkeller_, Feb 02 2012; corrected by _Primoz Pirnat_, Dec 28 2020

%F a(n) = A019445(n) / n. - _Sean A. Irvine_, Mar 17 2019

%e 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

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

%t Ceiling[Range[80]/GoldenRatio] (* _Harvey P. Dale_, Aug 02 2011 *)

%o (Haskell)

%o a019446 n = a019446_list !! (n-1)

%o a019446_list = 1 : zipWith (-) [3..] (map a019446 a019446_list)

%o -- _Reinhard Zumkeller_, Feb 02 2012

%o (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

%o (Python)

%o from math import isqrt

%o def A019446(n): return (n+isqrt(5*n**2)>>1)-n+1 # _Chai Wah Wu_, Aug 09 2022

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

%K nonn,easy,nice

%O 1,2

%A _R. K. Guy_, Tom Halverson (halverson(AT)macalester.edu)

%E Better name from _David Radcliffe_ and John Rickard, Dec 12 2000

%E Edited by _Dean Hickerson_, Nov 09 2002