Alex Meiburg - cp's OEIS frontend

A360839 Number of minimal graphs of twin-width 2 on n unlabeled vertices.

1, 6, 32, 103, 250, 220

Offset: 5

Alex Meiburg, Feb 24 2023

a(n) is the number of graphs on n nodes that have twin-width exactly 2, such that deletion of any single vertex would reduce the twin-width. That is, the graphs of twin-width 2 that are minimal under the induced subgraph order.
All such graphs are connected, have connected complements, and have no twins. If a graph is counted, so is its complement.
The only known self-complementary graphs are the 5-cycle and a particular n=8 graph with G6 code "GCpfK{". These are the only two, at least up through n=10. Thus a(5) and a(8) are odd while the rest are even.
It is known that a(n) >= 1 for any n >= 5, as the n-cycle is always a valid example for n >= 5.
The corresponding sequence for twin-width 1 is very simple: 1,0,0,0,... with offset 4, as the 4-vertex path (path of length 3) is the unique minimal graph of twin-width 1. Starting with n=8, there are graphs of twin-width 3; this sequence only counts those of twin-width 2.

			For n=5, the only case is the 5-cycle C5, thus a(5)=1 is the first term.
For n=6, there are the C6, the S3, and Antenna graphs (by the terminology of GraphClasses.org, see Links), and their complements. Thus a(6)=6.

Édouard Bonnet et al., Introduction to Twin-width.
Édouard Bonnet et al., Twin-width I: tractable FO model checking, arXiv:2004.14789 [cs.DS], 2020-2021.
GraphClasses, List of Small Graphs.

A346695 Numbers with more divisors than digits in their binary representation.

Original entry on oeis.org

6, 12, 18, 20, 24, 28, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100, 102, 104, 105, 108, 110, 112, 114, 120, 126, 132, 140, 144, 150, 156, 160, 162, 168, 176, 180, 192, 196, 198, 200, 204, 208, 210, 216, 220, 224, 225, 228, 234, 240, 252, 260

Offset: 1

Alex Meiburg, Jul 29 2021

Not all terms are perfect or abundant, with 105 being the first deficient term.
There are no primes in the sequence, and 6 is the only semiprime.
By the same comments as those at A175495, this sequence is infinite.
This sequence is a subsequence of A175495.
It is natural to conjecture that this sequence has asymptotic density 0. However, after the first three terms where a(n)/n = 6 -- a function which would increase to infinity if the asymptotic density were zero -- it drops, and it seems to take a long time to get that high again. The first time it gets above 5.0 is at a(30243)=151216. Even as high as a(2188516)=10000000, the density is only ~1/4.57.
The number of terms with m binary digits is Sum_{k>m} A346730(m,k). - Jon E. Schoenfield, Jul 31 2021

			12 has 6 divisors: {1,2,3,4,6,12}. 12 is written in binary as 1100, which has 4 digits. Since 6 > 4, 12 is in the sequence.

Cf. A000005, A070939.
Cf. A135772 (equal number rather than more).
Cf. A175495 (where "binary digits in n" is replaced by "log_2(n)").

Select[Range[1000], (DivisorSigma[0, #] > Floor[1 + Log2[#]]) &]

isok(m) = numdiv(m) > #binary(m); \\ Michel Marcus, Jul 29 2021

from sympy import divisor_count
def ok(n): return divisor_count(n) > n.bit_length()
print(list(filter(ok, range(1, 261)))) # Michael S. Branicky, Jul 29 2021

A297359 Array read by antidiagonals: Pascal-like recursion and self-referential boundaries.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 2, 4, 6, 4, 2, 1, 6, 10, 10, 6, 1, 1, 7, 16, 20, 16, 7, 1, 3, 8, 23, 36, 36, 23, 8, 3, 3, 11, 31, 59, 72, 59, 31, 11, 3, 1, 14, 42, 90, 131, 131, 90, 42, 14, 1, 2, 15, 56, 132, 221, 262, 221, 132, 56, 15, 2, 4, 17, 71, 188, 353, 483, 483, 353, 188, 71, 17, 4, 6, 21, 88, 259, 541, 836, 966, 836, 541, 259

Offset: 1

Alex Meiburg, Dec 29 2017

Array with recursion T(i,j) = T(i-1,j) + T(i,j-1), and boundaries T(0,n) = T(n,0) = a(n). Here a(n) is the array T read by antidiagonals. Require that a(0)=a(1)=1.

			The array looks like
  1,  1,  1,   1,   2,    1,    1,    3,    3,   1,   2, ...
  1,  2,  3,   4,   6,    7,    8,   11,   14,  15,  17, ...
  1,  3,  6,  10,  16,   23,   31,   42,   56,  71,  88, ...
  1,  4, 10,  20,  36,   59,   90,  132,  188, 259, 347, ...
  2,  6, 16,  36,  72,  131,  221,  353,  541, 800, ...
  1,  7, 23,  59, 131,  262,  483,  836, 1377, ...
  1,  8, 31,  90, 221,  483,  966, 1802,  ...
  3, 11, 42, 132, 353,  836, 1802,  ...
  3, 14, 56, 188, 541, 1377,  ...
  1, 15, 71, 259, 800,  ...
  2, 17, 88, 347, ...
... [Table corrected and reformatted by _Jon E. Schoenfield_, Jan 14 2018]
The defining property is that when this array is read by antidiagonals we get 1,1,1,1,2,1,... which is both the sequence itself and the top row and first column of the array.

Alex Meiburg, Table of n, a(n) for n = 1..19999

Cf. A283682, A283681, A283683.

See also A007318, A297495, A297497, A297188 (antidiagonal sums).

t[a_, b_] := (t[a, b] = t[a, b - 1] + t[a - 1, b]);
t[0, x_] := a[x]; t[x_, 0] := a[x];
a[0] = 1; a[1] = 1;
a[x_] := With[{k = Floor[(Sqrt[8 x + 1] - 1)/2]},
  t[x - k (k + 1)/2, (k + 1) (k + 2)/2 - x - 1]]
a /@ Range[60]
TableForm[ Table[t[i, j], {i, 0, 5}, {j, 0, 12}]]

A297347 List of y-coordinates in the Babylonian Spiral.

Original entry on oeis.org

0, 1, 2, 2, 1, -1, -4, -7, -10, -10, -9, -6, -2, 3, 8, 13, 17, 20, 20, 19, 17, 13, 7, 0, -7, -13, -15, -12, -7, 1, 9, 17, 23, 26, 21, 13, 4, -5, -14, -22, -25, -21, -14, -6, 4, 14, 23, 26, 19, 9, 0, 0, 1, 3, 11, 20, 30, 41, 53, 65, 76, 78, 71, 59, 48, 44, 53, 63, 75, 88, 101

Offset: 1

Alex Meiburg, Dec 28 2017

The "Babylonian Spiral" is defined and illustrated in A256111.

			The first few points are (0,0), (0,1), (1,2), (3,2) -- thus the sequence starts out 0, 1, 2, 2.

Alex Meiburg, Table of n, a(n) for n = 1..10000
Lars Blomberg, Illustrations of 100, 1000 and 10000 terms of the spiral.
MathPickle, Babylonian Spiral

The x-coordinates are given in A297346. Norms of vectors are given in A256111.

NextVec[{x_, y_}] :=
Block[{n = x^2 + y^2 + 1}, While[SquaresR[2, n] == 0, n++];
  TakeSmallestBy[
     Union[Flatten[(Transpose[
        Transpose[Tuples[{1, -1}, 2]] #] & /@
        ({{#[[1]], #[[2]]}, {#[[2]], #[[1]]}})) & /@
     PowersRepresentations[n, 2, 2], 2]],
  Mod[ArcTan[#[[2]], #[[1]]] - ArcTan[y, x], 2 Pi] &, 1][[1]]
]
Accumulate[NestList[NextVec, {0, 1}, 500]][[;; , 2]]

A297346 List of successive x-coordinates in the Babylonian Spiral.

Original entry on oeis.org

0, 0, 1, 3, 5, 7, 7, 6, 4, 0, -4, -7, -9, -9, -8, -6, -2, 3, 9, 15, 21, 26, 29, 29, 28, 24, 17, 10, 4, 4, 5, 7, 13, 21, 28, 32, 32, 31, 29, 24, 15, 6, -1, -7, -8, -6, -1, 9, 17, 21, 15, 4, -7, -18, -26, -33, -39, -43, -43, -42, -37, -25, -15, -12, -18, -30, -39, -47, -52, -53, -51, -48, -42, -33, -22, -10, 3, 17, 31, 45, 56, 62, 54, 40, 27

Offset: 1

Alex Meiburg, Dec 28 2017

The "Babylonian Spiral" is defined and illustrated in A256111. See also the MathPickle link.

			The first few points are (0,0), (0,1), (1,2), (3,2) -- thus the sequence starts out 0, 0, 1, 3.

Alex Meiburg, Table of n, a(n) for n = 1..10000
Lars Blomberg, Illustrations of 100, 1000 and 10000 terms of the spiral.
MathPickle, Babylonian Spiral
Hugo Pfoertner, Illustration of spiral using Plot 2.

The y-coordinates are given in A297347. Norms of vectors are given in A256111.

NextVec[{x_, y_}] :=
Block[{n = x^2 + y^2 + 1}, While[SquaresR[2, n] == 0, n++];
  TakeSmallestBy[
     Union[Flatten[(Transpose[
        Transpose[Tuples[{1, -1},2]] #] & /@
        ({{#[[1]], #[[2]]}, {#[[2]], #[[1]]}})) & /@
     PowersRepresentations[n, 2, 2], 2]],
  Mod[ArcTan[#[[2]], #[[1]]] - ArcTan[y, x], 2 Pi] &, 1][[1]]
]
Accumulate[NestList[NextVec, {0, 1}, 500]][[;; , 1]]

~

A260273 Successively add the smallest nonzero binary number that is not a substring.

Original entry on oeis.org

1, 3, 5, 8, 11, 15, 17, 20, 23, 27, 31, 33, 36, 39, 44, 51, 56, 61, 65, 68, 71, 76, 81, 84, 87, 91, 95, 99, 104, 111, 115, 120, 125, 129, 132, 135, 140, 145, 148, 151, 157, 165, 168, 171, 175, 179, 186, 190, 194, 199, 204, 209, 216, 223, 227, 232, 241, 246

Offset: 1

Alex Meiburg, Jul 22 2015

a(n) is at least Omega(n), at most O(n*log(n)).
The empirical approximation n*(log(n)/2 + exp(1)) is startlingly close to tight, compared with many increasing upper bounds.
A261644(n) = A062383(a(n)) - a(n). - Reinhard Zumkeller, Aug 30 2015

			Begin with a(1)=1, in binary, "1". This contains the string "1" but not "10", so we add 2. Thus a(2)=1+2=3. This also contains "1" but not "10", so we move to a(3)=3+2=5. This contains "1" and "10" but not "11", so we add 3. Thus a(4)=5+3=8. (See A261018 for the successive numbers that are added. - _N. J. A. Sloane_, Aug 17 2015)

Alex Meiburg, Table of n, a(n) for n = 1..20000

See A261922 and A261461 for the smallest missing number function; also A261923, A262279, A261281.
Cf. A030308, A261015, A261016, A261017, A261019.
See also A261396 (when a(n) just passes a power of 2), A261416 (the limiting behavior just past a power of 2).
First differences are A261018.
A262288 is the decimal analog.
Cf. A261644, A062383.

a260273 n = a260273_list !! (n-1)
a260273_list = iterate (\x -> x + a261461 x) 1
-- Reinhard Zumkeller, Aug 30 2015, Aug 17 2015

public static void main(String[] args) {
   int a=1;
   for(int iter=0;iter<100;iter++){
       System.out.print(a+", ");
       int inc;
       for(inc=1; contains(a,inc); inc++);
       a+=inc;
   }
}
static boolean contains(int a,int test){
   int mask=(Integer.highestOneBit(test)<<1)-1;
   while(a >= test){
       if((a & mask) == test) return true;
       a >>= 1;
   }
   return false;
}

sublistQ[L1_, L2_] := Module[{l1 = Length[L1], l2 = Length[L2], k}, If[l2 <= l1, For[k = 1, k <= l1 - l2 + 1, k++, If[L1[[k ;; k + l2 - 1]] == L2, Return[True]]]]; False];
a[1] = 1; a[n_] := a[n] = Module[{bb = IntegerDigits[a[n-1], 2], k}, For[k = 1, sublistQ[bb, IntegerDigits[k, 2]], k++]; a[n-1] + k]; Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Apr 01 2016 *)
NestList[Function[k, k + FromDigits[#, 2] &@ SelectFirst[IntegerDigits[Range[2^8], 2], Length@ SequencePosition[IntegerDigits[k, 2], #] == 0 &]], 1, 64] (* Michael De Vlieger, Apr 01 2016, Version 10.1 *)

A260273_list, a = [1], 1
for i in range(10**3):
    b, s = 1, format(a,'b')
    while format(b,'b') in s:
        b += 1
    a += b
    s = format(a,'b')
    A260273_list.append(a) # Chai Wah Wu, Aug 26 2015

a(n+1) = a(n) + A261461(a(n)). - Reinhard Zumkeller, Aug 30 2015

A180263 Odd k such that (k^2 + 1)/2 is not prime.

Original entry on oeis.org

1, 7, 13, 17, 21, 23, 27, 31, 33, 37, 41, 43, 47, 53, 55, 57, 63, 67, 73, 75, 77, 81, 83, 87, 89, 91, 93, 97, 99, 103, 105, 107, 109, 111, 113, 115, 117, 119, 123, 125, 127, 129, 133, 135, 137, 143, 147, 149, 151, 153, 155, 157, 161, 163, 167, 173, 177, 179, 183, 185

Offset: 1

Alex Meiburg, Aug 21 2010

nonn

			a(2)=7: (7^2 + 1)/2 = 25, which is not prime, so 7 is in the sequence.
(9^2 + 1)/2 = 41, which is prime, so 9 is not in the sequence.

Harvey P. Dale, Table of n, a(n) for n = 1..2000

Cf. A027862 (primes of the form (n^2+1)/2).

[ n: n in [1..200 by 2] | not IsPrime((n^2+1) div 2) ];

a={};For[i=1,i<100,i=i+2,If[PrimeQ[(i^2+1)/2],0,AppendTo[a,i]]]Print[a]
Select[Range[1,201,2],!PrimeQ[(#^2+1)/2]&] (* Harvey P. Dale, Jan 07 2016 *)

isok(n) = (n%2) && !isprime((n^2 + 1)/2); \\ Michel Marcus, Nov 23 2018

More terms from Vincenzo Librandi, Nov 18 2010

Example clarified by Harvey P. Dale, Jan 07 2016

cp's OEIS Frontend

User: Alex Meiburg

A360839 Number of minimal graphs of twin-width 2 on n unlabeled vertices.

Views

Author

Keywords

Comments

Examples

Links

A346695 Numbers with more divisors than digits in their binary representation.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

A297359 Array read by antidiagonals: Pascal-like recursion and self-referential boundaries.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A297347 List of y-coordinates in the Babylonian Spiral.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A297346 List of successive x-coordinates in the Babylonian Spiral.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A260273 Successively add the smallest nonzero binary number that is not a substring.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Java

Mathematica

Python

Formula

A180263 Odd k such that (k^2 + 1)/2 is not prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions