] = la[ - cp's OEIS frontend

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).

A359702 Odd primes p that are not congruent to 2*k modulo prime(k+1) for any positive integer k.

Original entry on oeis.org

3, 7, 31, 37, 43, 61, 67, 73, 157, 211, 271, 277, 331, 367, 421, 457, 571, 691, 823, 883, 997, 1093, 1201, 1237, 1303, 1657, 1783, 2053, 2287, 2347, 2371, 2377, 2557, 2803, 2971, 3001, 3061, 3067, 3307, 3313, 3391, 3967, 4021, 4231, 4273, 4357, 4447, 4561, 4603

Offset: 1

Andrea La Rosa, Jan 11 2023

nonn

This sequence arises from a more general study. First, consider a function f : P -> N (where P is the set of the odd prime numbers) such that 0 <= f(p) < p. Then, remove from the set P each prime number q such that q = f(p) (mod p) for some p.
For example, if f(p) = 0 for each p, then the final set is the empty set.
If f(p) = 1 for each p, then the final set seems to be the set of Fermat primes (empirical observation).
If f(p) = p-1, then the final set seems to be the set of Mersenne primes (empirical observation).
For the particular choice f(p) = 2k (where p is the k-th odd prime) this sequence is obtained.

			Terms in this sequence are those odd primes that are neither congruent to 2 (mod 3), nor congruent to 4 (mod 5), nor congruent to 6 (mod 7), nor congruent to 8 (mod 11), etc.
7 is a term because 7 == 1 (mod 3) and 7 == 2 (mod 5).
11 is not a term because 11 == 2 (mod 3).
13 is not a term because 13 == 6 (mod 7).
17 is not a term because 17 == 2 (mod 3).
19 is not a term because 19 == 8 (mod 11).

Mathematics StackExchange, Can the set of odd primes be finitely sieved by arbitrary congruences of primes?

Cf. A019434, A000668.

isok(p) = {if(!isprime(p)||p==2, 0, my(k=0); forprime(q=3, p-1, k+=2; if(p%q==k, return(0))); 1) } \\ Andrew Howroyd, Jan 11 2023

Terms a(15) and beyond from Andrew Howroyd, Jan 11 2023

A355182 a(n) = t(n) - s(n) where s(n) = n*(n-1)/2 is the sum of the first n nonnegative integers and t(n) is the smallest sum of consecutive integers starting from n such that t(n) > s(n).

Original entry on oeis.org

1, 1, 4, 3, 1, 6, 3, 10, 6, 1, 10, 4, 15, 8, 21, 13, 4, 19, 9, 26, 15, 3, 22, 9, 30, 16, 1, 24, 8, 33, 16, 43, 25, 6, 35, 15, 46, 25, 3, 36, 13, 48, 24, 61, 36, 10, 49, 22, 63, 35, 6, 49, 19, 64, 33, 1, 48, 15, 64, 30, 81, 46, 10, 63, 26, 81, 43, 4, 61, 21, 80, 39, 100, 58, 15, 78, 34, 99

Offset: 1

Andrea La Rosa, Jun 23 2022

nonn

Record high values of a(n)/n approach sqrt(2) and occur at values of n that are terms of A011900; a(A011900(k)) = A046090(k). - Jon E. Schoenfield, Jun 23 2022

It appears that the sequence 1,2,4,5,6,8,... (the largest integer in the t(n) sum) is A288998. - Michel Marcus, Jun 24 2022

			a(6) = -s(6) + t(6):
s(6) is the sum of the first 6 nonnegative integers = 6*5 / 2 = 15.
t(6) is the smallest sum k of consecutive integers starting from n = 6 such that k > s(6) = 15.
The first few sets of consecutive integers starting from 6 are
  {6}, whose elements add up to 6,
  {6, 7}, whose elements add up to 13,
  {6, 7, 8}, whose elements add up to 21,
  {6, 7, 8, 9}, whose elements add up to 30,
  ...
the smallest sum that is > 15 is 21, so t(6) = 21, so a(6) = -15 + 21 = 6.

Cf. A000217, A001477, A093001.

Cf. A288998.

function a(n) {
    var sum = 0;
    for (var i = 0; i < n; i++)
        sum -= i;
    while (sum <= 0)
        sum += i++;
    return sum;
}

a(n) = my(t=0, s=n*(n-1)/2, k=n); until (t > s, t += k; k ++); t-s; \\ Michel Marcus, Jun 24 2022

from math import isqrt
def A355182(n): return ((m:=(isqrt(((k:=n*(n-1))<<3)+1)+1)>>1)*(m+1)>>1)-k # Chai Wah Wu, Jul 14 2022

From Jon E. Schoenfield, Jun 23 2022: (Start)
a(n) = t(n) - s(n) where
   s(n) = n*(n-1)/2,
      j = floor(sqrt(8*n^2 - 8*n + 1)),
      m = ceiling(j/2) - n + 1, and
   t(n) = (m*(m + 2*n - 1))/2. (End)

A316296 a(n) = Sum_{k=1..n} f(k, n), where f(i, j) is the number of multiples of i greater than j and less than 2*j.

Original entry on oeis.org

0, 1, 3, 5, 9, 10, 15, 18, 21, 24, 31, 30, 38, 41, 44, 48, 55, 56, 64, 65, 70, 75, 84, 81, 90, 95, 98, 103, 112, 109, 120, 123, 129, 134, 139, 139, 150, 155, 160, 161, 173, 170, 183, 184, 187, 198, 205, 202, 212, 217, 223, 226, 239, 236, 245, 248, 255, 262, 271, 266, 282, 285, 288

Offset: 1

Andrea La Rosa, Jun 29 2018

f(n, m) is the number of multiples of n that are > m and < 2*m. n and m must be both >= 0.
By definition, this means that f(n, m) =
  0    if n >= 2m;
  1    if m < n < 2m;
If n <= m, then m = kn + q, where 0 <= q < n.
It can be proven that in this case f(n, m) =
  k - 1    if q = 0;
  k        if q > 0 and (n - q) >= q;
  k + 1    if q > 0 and (n - q) < q.
Let sd(n) = A006218; then a(n) = sd(2n-1) - sd(n) - (n - 1).
Also, a(n) = Sum_{k=n+1..2n-1} (d(k) - 1), where d(k) is number of divisors (A000005).
Number of ways the numbers from 1..n divide the numbers from n+1..2n-1, n>=2. - Wesley Ivan Hurt, Feb 08 2022

			For n = 7, a(7) = f(1,7) + f(2,7) + f(3,7) + f(4,7) + f(5,7) + f(6,7) + f(7,7) = 6 + 3 + 2 + 2 + 1 + 1 = 15.

function f(n,m){
    var count = 0;
    for(var i=m+1; i<2*m; i++){
        if(i%n === 0) count++;
    }
    return count;
}
function sf(n){
    var sum = 0;
    for(var i=1; i<=n; i++){
        sum += f(i, n);
    }
    return sum;
}

a(n) = n + sum(m = 1, n, (floor((n<<1 - 1) / m) - ceil((n + 1) / m))) \\ David A. Corneth, Jun 29 2018

from math import isqrt
def A316296(n): return ((s:=isqrt(n))+(t:=isqrt(m:=(n<<1)-1)))*(s-t)+(sum(m//k for k in range(1,t+1))-sum(n//k for k in range(1,s+1))<<1)-n+1 # Chai Wah Wu, Oct 24 2023

a(n) = Sum_{k=1..n} Sum_{i=n+1..2n-1} (1-ceiling(i/k)+floor(i/k)). - Wesley Ivan Hurt, Feb 08 2022

A268080 Difference between total number of Boolean functions of n variables and total number of monotonic Boolean functions of n variables.

Original entry on oeis.org

0, 1, 10, 236, 65368, 4294959715, 18446744073701723262, 340282366920938463463374605017086170458, 115792089237316195423570985008687907853269984665640563983327146779225571732148

Offset: 0

Ross La Haye, Jan 25 2016

nonn

Cf. A001146, A000372.

a(n) = 2^(2^n) - (n-th Dedekind number).

a(n) = A001146(n) - A000372(n).

A266696 a(n) = Sum_{k=3..n} k*StirlingS2(n+1, k+1).

Original entry on oeis.org

3, 34, 260, 1721, 10808, 67376, 427449, 2798432, 19042144, 135083103, 999573770, 7709458472, 61890269371, 516304085366, 4468459583648, 40058286666913, 371420337948828, 3556972620397996, 35138563919933649, 357654826207771292, 3746672499505598556, 40354065576745998303

Offset: 3

Ross La Haye, Jan 02 2016

Let F be a family of nonempty sets on an n-element set A with |F| > 1 such that every pair of distinct elements of F have the same nonempty intersection and there are no two distinct elements of F such that one is a subset of the other. Then a(n) = the total number of such families.
Proof: Let binomial(n,k) denote the binomial coefficient (the number of ways to choose k elements from an n-element set) and StirlingS2(n,k) the Stirling numbers of the second kind (the number of ways to partition an n-element set A into k nonempty parts, the union of which is A). As is well known, StirlingS2(n+1,k+1) = StirlingS2(n,k) + k*StirlingS2(n,k+1), where we assume StirlingS2(0,0) = 1, StirlingS2(n,0) = StirlingS2(0,n) = 0, and StirlingS2(n,k) = 0 when n < k, for n > 0.
Enumerate the elements of F in the following manner. Begin by partitioning the elements of A into either 1) k or 2) k+1 parts. For case 1, there are StirlingS2(n,k) possible partitions. From such a partition, select k-1 of the k parts to assign to the elements of F (where k >= 3). The remaining part constitutes the nonempty intersection. So this enumeration can be accomplished in binomial(k,k-1)*binomial(1,1)*StirlingS2(n,k) = k*StirlingS2(n,k) ways. Here we have that the size of the union of the elements of F equals |A|.
For case 2, there are StirlingS2(n,k+1) partitions. From such a partition, select k-1 of the k+1 parts to assign to the elements of F (where, again, k >= 3). Then select 1 of the 2 remaining parts to constitute the nonempty intersection. So this enumeration can be accomplished in binomial(k+1,k-1)*binomial(2,1)*StirlingS2(n,k+1) = k*(k+1)*StirlingS2(n,k+1) ways. Here we have that the size of the union of the elements of F is less than |A|. So the 2 cases cover both possibilities, i.e., the union of the elements of F is either equal to |A| or less than |A|.
Multiplying the above recurrence by k, we have k*StirlingS2(n+1,k+1) = k*StirlingS2(n,k) + k*(k+1)*StirlingS2(n,k+1), and the claim follows by summing over this for 3 <= k <= n. (Observe that n >= 3 as for n = 1, say [n] = {1}, there is only 1 subset of [n], and for n = 2, say [n] = {1,2}, the subsets of n are {},{1},{2},{1,2}, so that there are no pairs here that have a nonempty intersection and for which neither is a subset of the other. By similar reasoning, k >= 3, as we need at least 2 distinct sets in F, and we need at least 1 element of A not in either of these sets to add to them to create their common nonempty intersection.)
The families F counted here are very close in definition to sunflowers = delta-systems.
The families F counted here could be described perhaps more clearly as intersecting Sperner families such that every pair of distinct elements of F have the same nonempty intersection and |F| > 1.

			Let [n] = {1,2,3}. Then F = {{1,3},{2,3}} or {{1,2},{2,3}} or {{1,2},{1,3}}.

Miklos Bona, Introduction to Enumerative Combinatorics, McGraw-Hill, 2007, pages 363-364.
Peter Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994, pages 100-102.

Ross La Haye, Quasi-Sunflower Sperner Families and Dedekind's Problem, ResearchGate, 2017.
Wikipedia, Sperner family.
Wikipedia, Sunflower.

Cf. A000110, A008277.

seq(add(k*Stirling2(n+1,k+1),k=3..n), n=3..40); # Robert Israel, Jan 03 2016

Table[Sum[k*StirlingS2[n+1,k+1],{k,3,n}],{n,3,14}]

a(n) = sum(k=3, n, k*stirling(n+1, k+1, 2)); \\ Michel Marcus, Jan 03 2016

use ntheory ":all"; sub a266696 { my $n=shift; vecsum(map { vecprod($,stirling($n+1,$+1,2)) } 3..$n); } # Dana Jacobsen, Jan 03 2016

a(n) = Sum_{k=3..n} k * StirlingS2(n+1, k+1).
a(n) = B(n+2) - 2*B(n+1) - 3^n + 2^n, where B(n) is the n-th Bell number. - Ross La Haye, Feb 16 2017
E.g.f.: exp(x-1)*(exp(x) - 1)*(exp(exp(x)) - exp(x+1)). - Stefano Spezia, Jul 06 2021

More terms from Michel Marcus, Jan 03 2016

A224749 Vauban's sequence: a(n)=0 if n<=0, a(1)=1; thereafter a(n) = 3a(n-1) + 6a(n-2) + 6a(n-3) + 6a(n-4) + 6*a(n-5).

Original entry on oeis.org

0, 1, 3, 15, 69, 321, 1491, 6921, 32139, 149229, 692919, 3217437, 14939559, 69369021, 322101927, 1495619397, 6944625855, 32246056989, 149728468167, 695235829509, 3228196110975, 14989518216045, 69600993441975, 323179052074101, 1500620817813327, 6967849012498557, 32353889326768359

Offset: 0

Pierre de la Harpe, Apr 17 2013

In his essay "La Cochonnerie ou calcul estimatif...", French military engineer Vauban (1633-1707) writes about this Fibonacci-like sequence for the year-by-year growth of pigs. - Charles R Greathouse IV, Sep 16 2015

Sébastien Le Prestre de Vauban, La cochonnerie ou calcul estimatif pour connaître jusqu'où peut aller la production d'une truie pendant dix années de temps (1699).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Pierre de la Harpe, Vauban pour les cochons comme Fibonacci pour les lapins, Images des Mathématiques, CNRS, 2013.
Index entries for linear recurrences with constant coefficients, signature (3, 6, 6, 6, 6).

Cf. A000045 (Fibonacci), A000930 (Narayana).

I:=[0,1,3,15,69]; [n le 5 select I[n] else 3*Self(n-1)+6*Self(n-2)+6*Self(n-3)+6*Self(n-4)+6*Self(n-5): n in [1..30]]; // Vincenzo Librandi, Sep 17 2015

f:=proc(n) option remember;
if n <= 0 then 0 elif n=1 then 1 else
3*f(n-1)+6*f(n-2)+6*f(n-3)+6*f(n-4)+6*f(n-5); fi; end;
[seq(f(n),n=0..30)];

LinearRecurrence[{3, 6, 6, 6, 6}, {0, 1, 3, 15, 69}, 40] (* T. D. Noe, Apr 17 2013 *)
CoefficientList[Series[x/(1 - 3 x - 6 x^2 - 6 x^3 - 6 x^4 - 6 x^5), {x, 0, 33}], x] (* Vincenzo Librandi, Sep 17 2015 *)

a(n)=([0,1,0,0,0; 0,0,1,0,0; 0,0,0,1,0; 0,0,0,0,1; 6,6,6,6,3]^n*[0;1;3;15;69])[1,1] \\ Charles R Greathouse IV, Sep 16 2015

G.f.: x/(1-3*x-6*x^2-6*x^3-6*x^4-6*x^5). - Philippe Deléham, Apr 17 2013

A217764 Array defined by a(n,k) = floor((k+2)/2)3^n - floor((k+1)/2)2^n, read by antidiagonals.

Original entry on oeis.org

1, 3, 0, 9, 1, 1, 27, 5, 4, 0, 81, 19, 14, 2, 1, 243, 65, 46, 10, 5, 0, 729, 211, 146, 38, 19, 3, 1, 2187, 665, 454, 130, 65, 15, 6, 0, 6561, 2059, 1394, 422, 211, 57, 24, 4, 1, 19683, 6305, 4246, 1330, 665, 195, 84, 20, 7, 0, 59049, 19171, 12866, 4118, 2059, 633, 276, 76, 29, 5, 1

Offset: 0

Ross La Haye, Mar 23 2013

Columns 0,1,2,3 respectively correspond to relations R_3, R_4, R_0, R_1 defined in La Haye paper listed below.

			a(4,4) = 211 because floor((4+2)/2)*3^4 - floor((4+1)/2)*2^4 = 3*3^4 - 2*2^4 = 243 - 32 = 211.

Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

Cf. a(1,k) = A084964(k+2); a(n,0) = A000244(n); a(n,1) = A001047(n); a(n,2) = A027649(n); a(n,3) = A056182(n); a(n,4) = A001047(n+1); a(n,5) = A210448(n); a(n,6) = A166060(n); a(n,7) = A145563(n); a(n,8) = A102485(n).

a(n,k) = floor((k+2)/2)*3^n - floor((k+1)/2)*2^n. a(n,k) = 5*a(n-1,k) - 6*a(n-2,k); a(0,k) = floor((k+2)/2) - floor((k+1)/2), a(1,k) = floor((k+2)/2)*3 - floor((k+1)/2)*2.

A178784 Let d be the vector of divisors of 100 sorted from largest to smallest, i.e., [100,50,25,20,10,5,4,2,1]. Then a(n) = 100/d(n) - 1.

Original entry on oeis.org

0, 1, 3, 4, 9, 19, 24, 49, 99

Offset: 1

Ross La Haye, Jun 13 2010

Cf. A018283.

Map[(100/# - 1)&, Sort[Divisors[100], Greater]]
Map[(#-1)&,Divisors[100]]  (* Ross La Haye, Jun 17 2010 *)
100/Reverse[Divisors[100]]-1 (* Harvey P. Dale, Jan 14 2015 *)

a(n) = 100/A018283(10-n) - 1.

a(n) = A018283(n) - 1. - Ross La Haye, Jun 17 2010

A158333 Position of number of digits increment in the sequence of powers of 3.

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 133, 135

Offset: 0

Julio Cesar de la Yncera, Mar 16 2009

			For n=1 a(1)=3 since the sequence of powers of 3 is 1, 3, 9, 27, 81, 243, 729 and numbers of digits increase at position 1,3,5,...

A123384

A158333 := proc(n)
        1+floor(n/log10(3)) ;
end proc:
seq(A158333(n),n=0..20) ; # R. J. Mathar, Sep 01 2014

a[x_] := 1 + Floor[x/Log[10, 3]]; Table[a[i], {i, 0, 20}]

a(n)=1+Floor(n/Log_10(3)) = 1+A054965(n).

Indices in offset, example, and formula adjusted by R. J. Mathar, May 21 2009

More terms from Robert G. Wilson v, May 29 2009

cp's OEIS Frontend

User: ] = la[

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

A359702 Odd primes p that are not congruent to 2*k modulo prime(k+1) for any positive integer k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A355182 a(n) = t(n) - s(n) where s(n) = n*(n-1)/2 is the sum of the first n nonnegative integers and t(n) is the smallest sum of consecutive integers starting from n such that t(n) > s(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

JavaScript

PARI

Python

Formula

A316296 a(n) = Sum_{k=1..n} f(k, n), where f(i, j) is the number of multiples of i greater than j and less than 2*j.

Views

Author

Keywords

Comments

Examples

Programs

JavaScript

PARI

Python

Formula

A268080 Difference between total number of Boolean functions of n variables and total number of monotonic Boolean functions of n variables.

Views

Author

Keywords

Crossrefs

Formula

A266696 a(n) = Sum_{k=3..n} k*StirlingS2(n+1, k+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Perl

Formula

Extensions

A224749 Vauban's sequence: a(n)=0 if n<=0, a(1)=1; thereafter a(n) = 3*a(n-1) + 6*a(n-2) + 6*a(n-3) + 6*a(n-4) + 6*a(n-5).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

A224749 Vauban's sequence: a(n)=0 if n<=0, a(1)=1; thereafter a(n) = 3a(n-1) + 6a(n-2) + 6a(n-3) + 6a(n-4) + 6*a(n-5).

A217764 Array defined by a(n,k) = floor((k+2)/2)3^n - floor((k+1)/2)2^n, read by antidiagonals.