Mithra Karamchedu - cp's OEIS frontend

User: Mithra Karamchedu

Mithra Karamchedu has authored 4 sequences.

A372224 The size of the smallest critical set of hints needed to uniquely solve a generalized n X n Sudoku board.

0, 1, 2, 4, 6, 8, 12, 14, 17

Offset: 1

Agustin Gomez de la Vega and Mithra Karamchedu, Apr 22 2024

A "critical set" is a collection of Sudoku hints that uniquely determines a solution to the puzzle, but such that removing any hint no longer does so.
Our generalized n X n Sudoku board consists of n rows, n columns, and n lengthwise rectangular subgrids with dimensions A033676(n) X A033677(n). Every row, every column, and every subgrid must contain the digits 1..n.
When n is prime, a(n) is the size of smallest critical set of an n X n Latin square, which is conjectured to equal A002620(n).

			Below is a critical set of size 17 on the 9 X 9 Sudoku grid:
.
  +-------+-------+-------+
  |       | 8   1 |       |
  |       |       |   4 3 |
  | 5     |       |       |
  +-------+-------+-------+
  |       |   7   | 8     |
  |       |       | 1     |
  |   2   |   3   |       |
  +-------+-------+-------+
  | 6     |       |   7 5 |
  |     3 | 4     |       |
  |       | 2     | 6     |
  +-------+-------+-------+
.
which uniquely determines the solution:
.
  +-------+-------+-------+
  | 2 3 7 | 8 4 1 | 5 6 9 |
  | 1 8 6 | 7 9 5 | 2 4 3 |
  | 5 9 4 | 3 2 6 | 7 1 8 |
  +-------+-------+-------+
  | 3 1 5 | 6 7 4 | 8 9 2 |
  | 4 6 9 | 5 8 2 | 1 3 7 |
  | 7 2 8 | 1 3 9 | 4 5 6 |
  +-------+-------+-------+
  | 6 4 2 | 9 1 8 | 3 7 5 |
  | 8 5 3 | 4 6 7 | 9 2 1 |
  | 9 7 1 | 2 5 3 | 6 8 4 |
  +-------+-------+-------+

J. N. Cooper and A. Kirkpatrick, Critical Sets for Sudoku and General Graphs, Discrete Mathematics, 315-316 (2014), 112-119.
C. Lass, Minimal number of clues for Sudokus, Central European Journal of Computer Science, 2 (2012).
G. McGuire et al., There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration, Experimental Mathematics, 23 (2012), 190-217.

H. Chel, D. Mylavarapu, and D. Sharma, A novel multistage genetic algorithm approach for solving Sudoku puzzle, IEEE International Conference on Electrical, Electronics, and Optimization Techniques (2016), 1.

Cf. A002620, A002860, A198297.

When n is prime, a(n) is conjectured to equal A002620(n).

When n is square, a(n) = A198297(n).

A367055 Triangle read by rows: T(n, k) = A000120(n) + A000120(k), 0 <= k <= n.

Original entry on oeis.org

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

Offset: 0

Mithra Karamchedu and Sophia Pi, Nov 03 2023

T(n, k) is the sum of the Hamming weight of n and the Hamming weight of k.

See A365618 for a table read by antidiagonals.

			Triangle begins:
      k=0  1  2  3  4  5
  n=0:  0;
  n=1:  1, 2;
  n=2:  1, 2, 2;
  n=3:  2, 3, 3, 4;
  n=4:  1, 2, 2, 3, 2;
  n=5:  2, 3, 3, 4, 3, 4;
        ...

Cf. A000069, A000120, A000788, A001969, A365618.

T[n_, k_] := DigitCount[n, 2, 1] + DigitCount[k, 2, 1]

from math import comb, isqrt
def A367055(n): return (n-comb(r:=(m:=isqrt(k:=n+1<<1))+(k>m*(m+1)),2)).bit_count()+(r-1).bit_count() # Chai Wah Wu, Nov 11 2024

T(n, k) = A000120(n) + A000120(k).

A365618 Table read by antidiagonals: T(n, k) = A000120(n) + A000120(k).

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 2, 2, 2, 2, 1, 3, 2, 3, 1, 2, 2, 3, 3, 2, 2, 2, 3, 2, 4, 2, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 1, 4, 3, 4, 2, 4, 3, 4, 1, 2, 2, 4, 4, 3, 3, 4, 4, 2, 2, 2, 3, 2, 5, 3, 4, 3, 5, 2, 3, 2, 3, 3, 3, 3, 4, 4, 4, 4, 3, 3, 3, 3, 2, 4, 3, 4, 2, 5, 4, 5, 2

Offset: 0

Mithra Karamchedu and Sophia Pi, Nov 03 2023

T(n, k) is the sum of the Hamming weight of n and the Hamming weight of k.
Picking all points (n, k) such that T(n, k) <= N for some natural number N iteratively generates a Sierpinski-like fractal H. To generate the fractal, fix i and produce the set H_i = {(x, y) in [0, 1)^2 : T(floor(x * 2^i), floor(y * 2^i)) <= i}. Then, define the "limit fractal" H = {(x, y) in [0, 1)^2 : there exists N such that (x, y) is in H_i for all i >= N}.
The table is symmetric, T(n, k) = T(k, n).
See A367055 for a triangle read by rows.

			The table begins:
      k=0 1 2 3 4
  n=0:  0 1 1 2 1 ...
  n=1:  1 2 2 3 2 ...
  n=2:  1 2 2 3 2 ...
  n=3:  2 3 3 4 3 ...
  n=4:  1 2 2 3 2 ...

Mithra Karamchedu, Points (n, k), indicated in black, where T(n, k) <= 12, 0 <= n, k < 2^12.

Cf. A000120, A367055.

T[n_, k_] := DigitCount[n, 2, 1] + DigitCount[k, 2, 1]

T(n, k) = A000120(n) + A000120(k).

If n_1 and n_2 share no 1 bits in common, then T(n_1 + n_2, k) = A000120(n_1) + A000120(n_2) + A000120(k).

A363165 The number of spanning trees of the ladder graph L_n up to automorphisms of L_n.

Original entry on oeis.org

1, 1, 6, 17, 59, 204, 750, 2746, 10215, 37936, 141468, 527283, 1967449, 7340090, 27392124, 102219380, 381482477, 1423676862, 5313214098, 19829053909, 74002960983, 276182321224, 1030726172586, 3846720619566, 14356155740947, 53577895814828, 199955425410792

Offset: 1

Mithra Karamchedu and Lucas Bang, Jul 06 2023

The ladder graph L_n is the 2 X n grid graph.
L_n has two automorphisms when n = 1, eight automorphisms when n = 2, and four automorphisms when n >= 3.
When n = 1, Aut(L_n) = D_2; when n = 2, Aut(L_n) = D_8 (D_n is the dihedral group of order n). When n >= 3, Aut(L_n) = {e, h, v, r}, consisting of the identity (e), horizontal flip (h), vertical flip (v), and rotation (r = hv). For n >= 3, Aut(L_n) is isomorphic to the Klein four-group.

			For n = 3, the a(3) = 6 nonequivalent spanning trees are:
+   +   +---+   +---+   +   +   +   +   +---+
|   |   |       |       |   |   |   |   |
+---+   +---+   +---+   +---+   +   +   +   +
    |   |           |   |   |   |   |   |   |
+---+   +---+   +---+   +   +   +---+   +---+

Mithra Karamchedu, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Ladder Graph.
Index entries for linear recurrences with constant coefficients, signature (6,-6,-18,38,-18,-6,6,-1).

Cf. A001353, A001835, A048788.

a[n_] := If[n == 1 || n == 2, 1, FullSimplify[n/4 + ((2 + Sqrt[3])^n - (2 -Sqrt[3])^n)/(8*Sqrt[3]) + If [OddQ[n], ((2 + Sqrt[3])^(n/2) + (2 - Sqrt[3])^(n/2))/(2*Sqrt[6]), ((2 + Sqrt[3])^(n/2) - (2 - Sqrt[3])^(n/2))/(4*Sqrt[3])]]]

a(1) = 1, a(2) = 1, for n >= 3:
a(n) = A001353(n)/4 + A048788(n)/2 + n/4, for n odd, and
a(n) = A001353(n)/4 + A001353(n/2)/2 + n/4, for n even.
For n >= 3, a closed form is:
a(n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/(8*sqrt(3)) + ((2 + sqrt(3))^(n/2) + (2 - sqrt(3))^(n/2))/(2*sqrt(6)) + n/4, for n odd, and
a(n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/(8*sqrt(3)) + ((2 + sqrt(3))^(n/2) - (2 - sqrt(3))^(n/2))/(4*sqrt(3)) + n/4, for n even.
a(n) = 6*a(n-1) - 6*a(n-2) - 18*a(n-3) + 38*a(n-4) - 18*a(n-5) - 6*a(n-6) + 6*a(n-7) - a(n-8) for n > 10. - Peter Kagey, Jul 08 2023
G.f.: x*(1 - 5*x + 6*x^2 + 5*x^3 - 27*x^4 + 40*x^5 - 18*x^6 - 6*x^7 + 6*x^8 - x^9)/((1 - x)^2*(1 - 4*x + x^2)*(1 - 4*x^2 + x^4)). - Stefano Spezia, Jul 09 2023

cp's OEIS Frontend

User: Mithra Karamchedu

A372224 The size of the smallest critical set of hints needed to uniquely solve a generalized n X n Sudoku board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A367055 Triangle read by rows: T(n, k) = A000120(n) + A000120(k), 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A365618 Table read by antidiagonals: T(n, k) = A000120(n) + A000120(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A363165 The number of spanning trees of the ladder graph L_n up to automorphisms of L_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula