David Eppstein - cp's OEIS frontend

A375492 Number of compositions of n into powers of two that each divide the sum of previous powers.

1, 1, 2, 2, 5, 5, 10, 10, 26, 26, 52, 52, 130, 130, 260, 260, 677, 677, 1354, 1354, 3385, 3385, 6770, 6770, 17602, 17602, 35204, 35204, 88010, 88010, 176020, 176020, 458330, 458330, 916660, 916660, 2291650, 2291650, 4583300, 4583300, 11916580, 11916580

Offset: 0

David Eppstein, Aug 17 2024

nonn

If n = 2^k, a(n) = A003095(k). Otherwise, a(n) is the product of terms from A003095 corresponding to the powers of two in the binary representation of n. If n is odd, the final term of the composition must be 1, so a(n) = a(n-1).

Pieter Mostert points out that, after the first two values, this is a subsequence of A000404 (sums of two nonzero squares), because each term is either a square + 1 or a product of two earlier terms.

			For n = 4 the a(4) = 5 compositions are 1+1+1+1, 1+1+2, 2+1+1, 2+2, and 4. The composition 1+2+1 is not allowed, because 2 does not divide the sum of previous terms.

Cf. A023359, A003095.

Let p be the largest power of two less than n; then a(n) = a(p)a(n-p) if n is not a power of two, or a(n) = a(p)^2 + 1 if n is a power of two.

A348167 Numbers whose binary representation contains a maximal set of nonconsecutive 1's.

Original entry on oeis.org

1, 2, 5, 9, 10, 18, 21, 37, 41, 42, 73, 74, 82, 85, 146, 149, 165, 169, 170, 293, 297, 298, 329, 330, 338, 341, 585, 586, 594, 597, 658, 661, 677, 681, 682, 1170, 1173, 1189, 1193, 1194, 1317, 1321, 1322, 1353, 1354, 1362, 1365, 2341, 2345, 2346, 2377, 2378

Offset: 1

David Eppstein, Oct 03 2021

These are the numbers that do not contain 11 and 000 in their binary representations (cf. A086638), and in addition do not have 00 as their two lowest-order bits.

			5 is in this sequence, because its binary representation 101 cannot have any more ones added (below its highest nonzero bit) while preserving the property of having no two consecutive 1's.
4 is not in the sequence, because its binary representation 100 can be augmented to 101, producing another number in the sequence.

Subsequence of A003714 and A086638.

def A348167():
    x = -1
    while True:
        x = x + 1
        if x & (x>>1): continue
        if (x & 3) == 0: continue
        negx = ~x
        gaps = negx & (negx >> 1) & (negx >> 2)
        if (gaps-1) & x != x: continue
        yield x

A343245 Hyperplane-counting upper bound on the number of sorted orders of X+Y for two lists X and Y of length n.

Original entry on oeis.org

1, 1, 16, 190051, 48563893286, 62416511444764621, 278991478506233367981237, 3489283612532675861618129664796, 104930321415012656258005668476458298401, 6780157485532072442175423032103032983044918034

Offset: 0

David Eppstein, Apr 08 2021

nonn

Grows asymptotically as O(n^(8n)) (Fredman 1976).

			For n=2, 2*binomial(n,2)^2 + 2*binomial(n,2) = 4 and binomial(4,0) + ... + binomial(4,2*n) = 16, so a(2)=16.

Michael L. Fredman (1976). "How good is the information theory bound in sorting?". Theoretical Computer Science. 1 (4): 355-361.
Wikipedia, X+Y sorting.

a(n) = Sum_{i=0..2*n} binomial(2*binomial(n,2)^2 + 2*binomial(n,2), i).

A331235 The number of simple polygons having all points of a 3 X n grid as vertices.

Original entry on oeis.org

0, 1, 8, 62, 532, 4846, 45712, 441458, 4337468, 43187630, 434602280, 4411598154, 45107210436, 464047175770, 4799184825632, 49860914628042, 520109726201420, 5444641096394926, 57176049036449464, 602125661090565914, 6357215467283967404, 67274331104623532042

Offset: 1

David Eppstein, Jan 12 2020

The polygons are allowed to have flat angles (angles of exactly Pi) at some of the grid points. Empirically this sequence appears to be asymptotic to phi^(5n)/(66n), where phi is the golden ratio.

David Eppstein, Counting grid polygonalizations, Jan 12 2020

from math import log
memo = {}
def K(x,y,z):
    """Number of strings of length y from two sorted alphabets of lengths x,z"""
    if (x,y,z) in memo:
        return memo[(x,y,z)]
    if y == 0:
        result = 1
    else:
        # i = length of the last block of equal characters in the string
        # xx or zz = the largest remaining character in its alphabet
        result = (sum(K(xx,y-i,z) for xx in range(x) for i in range(1,y+1)) +
                 sum(K(x,y-i,zz) for zz in range(z) for i in range(1,y+1)))
    memo[(x,y,z)] = result
    return result
def GC(n):
    """Number of polygonalizations of 3xn grid"""
    sum = 0
    for i in range(n-1):    # number of points in K(...) can be up to n-2
        mid = K(n-1,i,n-1)
        for left in range(n-1-i):
            right = n-2-i-left
            contrib = mid
            if left:
                contrib *= 2
            if right:
                contrib *= 2
            sum += contrib
    return sum
def exponent(p):
    return p**(-4*p) * (1-p)**(-2*(1-p)) * (1-2*p)**(-1*(1-2*p))
base = ( (1+5**0.5)/2 )**5
#for n in range(2,50):
#    print(n,(base**n/(66*n))/GC(n),GC(n))
[GC(n) for n in range(1,50)]

A302757 a(n) is the smallest number whose greedy representation as a sum of terms of A126684 uses n terms.

Original entry on oeis.org

1, 3, 13, 55, 225, 907, 3637, 14559, 58249, 233011, 932061, 3728263, 14913073, 59652315, 238609285, 954437167, 3817748697, 15270994819, 61083979309, 244335917271, 977343669121, 3909374676523, 15637498706133, 62549994824575, 250199979298345, 1000799917193427

Offset: 1

David Eppstein, Apr 12 2018

A126684 is described as the fastest-growing sequence such that every nonnegative integer is the sum of two of its terms. However, if one uses a greedy algorithm to find a representation as a sum of its terms, the length of the representation will typically be more than two. This sequence gives the numbers whose greedy representations have record-setting lengths. For example, a(3) = 13 because (although 13 = 8 + 5, a representation as a sum of two terms of A126684) the greedy algorithm represents it as the three-term sum 13 = 10 + 2 + 1.

Colin Barker, Table of n, a(n) for n = 1..1000
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
Index entries for linear recurrences with constant coefficients, signature (6,-9,4).

Cf. A126684.

Fold[Append[#1, 4 Last[#1] + 2 #2 - 5] &, {1}, Range[2, 25]] (* Michael De Vlieger, Apr 12 2018 *)

Vec(x*(1 - 3*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)) + O(x^60)) \\ Colin Barker, Apr 13 2018

a(n) = 4*a(n-1) + 2*n - 5.
From Colin Barker, Apr 13 2018: (Start)
G.f.: x*(1 - 3*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)).
a(n) = (7 + 2^(1+2*n) - 6*n) / 9.
a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-3) for n>3.
(End)

A297963 The smallest position with nim-value n in subtract-a-square game.

Original entry on oeis.org

0, 1, 4, 25, 28, 29, 75, 103, 200, 234, 315, 364, 479, 633, 802, 1054, 1173, 1311, 1894, 2058, 2173, 2419, 3244, 3648, 4249, 4474, 4982, 5943, 6133, 6809, 7429, 8590, 8654, 9419, 10284, 11728, 12152, 13884, 15493, 16623, 17312, 18389, 19745, 20528, 22111, 23472

Offset: 0

David Eppstein, Jan 09 2018

nonn

a(n) is the position of the first copy of n in A014586.

			The sequence of nim-values for subtract-a-square (A014586) begins 0,1,0,1,2; the first position with value 2 is position 4 (starting from 0) so a(2)=4.

Nathan Fox, Subtraction Games with Infinite Subtraction Sets
Nathan Fox, Subtraction Games with Infinite Subtraction Sets [Local copy]

Cf. A014586.

A296840 The smallest positive integer whose greedy representation as a sum of 3-smooth numbers (A003586) requires n terms.

Original entry on oeis.org

1, 5, 23, 185, 1721, 15545, 277689, 5586105, 113081529, 2289863865, 46369706169, 986739675321, 26376728842425, 711906436354233, 19221208539173049, 518972365315281081, 22132599848083154505, 944314039112845753929, 40290722114409383329353

Offset: 1

David Eppstein, Dec 21 2017

nonn

			For n = 4, 185 = 162 + 18 + 4 + 1 requires four terms in its greedy representation even though it has the shorter non-greedy representation 185 = 144 + 32 + 9.

David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.

Cf. A018899 (numbers requiring n terms in non-greedy representations as sums of A003586), A006892 and A066352 (sequences describing greedy representations as sums of squares and of primes respectively).

With[{nn = 19}, Block[{s = Sort@ Flatten@ Table[2^a * 3^b, {a, 0, Log[2, #]}, {b, 0, Log[3, #/2^a]}] &[10^Floor[8 nn/5]], t}, t = Transpose@ {Most@ s, Differences@ s}; Fold[Append[#1, Function[{a, n}, Last[a] + SelectFirst[t, Last[#] > Last@ a &][[1]]][#1, #2]] &, {1}, Range[2, nn]]]] (* Michael De Vlieger, Dec 22 2017 *)

a(n) is a(n-1) plus the smallest 3-smooth number s whose next successive 3-smooth number is greater than s + a(n-1). For instance, a(3) = 23 = 5 + 18, where a(2) = 5 is the predecessor of 23 in the sequence and where the first gap bigger than 5 among the 3-smooth numbers is the one from 18 to 24.

A293596 The number of vertices on successive convex layers of the positive quadrant of the two-dimensional integer grid.

Original entry on oeis.org

1, 2, 2, 3, 4, 4, 3, 4, 6, 6, 5, 4, 6, 6, 8, 7, 6, 6, 6, 8, 9, 10, 10, 8, 8, 7, 8, 10, 10, 12, 13, 12, 12, 10, 10, 9, 10, 12, 12, 14, 13, 14, 14, 14, 12, 12, 9, 10, 14, 14, 16, 16, 17, 16, 18, 16, 16, 14, 13, 10, 14, 14, 14, 18, 18, 19, 18, 20, 18, 16, 18

Offset: 1

David Eppstein, Oct 12 2017

nonn

			a(1) is 1 because the first convex layer only has one vertex, (0,0).
a(2) is 2 because the second convex layer has the two vertices (0,1) and (1,0).
The illustration for a(5)=4, a(10)=6, ..., a(30)=12 see in Fig. 3 of the Eppstein, Har-Peled & Nivasch reference.

David Eppstein, Sariel Har-Peled, and Gabriel Nivasch, Grid peeling and the affine curve-shortening flow, arXiv:1710.03960 [cs.CG], 2017, Fig. 5. To appear in ALENEX 2018.

Cf. A290966.

A290966 The number of convex layers in an n X n grid of points.

Original entry on oeis.org

1, 1, 3, 3, 6, 6, 9, 9, 12, 12, 15, 15, 19, 19, 23, 23, 27, 27, 31, 31, 35, 35, 40, 40, 45, 45, 50, 50, 55, 55, 60, 60, 65, 65, 70, 70, 75, 75, 80, 80, 85, 85, 90, 90, 95, 95, 100, 100, 105, 105, 110, 110, 116, 116, 122, 122, 129, 129, 135, 135

Offset: 1

David Eppstein, Aug 15 2017

nonn

The convex layers of a point set are obtained by finding the convex hull, removing its vertices, and continuing recursively with the remaining points.

As can be seen in the subsequence 122, 129, 129, 135, the nonzero differences of consecutive sequence values do not grow monotonically.

			For n=3, the a(3)=3 convex layers of a 3 X 3 grid are (1) the four corner points, (2) the four side midpoints, and (3) the center point.

S. Har-Peled and B. Lidicky, Peeling the grid, arXiv:1302.3200 [cs.DM], 2013.
S. Har-Peled and B. Lidicky, Peeling the Grid, SIAM J. Discrete Math., Vol. 27, No. 2 (2013), 650-655.

Cf. A293596.

For every n, a(2n) = a(2n-1).

As Har-Peled and Lidicky (2013) proved, this sequence grows proportionally to n^{4/3}.

A275432 P-positions for the subtraction game whose allowed moves are the practical numbers (A005153).

Original entry on oeis.org

0, 3, 10, 13, 44, 47, 102, 105, 146, 149, 232, 235, 636, 639, 814, 817, 950, 953, 1208, 1211, 2994, 2997, 4922, 4925, 4996, 4999, 6748, 6751, 8026, 8029, 8478, 8481, 12092, 12095, 14004, 14007, 31934, 31937, 35824, 35827, 41568, 41571, 46118, 46121, 60056, 60059, 62530, 62533, 106986, 106989

Offset: 0

David Eppstein, Nov 20 2016

nonn

According to a general theorem of Golomb (1966) on subtraction games, this sequence is infinite, and more strongly (because of known results on the density of A005153) the number of terms below any given n is at least logarithmic in n.

			For instance, 10 is a P-position because each of the available moves (subtracting 1, 2, 4, 6, or 8 to yield 9, 8, 6, 4, or 2) can be countered: from 8, 6, 4, or 2, it is possible to win by moving directly to 0 and from 9 it is possible to win by subtracting 6 and moving to the smaller P-position 3.

S. W. Golomb, A mathematical investigation of games of "take-away", J. Combinatorial Theory, 1 (1966), 443-458.

Cf. A030193.

cp's OEIS Frontend

User: David Eppstein

A375492 Number of compositions of n into powers of two that each divide the sum of previous powers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A348167 Numbers whose binary representation contains a maximal set of nonconsecutive 1's.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A343245 Hyperplane-counting upper bound on the number of sorted orders of X+Y for two lists X and Y of length n.

Views

Author

Keywords

Comments

Examples

Links

Formula

A331235 The number of simple polygons having all points of a 3 X n grid as vertices.

Views

Author

Keywords

Comments

Links

Programs

Python

A302757 a(n) is the smallest number whose greedy representation as a sum of terms of A126684 uses n terms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A297963 The smallest position with nim-value n in subtract-a-square game.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A296840 The smallest positive integer whose greedy representation as a sum of 3-smooth numbers (A003586) requires n terms.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A293596 The number of vertices on successive convex layers of the positive quadrant of the two-dimensional integer grid.

Views

Author

Keywords

Examples

Links

Crossrefs

A290966 The number of convex layers in an n X n grid of points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula