A276885 -id:A276885 - cp's OEIS frontend

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

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

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

			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

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.

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

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

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

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

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

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

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

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

Edited by Dean Hickerson, Nov 09 2002

A276871 Sums-complement of the Beatty sequence for sqrt(5).

Original entry on oeis.org

1, 10, 19, 28, 37, 48, 57, 66, 75, 86, 95, 104, 113, 124, 133, 142, 151, 162, 171, 180, 189, 198, 209, 218, 227, 236, 247, 256, 265, 274, 285, 294, 303, 312, 323, 332, 341, 350, 359, 370, 379, 388, 397, 408, 417, 426, 435, 446, 455, 464, 473, 484, 493, 502

Offset: 1

Clark Kimberling, Sep 24 2016

The sums-complement of a sequence s(1), s(2), ... of positive integers is introduced here as the set of numbers c(1), c(2), ... such that no c(n) is a sum s(j)+s(j+1)+...+s(k) for any j and k satisfying 1 <= j <= k.  If this set is not empty, the term "sums-complement" also applies to the (possibly finite) sequence of numbers c(n) arranged in increasing order.  In particular, the difference sequence D(r) of a Beatty sequence B(r) of an irrational number r > 2 has an infinite sums-complement, abbreviated as SC(r) in the following table:
  r                  B(r)        D(r)       SC(r)
  ----------------------------------------------------
  sqrt(5)            A022839     A081427    A276871
  sqrt(6)            A022840     A276856    A276872
  sqrt(7)            A022841     A276857    A276873
  sqrt(8)            A022842     A276858    A276874
  e                  A022843     A276859    A276875
  2*e                A276853     A276860    A276876
  Pi                 A022844     A063438    A276877
  2*Pi               A028130     A276861    A276878
  1+sqrt(2)          A003151     A276862    A276879
  1+sqrt(3)          A054088     A007538    A276880
  1+sqrt(5)          A276854     A276863    A276881
  2+sqrt(2)          A001952     A276864    A276882
  2+sqrt(3)          A003512     A276865    A276883
  2+sqrt(5)          A004976     A276866    A276884
  1+tau              A001950   2 + A003849  A276885
  2+tau              A003231     A276867    A276886
  3+tau              A276855     A276868    A276887
  2+sqrt(1/2)        A182769     A276869    A276888
  sqrt(2)+sqrt(3)    A110117     A276870    A276889
From Jeffrey Shallit, Aug 15 2023: (Start)
Simpler description:  this sequence represents those positive integers that CANNOT be expressed as a difference of two elements of A022839.
There is a 20-state Fibonacci automaton for the terms of this sequence (see a276871.pdf).  It takes as input the Zeckendorf representation of n and accepts iff n is a member of A276871. (End)

			The Beatty sequence for sqrt(5) is A022839 = (0,2,4,6,8,11,13,15,...), with difference sequence s = A081427 = (2,2,2,2,3,2,2,2,3,2,...).  The sums s(j)+s(j+1)+...+s(k) include (2,3,4,5,6,7,8,9,11,12,...), with complement (1,10,19,28,37,...).

Luke Schaeffer, Jeffrey Shallit, and Stefan Zorcic, Beatty Sequences for a Quadratic Irrational: Decidability and Applications, arXiv:2402.08331 [math.NT], 2024. See p. 16.
Jeffrey Shallit, Fibonacci automaton for A276871
Index entries for sequences related to Beatty sequences

Cf. A022839, A081427.

z = 500; r = Sqrt[5]; b = Table[Floor[k*r], {k, 0, z}]; (* A022839 *)
t = Differences[b]; (* A081427 *)
c[k_, n_] := Sum[t[[i]], {i, n, n + k - 1}];
u[k_] := Union[Table[c[k, n], {n, 1, z - k + 1}]];
w = Flatten[Table[u[k], {k, 1, z}]]; Complement[Range[Max[w]], w];  (* A276871 *)

A372501 The 2-Zeckendorf array of the second kind, read by upward antidiagonals.

Original entry on oeis.org

0, 2, 1, 5, 4, 3, 7, 9, 8, 6, 10, 12, 16, 14, 11, 13, 17, 21, 27, 24, 19, 15, 22, 29, 35, 45, 40, 32, 18, 25, 37, 48, 58, 74, 66, 53, 20, 30, 42, 61, 79, 95, 121, 108, 87, 23, 33, 50, 69, 100, 129, 155, 197, 176, 142, 26, 38, 55, 82, 113, 163, 210, 252, 320, 286, 231

Offset: 1

A.H.M. Smeets, May 03 2024

The 2-Zeckendorf array of the second kind is based on the dual Zeckendorf representation of numbers (see A104326).
Column k contains the numbers whose dual Zeckendorf expansion ends "... 0 1^(k-1)" where ^ denotes repetition.
Rows satisfy this recurrence: T(n,k+1) = T(n,k) + T(n,k-1) + 2 for all n > 0 and k > 1.
As a sequence, the array is a permutation of the nonnegative integers.
As an array, T is an interspersion (hence also a dispersion). This holds as well for all Zeckendorf arrays of the second kind.
In general, for the m-Zeckendorf array of the second kind, the row recursion is given by T(n,k) = T(n,k-1) + T(n,k-m) + m, and the first column represent the "even" numbers.

			Array begins:
       k=1    2    3    4    5    6    7
      +---------------------------------
  n=1 |  0    1    3    6   11   19   32
  n=2 |  2    4    8   14   24   40   66
  n=3 |  5    9   16   27   45   74  121
  n=4 |  7   12   21   35   58   95  155
  n=5 | 10   17   29   48   79  129  210
  n=6 | 13   22   37   61  100  163  265
  n=7 | 15   25   42   69  113  184  299
The same in dual Zeckendorf form shows the pattern of digit suffixes, for example column k=3 is all numbers ending 011:
          k=1      2       3        4
      +------------------------------
  n=1 |     0      1      11      111
  n=2 |    10    101    1011    10111
  n=3 |   110   1101   11011   110111
  n=4 |  1010  10101  101011  1010111
  n=5 |  1110  11101  111011  1110111

Cf. A104326.
Rows n=1..3: A001911, A019274, A014739.
Columns k=1..3: A090909, A276885, A188012.
Cf. k-th prepended column: A022342 (k=1), A023444 (k=2).

T(n,1) = A090909(n+1).
T(1,k) = A001911(k-1).
T(2,k) = A019274(k-2).
T(3,k) = A014739(k-1).
T(n,1) = floor((n-1)*phi^2) and T(n,k+1) = floor((T(n,k)+1)*phi) for k > 0, where phi = (1+sqrt(5))/2. This can be considered as an alternative way to define the array.

A383670 Limiting word, as a sequence, obtained by prefixing with 0 the limiting sequence of s(n) defined by s(0) = 0, s(1) = 12, s(n) = the concatenation of s(n - 1) and s(n - 2).

Original entry on oeis.org

0, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 0, 1, 2, 1, 2, 0, 1

Offset: 1

Clark Kimberling, May 15 2025

nonn

The length of the n-th initial subword is A000045(n), for n>=1.

			s(0) = 1, s(1) = 12, s(2) = 120, s(3) = 12012, etc., so that the limiting word with 0 prefixed is 0120120120...

Cf. A000045, A003849, A276885 (positions of 0), A001950 (positions of 1), A026352 (positions of 2), A383671.

s[0] = "0"; s[1] = "12"; s[n_] := StringJoin[s[n - 1], s[n - 2]];
Join[{0}, IntegerDigits[FromDigits[s[10]]]]

from math import isqrt
def A276885(n): return n+(n-1+isqrt(5*(n-1)**2)&-2)
def A001950(n): return (n+isqrt(5*n**2)>>1)+n
def A383670(n):
    def bsearch(f, n):
        kmin, kmax = 0, 1
        while f(kmax) <= n:
            kmax <<= 1
        kmin = kmax>>1
        while True:
            kmid = kmax+kmin>>1
            if f(kmid) > n:
                kmax = kmid
            else:
                kmin = kmid
            if kmax-kmin <= 1:
                break
        return kmin
    for i, f in enumerate((A276885, A001950)):
        if f(bsearch(f, n))==n: return i
    return 2 # Chai Wah Wu, May 21 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

Python

Formula

Extensions

A276871 Sums-complement of the Beatty sequence for sqrt(5).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A372501 The 2-Zeckendorf array of the second kind, read by upward antidiagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A383670 Limiting word, as a sequence, obtained by prefixing with 0 the limiting sequence of s(n) defined by s(0) = 0, s(1) = 12, s(n) = the concatenation of s(n - 1) and s(n - 2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python