|
%I #86 Aug 15 2023 08:12:58
%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 = 2floor(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) = 2floor(phi*n)+n+1. To incorporate also the first "singleton term" a(1)=1, we take
%C b(n) = V(n-1) = 2floor(phi*(n-1)+n-1+1 = 2floor(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
|
