Suppose that s = (s(n)) and t = (t(n)) are sequences of numbers and h > 0 and k > 0. The lower (h, k)-midsequence of s and t is floor(h*s + k*t); the upper (h, k)-midsequence of s and t is ceiling(h*s + k*t). See A398651 for a guide to related sequences.
Suppose that s = (s(n)) and t = (t(n)) are sequences of numbers and h > 0 and k > 0. The lower (h, k)-midsequence of s and t is floor(h*s + k*t); the upper (h, k)-midsequence of s and t is ceiling(h*s + k*t). See A398651 for a guide to related sequences.
Suppose that s = (s(n)) and t = (t(n)) are sequences of numbers and h > 0 and k > 0. The lower (h, k)-midsequence of s and t is floor(h*s + k*t); the upper (h, k)-midsequence of s and t is ceiling(h*s + k*t). See A398651 for a guide to related sequences.
Suppose that s = (s(n)) and t = (t(n)) are sequences of numbers and h > 0 and k > 0. The lower (h, k)-midsequence of s and t is floor(h*s + k*t); the upper (h, k)-midsequence of s and t is ceiling(h*s + k*t).
A Latin square of order n on the symbols 0..n-1 is idempotent if the cell in row i, column i contains i for every i.
Applying a single permutation simultaneously to rows, columns and symbols carries idempotent squares to idempotent squares. This is quasigroup isomorphism, and a(n) counts the resulting equivalence classes.
Isotopy, which applies three independent permutations, does not preserve the main diagonal, so isomorphism rather than isotopy is the appropriate equivalence for idempotent squares.
a(7) was computed by exhaustive classification using canonical forms, then checked by the orbit-stabilizer identity: summing n!/|Aut| over the 10213 classes returns exactly A395689(7) = 49390080.
a(8) was computed from A395689(8) by Burnside's lemma, the number of classes being the average over all permutations of the number of squares each one fixes. Only highly symmetric squares are fixed by a non-identity permutation, so those fixed-point counts are small exhaustive searches.
Number of idempotent Latin squares of order n up to simultaneous row, column and symbol permutation combined with the six conjugate (parastrophe) operations.
A Latin square of order n on the symbols 0..n-1 is idempotent if the cell in row i, column i contains i for every i.
Regard such a square as its set of n^2 triples (r, c, L(r,c)). The six permutations of the three coordinates give the six conjugates, or parastrophes, of L.
Every conjugate of an idempotent Latin square is again idempotent, because the diagonal triples (i,i,i) are unchanged by any permutation of the coordinates.
Conjugation commutes with relabeling rows, columns and symbols by a single permutation, so the two together give an action of S_n X S_3, and a(n) is the number of orbits.
a(n) = (1/(6*n!)) * Sum_{g in S_n X S_3} F(g), where F(g) is the number of idempotent Latin squares of order n fixed by g; F(identity) = A395689(n).
EXAMPLE
a(5) = 2: the four isomorphism classes of order 5 merge under conjugation into two orbits, one containing three of the classes and one containing the fourth.
For n = 3, there are 6 permutations in total. Among them, a(3) = 2 permutations require the minimum number of comparisons, namely 2, when sorted using binary search: <2,3,1> and <3,2,1>. The remaining permutations, <1,2,3>, <1,3,2>, <2,1,3>, and <3,1,2>, require 3 comparisons. This is the row n = 3 of the triangle in A395685.
g(k)^4 < k holds if and only if k has no divisor d with k^(1/4) <= d <= k^(3/4), if and only if A006530(k)^4 > k^3, i.e., the largest prime factor of k exceeds k^(3/4). Proof: if p = A006530(k) > k^(3/4), every divisor of k is either a multiple of p (hence > k^(3/4)) or a divisor of k/p < k^(1/4). Conversely, if p <= k^(3/4) and p >= k^(1/4), then p itself lies in the excluded range; if all prime factors of k are < k^(1/4), multiplying them one at a time yields a divisor in [k^(1/4), k^(1/2)).
a(n) = A000720(n) for 1 <= n <= 15, since every composite k has a divisor in [2, sqrt(k)], so g(k) >= 2 and g(k)^4 >= 16 > k.
This is the m = 4 member of a family: for each integer m >= 3, the condition g(k)^m < k is equivalent to A006530(k)^m > k^(m-1), giving Sum_{c=2..floor(n^(1/m))} (A000720(floor(n/c)) - A000720(c^(m-1))) = a_m(n) - A000720(n). The case m = 3 is A396205. The equivalence fails for m = 2 (e.g., k = 12).
Limiting density: a(n)/n tends to log(4/3) = 0.28768... (follows from the formula together with the Prime Number Theorem).
For n >= 1, A000720(n) = a(n) - Sum_{c=2..floor(n^(1/4))} ( A000720(floor(n/c)) - A000720(c^3) ).
a(n) ~ n * log(4/3).
EXAMPLE
g(10) = 2 and 2^4 = 16 is not less than 10, so the indicator at k = 10 is 0; hence a(10) = a(9) = 4. (Note A006530(10) = 5 < 10^(3/4), so 10 is counted in A396205 but not here.)
g(22) = 2 and 2^4 = 16 < 22, so the indicator at k = 22 is 1; hence a(22) = 9.
