A028130 -id:A028130 - cp's OEIS frontend

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

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 *)

A185966 Series reversion of A028310.

Original entry on oeis.org

1, -1, 0, 2, -2, -5, 14, 5, -72, 68, 278, -726, -520, 4691, -3514, -21758, 50374, 56185, -374566, 194596, 1962618, -3956504, -6258320, 33057877, -8974630, -190822072, 330170022, 710487590, -3088268200, 18008739, 19398384974, -28292606291, -81631282280, 298546543220, 84094857302, -2028216574806, 2428288153424, 9450205225145

Offset: 0

Paul Barry, Feb 07 2011

			1 - x + 2*x^3 - 2*x^4 - 5*x^5 + 14*x^6 + 5*x^7 - 72*x^8 + 68*x^9 + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A028130, A185962, A185965.

CoefficientList[1/x*InverseSeries[Series[x*(1-x+x^2) /(1-x)^2, {x, 0, 20}], x],x] (* Vaclav Kotesovec, Jan 22 2014 *)

{a(n) = if( n<0, 0, polcoeff( serreverse( x * ((1 - x + x^2) / (1 - x)^2 + x * O(x^n))) / x, n))} /* Michael Somos, Apr 05 2012 */

{a(n) = local(B); if( n<0, 0, B = O(x); for( k=0, n, B = (1 - B) * (x + B * (B - x))); polcoeff( B / x, n))} /* Michael Somos, Apr 05 2012 */

a(n) = A185962(2*n,n)/(n+1) = A185965(n)/(n+1).
Given g.f. A(x) then B(x) = x * A(x) satisfies B(x) = (1 - B(x)) * (x + B(x) * (B(x) - x)). - Michael Somos, Apr 05 2012
Conjecture: 6*n*(n+1)*a(n) -n*(n-14)*a(n-1) +2*n*(14*n-19)*a(n-2) -4*(n-2)*(17*n-48)*a(n-3) +6*(2*n-5)*(n-4)*a(n-4)=0. - R. J. Mathar, Nov 15 2012
Recurrence (of order 3): 3*n*(n+1)*(19*n-27)*a(n) = -2*n*(38*n^2 - 73*n + 9)*a(n-1) - 20*(19*n^3 - 65*n^2 + 66*n - 18)*a(n-2) + 2*(n-3)*(2*n-3)*(19*n-8)*a(n-3). - Vaclav Kotesovec, Jan 22 2014
Lim sup n->infinity |a(n)|^(1/n) = sqrt(20/9 + 1/27*(272376 - 12312 * sqrt(57))^(1/3) + 2/9*(1261 + 57 * sqrt(57))^(1/3)) = 2.637962913244886521522... - Vaclav Kotesovec, Jan 22 2014

A373398 Triangle read by rows: T(n, k) = number of k-element subobjects of an n-element set in the category of relations, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 9, 1, 1, 15, 55, 25, 1, 1, 31, 285, 395, 65, 1, 1, 63, 1351, 5045, 2555, 161, 1, 1, 127, 6069, 56931, 78685, 15211, 385, 1, 1, 255, 26335, 592725, 2091171, 1101021, 85099, 897, 1, 1, 511, 111645, 5834515, 50334765, 67590387, 14169405, 454315, 2049, 1

Offset: 0

Keith J. Bauer, Jun 03 2024

A subobject of an object A is an object S equipped with a monomorphism S -> A, up to isomorphism in the category of objects equipped with such morphisms. Objects in the category of relations are sets, morphisms are relations, and composition is relation composition.
Objects and morphisms in Rel can be re-characterized as free complete join-semilattices (the power set of a set with join being union) and join-equivariant maps, respectively. Therefore, subobjects in Rel can be re-characterized as injective n X k matrices of truth values. Because every injective matrix of truth values can be shown to have pivots, subobjects can be counted via Schubert cells and this results in a family of generating functions describing the entire triangle. Short proof: if a monomorphism does not have a row consisting of all 0's except for one column in particular, then consider where it sends the column vector containing all 1's and the column vector containing all 1's but with the corresponding row flipped to 0. It cannot possibly send these vectors to two different vectors. (Here 0 and 1 represent false and true, respectively. Note that addition is logical "or" and multiplication is logical "and".)
Because Rel is self-dual, this sequence also counts quotient objects.
Entries not in the triangle's range are equal to 0 because there is no monomorphism from a k-element set to an n-element set when k > n.
All monomorphisms in Rel are regular, i.e., the equalizer of a pair of morphisms. In some categories, subobjects are taken to only be regular monomorphisms, or are at least distinguished; for example, a normal subgroup is (the domain of) a regular monomorphism in the category of groups. Because all monomorphisms in Rel are regular, there is no ambiguity in what a subobject in Rel is. See the link for a proof of this fact.

			There are 9 2-element subobjects of a 3-element set in Rel. As truth matrices:
  [1 0] [1 0] [0 0] [1 0] [0 1] [0 1] [1 1] [1 0] [1 0]
  [0 1] [0 0] [1 0] [0 1] [1 0] [0 1] [1 0] [1 1] [0 1]
  [0 0] [0 1] [0 1] [0 1] [0 1] [1 0] [0 1] [0 1] [1 1]
To convert to relations, note that each entry corresponds to whether
  [(1,1) (2,1)]
  [(1,2) (2,2)]
  [(1,3) (2,3)]
is in the relation.
Triangle starts:
  1,
  1,   1,
  1,   3,      1,
  1,   7,      9,       1,
  1,  15,     55,      25,        1,
  1,  31,    285,     395,       65,        1,
  1,  63,   1351,    5045,     2555,      161,        1,
  1, 127,   6069,   56931,    78685,    15211,      385,      1,
  1, 255,  26335,  592725,  2091171,  1101021,    85099,    897,    1,
  1, 511, 111645, 5834515, 50334765, 67590387, 14169405, 454315, 2049, 1,
  ...

Keith J. Bauer, Every monomorphism in Rel is regular.
nLab, Rel

T(n, 0) = A000012(n).
T(n, 1) = A000225(n).
T(n, 2) = A016269(n - 2).
T(n, 3) = A028130(n - 3).
T(n, n) = A000012(n).
T(n, n - 1) = A002064(n - 1).
Analogous sequence in the category Set: A007318.

T[n_,k_]:=SeriesCoefficient[(1 / (1 - 2^k* x)) * Product[1 / (1 - (2^k - 2^i) * x),{i,0,k-1}],{x,0,n}]; Table[T[n-k,k],{n,0,9},{k,0,n}]//Flatten (* Stefano Spezia, Jun 04 2024 *)

dim = 10
def getGF(n):
    R. = PowerSeriesRing(ZZ, 'x', dim)
    f = 1 / (1 - 2^n * x)
    for k in range(n):
        f = f / (1 - (2^n - 2^k) * x)
    return f
for n in range(dim):
    print([getGF(k).list()[n - k] for k in range(n + 1)])

G.f.: Sum_{n>=0} T(n + k, k) * x^n = (1 / (1 - 2^k * x)) * Product_{i=0..k-1} (1 / (1 - (2^k - 2^i) * x)).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A185966 Series reversion of A028310.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A373398 Triangle read by rows: T(n, k) = number of k-element subobjects of an n-element set in the category of relations, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula