A003622 - OEIS

%I M3278 #188 Feb 07 2025 14:49:02

%S 1,4,6,9,12,14,17,19,22,25,27,30,33,35,38,40,43,46,48,51,53,56,59,61,

%T 64,67,69,72,74,77,80,82,85,88,90,93,95,98,101,103,106,108,111,114,

%U 116,119,122,124,127,129,132,135,137,140,142,145,148,150,153,156,158,161,163,166

%N The Wythoff compound sequence AA: a(n) = floor(n*phi^2) - 1, where phi = (1+sqrt(5))/2.

%C Also, integers with "odd" Zeckendorf expansions (end with ...+F_2 = ...+1) (Fibonacci-odd numbers); first column of Wythoff array A035513; from a 3-way splitting of positive integers. [Edited by _Peter Munn_, Sep 16 2022]

%C Also, numbers k such that A005206(k) = A005206(k+1). Also k such that A022342(A005206(k)) = k+1 (for all other k's this is k). - Michele Dondi (bik.mido(AT)tiscalenet.it), Dec 30 2001

%C Also, positions of 1's in A139764, the smallest term in Zeckendorf representation of n. - _John W. Layman_, Aug 25 2011

%C From _Amiram Eldar_, Sep 03 2022: (Start)

%C Numbers with an odd number of trailing 1's in their dual Zeckendorf representation (A104326), i.e., numbers k such that A356749(k) is odd.

%C The asymptotic density of this sequence is 1 - 1/phi (A132338). (End)

%C {a(n)} is the unique monotonic sequence of positive integers such that {a(n)} and {b(n)}: b(n) = a(n) - n form a partition of the nonnegative integers. - _Yifan Xie_, Jan 25 2025

%D A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 62.

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 307-308 of 2nd edition.

%D C. Kimberling, "Stolarsky interspersions", Ars Combinatoria 39 (1995) 129-138.

%D D. R. Morrison, "A Stolarsky array of Wythoff pairs", in A Collection of Manuscripts Related to the Fibonacci Sequence. Fibonacci Assoc., Santa Clara, CA, 1980, pp. 134-136.

%D J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 10.

%D N. J. A. Sloane and Simon Plouffe, Encyclopedia of Integer Sequences, Academic Press, 1995: this sequence appears twice, as both M3277 and M3278.

%H A.H.M. Smeets, <a href="/A003622/b003622.txt">Table of n, a(n) for n = 1..20000</a> (terms 1.1000 from T. D. Noe)

%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 A. Brousseau, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/fibonacci-tables.html">Fibonacci and Related Number Theoretic Tables</a>, Fibonacci Association, San Jose, CA, 1972, p. 62.

%H Larry Ericksen and Peter G. Anderson, <a href="http://www.cs.rit.edu/~pga/k-zeck.pdf">Patterns in differences between rows in k-Zeckendorf arrays</a>, The Fibonacci Quarterly, Vol. 50, February 2012. - _N. J. A. Sloane_, Jun 10 2012

%H Aviezri S. Fraenkel, <a href="https://www.emis.de/journals/INTEGERS/papers/a13int2005/a13int2005.Abstract.html">The Raleigh game</a>, INTEGERS: Electronic Journal of Combinatorial Number Theory 7.2 (2007): A13, 10 pages. See Table 1.

%H Martin Griffiths, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Griffiths/gr48.html">On a Matrix Arising from a Family of Iterated Self-Compositions</a>, Journal of Integer Sequences, 18 (2015), Article 15.11.8.

%H V. E. Hoggatt, Jr., <a href="/A005676/a005676.pdf">7-page typed letter to N. J. A. Sloane with suggestions for new sequences</a>, circa 1977.

%H Clark Kimberling, <a href="http://faculty.evansville.edu/ck6/integer/intersp.html">Interspersions</a>.

%H Clark Kimberling, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Kimberling/kimberling719a.html">Complementary equations and Wythoff Sequences</a>, JIS 11 (2008), Article 08.3.3.

%H Clark Kimberling, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Kimberling/kimber12.html">Lucas Representations of Positive Integers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.9.5.

%H Clark Kimberling, <a href="https://doi.org/10.4171/EM/468">Intriguing infinite words composed of zeros and ones</a>, Elemente der Mathematik (2021).

%H Clark Kimberling and K. B. Stolarsky, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.123.3.267">Slow Beatty sequences, devious convergence, and partitional divergence</a>, Amer. Math. Monthly, 123 (No. 2, 2016), 267-273.

%H L. Lindroos, A. Sills, and H. Wang, <a href="http://digitalcommons.georgiasouthern.edu/math-sci-facpubs/182/">Odd fibbinary numbers and the golden ratio</a>, Fib. Q., 52 (2014), 61-65.

%H A. J. Macfarlane, <a href="https://arxiv.org/abs/2405.18128">On the fibbinary numbers and the Wythoff array</a>, arXiv:2405.18128 [math.CO], 2024. See page 3.

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/3459893/golden-ratio-and-floor-function-lfloor-phi-2-n-rfloor-lfloor-phi-lfloo">Golden ratio and floor function floor(phi^2*n) - floor(phi*floor(phi*n)) = 1</a>.

%H M. Rigo, P. Salimov, and E. Vandomme, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Rigo/rigo3.html">Some Properties of Abelian Return Words</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.2.5.

%H N. J. A. Sloane, <a href="/classic.html#WYTH">Classic Sequences</a>

%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)

%H Jiemeng Zhang, Zhixiong Wen, and Wen Wu, <a href="https://doi.org/10.37236/6745">Some Properties of the Fibonacci Sequence on an Infinite Alphabet</a>, Electronic Journal of Combinatorics, 24(2) (2017), Article P2.52.

%F a(n) = floor(n*phi) + n - 1. [Corrected by _Jianing Song_, Aug 18 2022]

%F a(n) = floor(floor(n*phi)*phi) = A000201(A000201(n)). [See the Mathematics Stack Exchange link for a proof of the equivalence of the definition. - _Jianing Song_, Aug 18 2022]

%F a(n) = 1 + A022342(1 + A022342(n)).

%F G.f.: 1 - (1-x)*Sum_{n>=1} x^a(n) = 1/1 + x/1 + x^2/1 + x^3/1 + x^5/1 + x^8/1 + ... + x^F(n)/1 + ... (continued fraction where F(n)=n-th Fibonacci number). - _Paul D. Hanna_, Aug 16 2002

%F a(n) = A001950(n) - 1. - _Philippe Deléham_, Apr 30 2004

%F a(n) = A022342(n) + n. - _Philippe Deléham_, May 03 2004

%F a(n) = a(n-1) + 2 + A005614(n-2); also a(n) =  a(n-1) + 1 + A001468(n-1). - _A.H.M. Smeets_, Apr 26 2024

%p A003622 := proc(n)

%p     n+floor(n*(1+sqrt(5))/2)-1 ;

%p end proc: # _R. J. Mathar_, Jan 25 2015

%p # Maple code for the Wythoff compound sequences, from _N. J. A. Sloane_, Mar 30 2016

%p # The Wythoff compound sequences: Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864. The eight triples AAA, AAB, ..., BBB are A134859, A134860, A035337, A134862, A134861, A134863, A035338, A134864, resp.

%p # Assume files out1, out2 contain lists of the terms in the base sequences A and B from their b-files

%p read out1; read out2; b[0]:=b1: b[1]:=b2:

%p w2:=(i,j,n)->b[i][b[j][n]];

%p w3:=(i,j,k,n)->b[i][b[j][b[k][n]]];

%p for i from 0 to 1 do

%p lprint("name=",i);

%p lprint([seq(b[i][n],n=1..100)]):

%p od:

%p for i from 0 to 1 do for j from 0 to 1 do

%p lprint("name=",i,j);

%p lprint([seq(w2(i,j,n),n=1..100)]);

%p od: od:

%p for i from 0 to 1 do for j from 0 to 1 do for k from 0 to 1 do

%p lprint("name=",i,j,k);

%p lprint([seq(w3(i,j,k,n),n=1..100)]);

%p od: od: od:

%t With[{c=GoldenRatio^2},Table[Floor[n c]-1,{n,70}]] (* _Harvey P. Dale_, Jun 11 2011 *)

%t Range[70]//Floor[#*GoldenRatio^2]-1& (* _Waldemar Puszkarz_, Oct 10 2017 *)

%o (PARI) a(n)=floor(n*(sqrt(5)+3)/2)-1

%o (PARI) a(n) = (sqrtint(n^2*5)+n*3)\2 - 1; \\ _Michel Marcus_, Sep 17 2022

%o (Haskell)

%o a003622 n = a003622_list !! (n-1)

%o a003622_list = filter ((elem 1) . a035516_row) [1..]

%o -- _Reinhard Zumkeller_, Mar 10 2013

%o (Python)

%o from sympy import floor

%o from mpmath import phi

%o def a(n): return floor(n*phi**2) - 1 # _Indranil Ghosh_, Jun 09 2017

%o (Python)

%o from math import isqrt

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

%Y Positions of 1's in A003849.

%Y Complement of A022342.

%Y Cf. A066096, A139764, A035516, A026273, A104326, A132338, A356749.

%Y The Wythoff compound sequences: Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864. The eight triples AAA, AAB, ..., BBB are A134859, A134860, A035337, A134862, A134861, A134863, A035338, A134864, resp.

%Y The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - _N. J. A. Sloane_, Mar 11 2021

%K nonn,easy,nice

%O 1,2

%A _N. J. A. Sloane_, _Mira Bernstein_, _Marc LeBrun_