Warren D. Smith - cp's OEIS frontend

A269747 Number of regular tetrahedra in an n-node-per-edge tetrahedral grid.

0, 0, 1, 5, 16, 39, 80, 155, 281, 476, 760, 1154, 1686, 2394, 3331, 4551, 6110, 8065, 10486, 13461, 17079, 21430, 26606, 32726, 39928, 48360, 58183, 69573, 82708, 97767, 114930, 134387, 156329, 180960, 208506, 239230, 273444, 311486, 353709, 400467, 452136, 509093, 571716, 640393, 715537

Offset: 0

Warren D. Smith, Mar 21 2016; more terms Mar 23 2016

nonn

Number of ways to choose 4 points forming a regular tetrahedron out of the binomial(n+2,3) points in a regular tetrahedral grid.
The tetrahedra defined by the four points may have any orientation.
Similar to A216173, which differs from the present sequence in a mysterious way.

Cf. A000332 (2-D version), A216173, A270805, A270806.

It would be nice to have a g.f. - N. J. A. Sloane, Mar 21 2016

a(21) changed from 24130 to 21430 by Anthony Guttmann, Mar 07 2023

A269746 Maximal number of 1's in an equilateral triangle of 0's and 1's with n points on each side, the entries being constant on vertical lines, with property that no three 1's form a triangle with sides parallel to the edges of the triangle.

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 13, 16, 20, 24, 28, 32, 36, 40

Offset: 1

Warren D. Smith and N. J. A. Sloane, Mar 20 2016

The triangle is oriented with apex at the top and horizontal base.

Label the entries in the top left and right edges with the numbers 1 through 2n-1, and let S denote the subset of [1..2n-1] where these edges contains 1's. Then the matrix has the no-subtriangle property iff S contains no three-term arithmetic progression.

			n, a(n), example of optimal S:
1, 1, [1]
2, 2, [1, 2]
3, 4, [1, 3, 4]
4, 6, [1, 2, 4, 5]
5, 8, [2, 3, 5, 6]
6, 10, [3, 4, 6, 7]
7, 13, [1, 5, 7, 8, 10]
8, 16, [1, 2, 7, 8, 10, 11]
9, 20, [1, 3, 4, 9, 10, 12, 13]
10, 24, [1, 2, 4, 5, 10, 11, 13, 14]
11, 28, [2, 3, 5, 6, 11, 12, 14, 15]
12, 32, [3, 4, 6, 7, 12, 13, 15, 16]
13, 36, [4, 5, 7, 8, 13, 14, 16, 17]
14, 40, [5, 6, 8, 9, 14, 15, 17, 18]
...
For example, the line 5, 8, [2, 3, 5, 6] corresponds to the triangle
....1....
...0.1...
..1.1.0..
.1.0.1.0.
0.1.1.0.0
and the value a(5) = 8.
It is a plausible conjecture that any optimal solution S here is also an optimal solution to the square grid version in A269745, and vice versa. (The square grid being obtained by reflecting the triangle in its base.)

This is a lower bound on A227308.

Cf. A003002, A269745.

A269745 Maximal number of 1's in an n X n {0,1} Toeplitz matrix with property that no four 1's form a square with sides parallel to the edges of the matrix.

Original entry on oeis.org

1, 3, 6, 10, 14, 18, 23, 29, 36, 44, 52, 60, 68, 76

Offset: 1

Warren D. Smith and N. J. A. Sloane, Mar 19 2016

Label the entries in the left edge and top row (reading from the bottom left to the top right) with the numbers 1 through 2n-1, and let S denote the subset of [1..2n-1] where the matrix contains 1's. Then the matrix has the no-subsquare property iff S contains no three-term arithmetic progression.

			n, a(n), example of optimal S:
1, 1, [1]
2, 3, [1, 2]
3, 6, [1, 3, 4]
4, 10, [1, 2, 4, 5]
5, 14, [2, 3, 5, 6]
6, 18, [3, 4, 6, 7]
7, 23, [1, 5, 7, 8, 10]
8, 29, [1, 2, 7, 8, 10, 11]
9, 36, [1, 3, 4, 9, 10, 12, 13]
10, 44, [1, 2, 4, 5, 10, 11, 13, 14]
11, 52, [2, 3, 5, 6, 11, 12, 14, 15]
12, 60, [3, 4, 6, 7, 12, 13, 15, 16]
13, 68, [4, 5, 7, 8, 13, 14, 16, 17]
14, 76, [5, 6, 8, 9, 14, 15, 17, 18]
...
For example, the line 5, 14, [2, 3, 5, 6] corresponds to the Toeplitz matrix
11000
01100
10110
11011
01101
and the value a(5) = 14.

This is a lower bound on A227133.
See A269746 for the analogous sequence for a triangular grid.
Cf. A003002.

a(14) from N. J. A. Sloane, May 05 2016

A172161 Greedy Coppersmith-Winograd sequence.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 9, 13, 20, 30, 45, 67, 101, 151, 227, 340, 510, 765, 1148, 1722, 2583, 3874, 5811, 8717, 13075, 19613, 29419, 44129, 66193, 99290, 148935, 223402, 335103, 502655, 753982, 1130973, 1696460, 2544690, 3817035, 5725552

Offset: 1

Warren D. Smith, Jan 27 2010

Coppersmith & Winograd asked for dense sets S of integers such that if A,B,C are three disjoint subsets of S, their sums are cannot all be equal. Such sets yield new matrix multiplication algorithms. This is the "greedy sequence" obeying this property, that is, we start with S = {0, 1} and adjoin new integers one at a time, always adjoining the least new integer such that the Coppersmith-Winograd property remains valid. It looks as though each term is approximately 1.5 times the preceding term. The sequence is clearly infinite because each term is no greater than the sum of all previous terms.
Amazingly, this sequence appears to agree with McRae's sequence A120134 after the "3". (This probably can be proved, but I haven't yet.) - Warren D. Smith, Jan 29 2010
Considering the A120134 tie-in comment, via the Maiga link, its alternate algorithm generates both a(n) and A120134(m) for n >= 1 and m >= 1.
That algorithm applies b(0)=2, b(1)=2, b(2)=3, b(3)=5, b(4)=8 then b(n) = floor(3*b(n-1)/2). Then a(n) = first differences of b(n), while A120134(m) begins from b(5) - b(4). - Bill McEachen, Dec 02 2022
This sequence is complete: every positive integer is the sum of a subset of its terms. - Charles R Greathouse IV, Dec 02 2022

			For a(6), if 5 were chosen, the sets {1, 4}, {2,3}, and {5} would all have the same sum. Clearly a(6) = 6 works because 0+1+2+3+4 = 10 < 2*6.

Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, 9 (1990) 251-280.
Jon Maiga, Computer-generated formulas for A172161, Sequence Machine.

Cf. A120134.

first(n)=if(n<6, return([0..n-1])); my(v=vector(n),s=3); v[2]=1; v[3]=2; v[4]=3; for(i=5,n, v[i]=(s+=v[i-1])\2+1); v \\ Charles R Greathouse IV, Dec 02 2022

Conjecture: a(n) ~ k*(3 / 2)^n for some k. - Bill McEachen, Dec 02 2022

a(n) = floor((Sum_{i 4. - Charles R Greathouse IV, Dec 02 2022

Two more terms from Warren D. Smith, Jan 29 2010

Extended by Charles R Greathouse IV, Dec 02 2022

A123509 Rohrbach's problem: a(n) is the largest integer such that there exists a set of n integers that is a basis of order 2 for (0, 1, ..., a(n)-1).

Original entry on oeis.org

1, 3, 5, 9, 13, 17, 21, 27, 33, 41, 47, 55, 65, 73, 81, 93, 105, 117, 129, 141, 153, 165, 181, 197, 213

Offset: 1

Warren D. Smith, Oct 02 2006

Notation: N[q] = the set of q+1 elements inside {0,1,...,N-1}
Length of the longest sequence of consecutive integers that can be obtained from a set of n distinct integers by summing any two integers in the set or doubling any one. - Jon E. Schoenfield, Jul 16 2017
According to Zhining Yang, Jul 08 2017, a(13) to a(20) are 65, 70, 79, 90, 101, 112, 123, 134, but there is some doubt about these terms, and they should be confirmed before they are accepted. They do not agree with the conjecture, so perhaps the VBA program is not correct.
The definition of Rohrbach's Problem in the paper of S. Gunturk and M. B. Nathanson in the links is different from the one here. In the paper, the set should contain n nonnegative integers instead of integers. The result should be equal to A001212(n-1)+1 according to the definition in the paper since adding one 0 before any set for A001212(n-1) provides a set of the problem. The data provided by Zhining Yang is obviously wrong since a(n) >= A001212(n-1)+1. And A302648 provides another lower bound of this array since a(n) >= 2*A302648(n)+1. - Zhao Hui Du, Apr 13 2018

			Example: 8[3]: 0,1,3,4 means {0,1,2,...,8} is covered thus: 0=0+0, 1=0+1, 2=1+1, 3=0+3, 4=0+4=1+3, 5=1+4, 6=3+3, 7=3+4, 8=4+4.
N[q]: set
------------------------------
3[2]: 0,1,
4[3]: 0,1,2,
5[3]: 0,1,2,
6[3]: 0,2,3,
7[4]: 0,1,2,3,
8[4]: 0,1,3,4,
9[4]: 0,1,3,4,
10[5]: 0,1,2,4,5,
11[5]: 0,1,2,4,5,
12[5]: 0,1,3,5,6,
13[5]: 0,1,3,5,6,
14[6]: 0,1,2,4,6,7,
15[6]: 0,1,2,4,6,7,
16[6]: 0,1,3,5,7,8,
17[6]: 0,1,3,5,7,8,
18[6]: 0,2,3,7,8,10,
19[7]: 0,1,2,4,6,8,9,
20[7]: 0,1,3,5,7,9,10,
21[7]: 0,1,3,5,7,9,10,
22[7]: 0,2,3,7,8,10,11,
23[8]: 0,1,2,4,6,8,10,11,
24[8]: 0,1,3,5,7,9,11,12,
25[8]: 0,1,3,5,7,9,11,12,
26[8]: 0,2,3,7,8,10,12,13,
27[8]: 0,1,3,4,9,10,12,13,
28[8]: 0,2,3,7,8,12,13,15,
29[9]: 0,1,3,5,7,9,11,13,14,
30[9]: 0,2,3,7,8,10,12,14,15,
31[9]: 0,1,3,4,9,10,12,14,15,
32[9]: 0,2,3,7,8,12,13,15,16,
a(5)=13 because we can obtain at most a total of 13 consecutive integers from a set of 5 integers by summing any two integers in the set or doubling any one; from the 5-integer set {1,2,4,6,7}, we can obtain all 13 integers in the interval [2..14] as follows: 2=1+1, 3=1+2, 4=2+2, 5=1+4, 6=2+4, 7=1+6, 8=2+6, 9=2+7, 10=4+6, 11=4+7, 12=6+6, 13=6+7, 14=7+7.
a(16)=90 because we can obtain at most a total of 90 consecutive integers from a set of 16 integers by summing any two integers in the set or doubling any one: from the 16-integer set {1,2,4,5,8,9,10,17,18,22,25,36,47,58,69,80}, we can obtain all 90 integers in the interval [2..91]. - _Jon E. Schoenfield_, Jul 16 2017

S. Gunturk and M. B. Nathanson, A new upper bound for finite additive bases, Acta Arithmetica, Vol. 124, No. 3 (2006) 235-255.
Jürgen Herzog, Shinya Kumashiro, and Dumitru I. Stamate, The tiny trace ideals of the canonical modules in Cohen-Macaulay rings of dimension one, arXiv:2106.09404 [math.AC], 2021. See p. 9.
Jürgen Herzog, Shinya Kumashiro, and Dumitru I. Stamate, The far-flung Gorenstein property for numerical semigroups, Extended abstract for IMNS 2024. See p. 3.
Kagawa, VBA program
H. Rohrbach, Ein Beitrag zur additiven Zahlentheorie, Math. Z. 42 (1937) 1-30. DOI
W. D. Smith, More information

Cf. A001212, A008932.

a(n) = A001212(n-1)+1 (conjecture). - R. J. Mathar, Oct 08 2006. Comment from Martin Fuller, Mar 18 2009: I agree with this conjecture.

lim inf a(n) / n^2 > 0.2857 lim sup a(n) / n^2 < 0.4789 - Charles R Greathouse IV, Aug 11 2007

More terms (from Smith's web site) from R. J. Mathar, Oct 08 2006
Entry revised by N. J. A. Sloane, Aug 06 2017
a(13)-a(25) from Herzog et al. added by Stefano Spezia, Jul 05 2024

A122916 Minimum number of n-candidate full-rank-order ballots required to instantiate any tournament on n nodes (where A beats B in the tournament if and only if it does so in a majority of the ballots and we forbid pairwise ties).

Original entry on oeis.org

1, 3, 3, 3, 3

Offset: 1

Warren D. Smith, Sep 19 2006

Every entry is an odd number. a(n) <= a(n+1) <= a(n)+4. For all large enough n we know Cn/log(n) < a(n) < Kn/log(n) for suitable constants 0= 5.

P. Erdos and L. Moser, On the representation of directed graphs as unions of orderings, Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964) 125-132; also reprinted in Paul Erdos: The art of counting, Selected writings (ed. Joel Spencer) MIT Press 1973, pp. 79-86.
Warren D. Smith, Answer to puzzle 28 (surveys the problem)
Richard Stearns, The voting problem, Amer. Math. Monthly 66 (1959) 761-763. Warning: Erdos, Moser and Stearns actually consider a slightly different problem definition, where ties are allowed. That would define a different sequence which would upper-bound this one and is related to it, but the present sequence seems to be a little more pleasant.

A122026 Least number m such that every tournament with at least m nodes contains the acyclic n-node tournament.

Original entry on oeis.org

0, 1, 2, 4, 8, 14, 28

Offset: 0

Warren D. Smith, Sep 11 2006

nonn

A Ramsey-like number but defined for tournaments (i.e., directed graphs in which each node-pair is joined by exactly one arc) rather than undirected graphs.
It is not hard to show that a(n) always exists and a(n) is nondecreasing.
The lower bounds a(4)>=8 and a(5)>=14 and a(6)>=28 arise from the cyclic tournaments with offsets 1,2,4 mod 7; the same is true of offsets 1,3,9,2,6,5 mod 13 and the "QRgraph" in GF(3^3) with 27 vertices.
The following lower bounds a(n)>=P+1 arise from QRgraph(P) where P is prime and P=3 (mod 4): a(8)>=48, a(9)>=84, a(10)>=108, a(12)>=200, a(13)>=272.
This is almost certainly different from the other sequences currently in the OEIS which begin 1,2,4,8,14,28.

K. B. Reid, Tournaments, in Handbook of Graph Theory; see p. 167.

W. D. Smith, Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs
Yahoo Groups, Range Voting
Range Voting Yahoo Group, Introduction. [Cached copy]
RangeVoting.org, Group Website.
W. D. Smith, Survey on directed graph Ramsey Numbers.

Cf. A122027, A003141.

A122027 Largest integer m such that every n-tournament contains a transitive (i.e., acyclic) sub-tournament with at least m vertices.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6

Offset: 1

Warren D. Smith, Sep 11 2006

K. B. Reid, Tournaments, in Handbook of Graph Theory; see p. 167.
D. J. Wildstrom, Design and serial construction of digraph braids, Journal of Mathematics and the Arts, Volume 9, Issue 1-2, 2015.

W. D. Smith, Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs
D. J. Wildstrom, Structural Qualities and Serial Construction of Tournament Braids, in Bridges 2012: Mathematics, Music, Art, Architecture, Culture.
Yahoo Groups, Range Voting
Range Voting Yahoo Group, Introduction. [Cached copy]
RangeVoting.org, Group Website.

Cf. A122026.

A058320 Distinct even prime-gap lengths (number of composites between primes), from 3+2, 7+4, 23+6,...

Original entry on oeis.org

2, 4, 6, 8, 14, 10, 12, 18, 20, 22, 34, 24, 16, 26, 28, 30, 32, 36, 44, 42, 40, 52, 48, 38, 72, 50, 62, 54, 60, 58, 46, 56, 64, 68, 86, 66, 70, 78, 76, 82, 96, 112, 100, 74, 90, 84, 114, 80, 88, 98, 92, 106, 94, 118, 132, 104, 102, 110, 126, 120, 148, 108

Offset: 0

Warren D. Smith, Dec 11 2000

Nicely and Nyman have sieved up to 1.3565*10^16 at least. They admit it is likely they have suffered from hardware or software bugs, but believe the probability the sequence up to this point is incorrect is <1 in a million. This sequence is presumably all even integers (in different order). It is not monotonic. The monotonic subsequence of record-breaking prime gaps is A005250.

Essentially the same as A014320. [From R. J. Mathar, Oct 13 2008]

Richard P. Brent, The first occurrence of large gaps between successive primes, Math. Comp. 27:124 (1973), 959-963.
Thomas R. Nicely, New maximal prime gaps and first occurrences, Math. Comput. 68,227 (1999) 1311-1315.
Thomas R. Nicely, First occurrence prime gaps [For local copy see A000101]

Cf. A008996, A005250.

Equals 2*A014321(n-1).

DeleteDuplicates[Differences[Prime[Range[2,200000]]]] (* Harvey P. Dale, Dec 07 2014 *)

Comment corrected by Harvey P. Dale, Dec 07 2014

A057821 a(n) is the least nonnegative integer k such that 2^n - k is a safe prime.

Original entry on oeis.org

1, 5, 9, 5, 21, 29, 9, 5, 9, 17, 45, 161, 165, 269, 285, 17, 45, 233, 9, 17, 321, 317, 633, 677, 405, 437, 189, 1385, 69, 209, 9, 641, 849, 137, 45, 401, 381, 437, 1965, 2201, 741, 1493, 573, 857, 1485, 5297, 2709, 161, 465, 473, 1269, 4805, 789

Offset: 3

Warren D. Smith, Nov 23 2000

nonn

Previous name was: "Useful safe primes: a(n) = least nonnegative integer k such that 2^n - k is prime and (2^n-k-1)/2 is also prime". The resulting sequence of 2^n-k terms: 7, 11, 23, 59, 107, ..., are thus the largest safe primes smaller than 2^n (A243916), a subsequence of A005385. - Michel Marcus, Jan 08 2014

Mark Andreas, Table of n, a(n) for n = 3..5120 (first 3070 terms from Artsiom Palkounikau)

Cf. A005385, A013603, A243916.

a(n) = {my(k=0); until (isprime(2^n-k) && isprime((2^n-k-1)/2), k++); return (k);} \\ Michel Marcus, Jun 29 2013

from sympy import isprime
def a(n):
    k=0
    while True:
        k+=1
        if isprime(2**n - k) and isprime((2**n - k - 1)//2): return k
print([a(i) for i in range(3, 21)]) # Indranil Ghosh, Jun 12 2017, after PARI code by Michel Marcus

cp's OEIS Frontend

User: Warren D. Smith

A269747 Number of regular tetrahedra in an n-node-per-edge tetrahedral grid.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A269746 Maximal number of 1's in an equilateral triangle of 0's and 1's with n points on each side, the entries being constant on vertical lines, with property that no three 1's form a triangle with sides parallel to the edges of the triangle.

Views

Author

Keywords

Comments

Examples

Crossrefs

A269745 Maximal number of 1's in an n X n {0,1} Toeplitz matrix with property that no four 1's form a square with sides parallel to the edges of the matrix.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A172161 Greedy Coppersmith-Winograd sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A123509 Rohrbach's problem: a(n) is the largest integer such that there exists a set of n integers that is a basis of order 2 for (0, 1, ..., a(n)-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A122916 Minimum number of n-candidate full-rank-order ballots required to instantiate any tournament on n nodes (where A beats B in the tournament if and only if it does so in a majority of the ballots and we forbid pairwise ties).

Views

Author

Keywords

Comments

Links

A122026 Least number m such that every tournament with at least m nodes contains the acyclic n-node tournament.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A122027 Largest integer m such that every n-tournament contains a transitive (i.e., acyclic) sub-tournament with at least m vertices.

Views

Author

Keywords

References

Links

Crossrefs

A058320 Distinct even prime-gap lengths (number of composites between primes), from 3+2, 7+4, 23+6,...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A057821 a(n) is the least nonnegative integer k such that 2^n - k is a safe prime.

Views