Alexander D. Healy - cp's OEIS frontend

A369692 Connected domination number of the n X n grid graph.

1, 2, 3, 7, 11, 14, 20, 26, 30, 39, 47, 52, 64, 74, 80, 95

Offset: 1

Alexander D. Healy, Feb 25 2024

			From _Andrew Howroyd_, Mar 06 2024: (Start)
a(16) = 95 = 16 + 5*14 + 4*2 + 1.
  . . . . . . . . . . . . . . . .
  X X X X X X X X X X X X X X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X .
(End)

Alexander D. Healy, Examples of (near-)optimal dominating sets for n <= 12
Eric Weisstein's World of Mathematics, Connected Domination Number.
Eric Weisstein's World of Mathematics, Grid Graph.

Cf. A104519, A287690, A302488, A370428.

Cf. A381730 (numbers of minimum connected dominating sets).

a(3*n) <= n*(3*n+1); a(3*n-1) <= 3*n^2 - 1; a(3*n-2) <= (n-1)*(3*n+1). Conjecturally these inequalities hold with equality for n > 1. - Andrew Howroyd, Mar 06 2024

a(10)-a(16) from Andrew Howroyd, Feb 25 2024

A370428 Connected domination number of the n X n king graph.

Original entry on oeis.org

1, 1, 1, 4, 5, 8, 12, 15, 20, 24, 28, 33, 39, 46, 52, 58

Offset: 1

Alexander D. Healy, Feb 24 2024

In other words, a(n) is the minimum number of kings that can be placed on an n X n chessboard such that (i) the occupied squares form a single connected component, and (ii) every square is either occupied by a king or adjacent to one that is.

a(17) <= 67; a(18) <= 75; a(19) <= 83; a(20) <= 92.

Alexander D. Healy, Examples of (near-)optimal connected dominating sets for n <= 20.
Eric Weisstein's World of Mathematics, Connected Domination Number.
Eric Weisstein's World of Mathematics, King Graph.

Cf. A075561, A289180, A302401, A369692.

Cf. A382206 (numbers of minimum connected dominating sets).

a(13)-a(16) from Andrew Howroyd, Feb 25 2024

A355477 Maximum number of skew-tetrominoes that can be packed into an n X n square.

Original entry on oeis.org

0, 0, 1, 3, 4, 8, 9, 14, 16, 23, 25, 33, 36, 46, 49, 60, 64, 77, 81, 96, 100

Offset: 1

Alexander D. Healy, Jul 03 2022

Skew-tetrominoes are tiles of the form:
   _
  |  |
    |_|
together with all rotations/reflections of this shape.
It is not hard to see that skew-tetrominoes cannot completely tile an n X n square, so a(n) < n^2/4.
The odd terms are easily understood: a(2m+1) = m^2.
A straightforward (greedy) construction shows that m^2 skew-tetrominoes (all with the same orientation) can be packed into a (2m+1) X (2m) rectangle. Therefore a(2m+1) >= m^2.
On the other hand, we also have a(2m+1) <= m^2: Consider all cells with indices of the form (2i, 2j); there are m^2 such cells in a (2m+1) X (2m+1) square. Moreover, any valid placement of a skew-tetromino must cover one of these cells, so a(2m+1) <= m^2.
The behavior of a(2m) appears more subtle; the initial terms satisfy a(2m) = m^2 - floor(m/2), but this formula breaks down at a(20) = 96 (not 95).
Additional terms:
(Lower bounds are from explicit constructions; upper bounds are from mixed-integer-programming search.)
a(22) in {116, 117}.
a(23) = 121.
a(24) = 139.
a(25) = 144.
a(26) in {163, 164}.
a(27) = 169.
a(28) in {190, 191}.
a(29) = 196.
a(30) in {218, 219, 220}.
a(31) = 225.
a(32) in {248, 249, 250, 251}.
a(33) = 256.
a(34) in {280, 281, 282, 283}.
a(35) = 289.
a(36) in {316, 317, 318}.
a(37) = 324.
a(38) in {352, 353, 354, 355}.
a(39) = 361.
a(40) in {388, 389, 390, 391, 392, 393, 394}.
a(41) = 400.
a(42) in {432, 433, 434}.

			a(8) = 14 by the following packing of 14 skew-tetrominoes into an 8 X 8 square:
   _______________
  |_|1 _| |___| |_|
  |___| 2_|3 _|_4 |
  |_ 5|_|___| | |_|
  | |___| | 6_|_7 |
  |_8 | 9_|_|_10|_|
  | |_|_|11_| |___|
  |_12|___|13_|14_|
  |_|_|___|_|___|_|

Alexander D. Healy, Examples of (near-)optimal packings for n <= 42
Wikipedia, Tetromino

Cf. A256535.

a(n) < n^2/4.

a(2m+1) = m^2.

A348574 Length of the shortest string over the alphabet {1,...,n} such that every subset of {1,...,n} appears as a substring (in some order).

Original entry on oeis.org

1, 2, 4, 8, 13, 24, 40

Offset: 1

Alexander D. Healy, Oct 23 2021

a(7) = 40 by computer search.
a(8) >= 73 by formula (1) of Lipski.
a(8) <= 76 using 12345671825473861253846275138427163587...
                 ...26341568237415876412573641823178456231.
a(9) >= 130 by formula (1) of Lipski.
a(9) <= 149 using 1234567891245739681253946175283419726538...
                  ...4926137845926374159837241856931728643...
                  ...1597246159283674981635781642391874562...
                  ...89751384973251697248567213864957684.

			a(4) = 8 because the string 12342413 contains every subset of {1,2,3,4} as a substring -- e.g., {1,3,4} can be found in the last three symbols ('413') -- and it can be shown that no string of length 7 has this property (see, e.g., Lipski 1978).
Examples of optimal strings for n <= 7:
1: 1
2: 12
3: 1231
4: 12342413
5: 1234512413524
6: 123415643641253624531625
7: 1234567214573126431523674256147325716357

I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, pp. 39-40.

W. Lipski, Jr., On strings containing all subsets as substrings, Discrete Mathematics 21, 1978, pp. 253-259.

Cf. A062714.

a(n) >= binomial(n, ceiling(n/2)) + ceiling(n/2) - 1. [Lipski, formula (1)]

a(n) >= n * ceiling(binomial(n, floor(n/2)) / n). [Lipski, formula (3)]

A061713 Number of closed walks of length n on a 3 X 3 X 3 Rubik's Cube.

Original entry on oeis.org

1, 0, 18, 36, 720, 3600, 42624, 312480, 3148032, 27073152, 261446688, 2407791936, 23168736768, 220481838720, 2137258661472

Offset: 0

Alexander D. Healy, Jun 21 2001

Number of n-move sequences on a 3 X 3 X 3 Rubik's Cube (quarter-twists and half-twists count as moves, cf. A060010) that leave the cube unchanged, i.e. closed walks of length n from a fixed vertex on the Cayley graph of the cube with {F, F^(-1), F^2, R, R^(-1), R^2, B, B^(-1), B^2, L, L^(-1), L^2, U, U^(-1), U^2, D, D^(-1), D^2} as the set of generators. Alternatively, the n-th term is equal to the sum of the n-th powers of the eigenvalues of this Cayley graph divided by the order of the Rubik's cube group, ~4.3*10^19 (see A054434).

			There are 18 closed walks of length 2: F*F^(-1), F^2*F^2, F^(-1)*F, R*R^(-1), R^(-1)*R, R^2*R^2 . . ., D*D^(-1), D^(-1)*D, D^2*D^2.

Cf. A060010, A054434.

A079312 a(n) = 4 * A079137(n).

Original entry on oeis.org

0, 0, 32, 0, 328, 2976, 25512, 124352, 758752, 4852448, 26735408, 145945312, 805129880, 4334341216, 22824469832, 119276925152, 617722010896, 3163151197504, 16059782780784, 80965219241952, 405344545960912

Offset: 1

Alexander D. Healy, Feb 11 2003

nonn

See A079137, which is the main entry for this problem.

Equals 4*A079137(n). Cf. A070030.

Incorrect description removed by Andrew Howroyd, Oct 12 2019

A080583 Number of positions that the 3 X 3 X 3 Rubik cube puzzle can be in after exactly n moves.

Original entry on oeis.org

1, 18, 262, 3502, 46741, 621649, 8240087, 109043123, 1441386411, 19037866206, 251285929522, 3314574738534, 43689000394782, 575342418679410

Offset: 0

Alexander D. Healy, Feb 21 2003

This is different from the sequence giving the number of positions that can be reached in n moves from the start, but which cannot be reached in fewer than n moves (A080601).
A half-turn is considered to be a single move (rather than two moves).
The total number of positions is 901083404981813616.
Relationship with A080601: 243 = 262 - 18 - 1, 3240 = 3502 - 262, 43239 = 46741 - 3502, ...

Mark Longridge, God's Algorithm Calculations for Rubik's Cube...
Rokicki, Tomas; God's Algorithm out to 13f*

Cf. A080601, A080602.

Added a(13). Tomas Rokicki, Jul 25 2009

A060010 Number of 2n-move sequences on the 3 X 3 X 3 Rubik's Cube (only quarter-twists count as moves) that leave the cube unchanged.

Original entry on oeis.org

1, 12, 312, 10464, 398208, 16323072, 702465024

Offset: 0

Alexander D. Healy, Mar 15 2001

I.e., closed walks of length 2n from a fixed vertex on the Cayley graph of the cube with {F, F^(-1), R, R^(-1), B, B^(-1), L, L^(-1) U, U^(-1), D, D^(-1)} as the set of generators. Alternatively, the n-th term is equal to the sum of the n-th powers of the eigenvalues of this Cayley graph divided by the order of the Rubik's cube group, ~4.3*10^19 (see A054434).

			There are 12 closed walks of length 2: F*F^(-1), F^(-1)*F, R*R^(-1), R^(-1)*R, ..., D*D^(-1), D^(-1)*D.

Cf. A054434, A061713, A080602.

A060200 Number of Sophie Germain primes <= prime(2^n).

Original entry on oeis.org

2, 3, 4, 8, 12, 20, 32, 54, 94, 170, 297, 549, 1017, 1895, 3505, 6577, 12388, 23565, 44891, 85922, 164299, 314173, 602624, 1158231, 2232286

Offset: 1

Alexander D. Healy, Mar 19 2001

nonn

Sophie Germain primes are primes p such that 2p+1 is also prime.

			The first four primes are 2, 3, 5 and 7. Three of these are Sophie Germain primes (since 2*2 + 1 = 5, 2*3 + 1 = 7 and 2*5 + 1 = 11 are prime, but 2*7 + = 15). Therefore the second value in the sequence is 3.

Cf. A049040.

<< NumberTheory`NumberTheoryFunctions` cnt = 0; currentPrime = 1; For[ i = 1, i == i, i ++, currentPrime = NextPrime[ currentPrime ]; If[ PrimeQ[ 2*currentPrime + 1 ], cnt++ ]; If[ IntegerQ[ Log[ 2, i ] ], Print[ cnt ] ]; ]

A061712 Smallest prime with Hamming weight n (i.e., with exactly n 1's when written in binary).

Original entry on oeis.org

2, 3, 7, 23, 31, 311, 127, 383, 991, 2039, 3583, 6143, 8191, 73727, 63487, 129023, 131071, 522239, 524287, 1966079, 4128767, 16250879, 14680063, 33546239, 67108351, 201064447, 260046847, 536739839, 1073479679, 5335154687, 2147483647, 8581545983, 16911433727, 32212254719

Offset: 1

Alexander D. Healy, Jun 19 2001

a(n) = 2^n - 1 for n in A000043, so Mersenne primes A000668 is a subsequence of this one. Binary length of a(n) is given by A110699 and the number of zeros in a(n) is given by A110700. - Max Alekseyev, Aug 03 2005

Drmota, Mauduit, & Rivat prove that a(n) exists for n > N for some N. - Charles R Greathouse IV, May 17 2010

			The fourth term is 23 (10111 in binary), since no prime less than 23 has exactly 4 1's in its binary representation.

Charles R Greathouse IV, Table of n, a(n) for n = 1..3320 (first 1024 terms from T. D. Noe)
Michael Drmota, Christian Mauduit, and Joel Rivat, Primes with an average sum of digits, Compositio Mathematica 145 (2009), pp. 271-292.
Kenichiro Kashihara, Letter to the Editor, Math. Scientist 20 (1) (1995), 67-68.
MathOverflow, Are there primes of every Hamming weight?
Samuel S. Wagstaff, Prime numbers with a fixed number of one bits or zero bits in their binary representation, Experimental Mathematics 10 (2001), pp. 267-273.

Cf. A000043, A000120, A000668, A001348, A014499, A049084, A066195, A110699, A110700.

a061712 n = fromJust $ find ((== n) . a000120) a000040_list
-- Reinhard Zumkeller, Feb 10 2013

with(combstruct):
a:=proc(n) local m,is,s,t,r; if n=1 then return 2 fi; r:=+infinity; for m from 0 to 100 do is := iterstructs(Combination(n-2+m),size=n-2); while not finished(is) do s := nextstruct(is); t := 2^(n-1+m)+1+add(2^i,i=s); # print(s,t);
if isprime(t) then r:=min(t,r) fi; od; if r<+infinity then return r fi; od; return 0; end: seq(a(n),n=1..60); # Max Alekseyev, Aug 03 2005

Do[k = 1; While[ Count[ IntegerDigits[ Prime[k], 2], 1] != n, k++ ]; Print[ Prime[k]], {n, 1, 30} ]
(* Second program: *)
a[n_] := Module[{m, s, k, p}, For[m=0, True, m++, s = {1, Sequence @@ #, 1} & /@ Permutations[Join[Table[1, {n-2}], Table[0, {m}]]] // Sort; For[k=1, k <= Length[ s], k++, p = FromDigits[s[[k]], 2]; If[PrimeQ[p], Print["a(", n, ") = ", p]; Return[p]]]]]; a[1] = 2; Array[a, 100] (* Jean-François Alcover, Mar 16 2015 *)
Module[{hw=Table[{n,DigitCount[n,2,1]},{n,Prime[Range[250*10^6]]}]}, Table[ SelectFirst[hw,#[[2]]==k&],{k,31}]][[All,1]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Jan 01 2019 *)

a(n)=forprime(p=2, , if (hammingweight(p) == n, return(p));); \\ Michel Marcus, Mar 16 2015

from itertools import combinations
from sympy import isprime
def A061712(n):
    l, k = n-1, 2**n
    while True:
        for d in combinations(range(l-1,-1,-1),l-n+1):
            m = k-1 - sum(2**(e) for e in d)
            if isprime(m):
                return m
        l += 1
        k *= 2 # Chai Wah Wu, Sep 02 2021

Conjecture: a(n) < 2^(n+3). - T. D. Noe, Mar 14 2008

A000120(a(n)) = A014499(A049084(a(n))) = n. - Reinhard Zumkeller, Feb 10 2013

Extended to 60 terms by Max Alekseyev, Aug 03 2005

Further terms from T. D. Noe, Mar 14 2008

cp's OEIS Frontend

User: Alexander D. Healy

A369692 Connected domination number of the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A370428 Connected domination number of the n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A355477 Maximum number of skew-tetrominoes that can be packed into an n X n square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A348574 Length of the shortest string over the alphabet {1,...,n} such that every subset of {1,...,n} appears as a substring (in some order).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A061713 Number of closed walks of length n on a 3 X 3 X 3 Rubik's Cube.

Views

Author

Keywords

Comments

Examples

Crossrefs

A079312 a(n) = 4 * A079137(n).

Views

Author

Keywords

Comments

Crossrefs

Extensions

A080583 Number of positions that the 3 X 3 X 3 Rubik cube puzzle can be in after exactly n moves.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A060010 Number of 2n-move sequences on the 3 X 3 X 3 Rubik's Cube (only quarter-twists count as moves) that leave the cube unchanged.

Views

Author

Keywords

Comments

Examples

Crossrefs

A060200 Number of Sophie Germain primes <= prime(2^n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A061712 Smallest prime with Hamming weight n (i.e., with exactly n 1's when written in binary).

Views

Author

Keywords