OFFSET
1,5
COMMENTS
a(p) = p-3 for any odd prime p. a(2n) = a(3n) = 0.
a(n) > 0 if and only if n is coprime to 6. - Chai Wah Wu, Aug 26 2016
Multiplicative by the Chinese remainder theorem. - Andrew Howroyd, Aug 07 2018
From Eduard I. Vatutin, Nov 03 2020: (Start)
a(n) is the number of cyclic diagonal Latin squares of order n with the first row in order. Every cyclic diagonal Latin square is a cyclic Latin square, so a(n) <= A000010(n). Every cyclic diagonal Latin square is pandiagonal, but the converse is not true. For example, for order n=13 there is a square
7 1 0 3 6 5 12 2 8 9 10 11 4
2 3 4 10 0 7 6 9 12 11 5 8 1
4 11 1 7 8 9 10 3 6 0 12 2 5
6 5 8 11 10 4 7 0 1 2 3 9 12
8 9 2 5 12 11 1 4 3 10 0 6 7
3 6 12 0 1 2 8 11 5 4 7 10 9
10 0 3 2 9 12 5 6 7 8 1 4 11
1 7 10 4 3 6 9 8 2 5 11 12 0
11 4 5 6 7 0 3 10 9 12 2 1 8
5 8 7 1 4 10 11 12 0 6 9 3 2
12 2 9 8 11 1 0 7 10 3 4 5 6
9 10 11 12 5 8 2 1 4 7 6 0 3
0 12 6 9 2 3 4 5 11 1 8 7 10
that is pandiagonal but not cyclic (Dabbaghian and Wu). (End)
Schemmel's totient function of order 3 (Schemmel, 1869; Sándor and Crstici, 2004). - Amiram Eldar, Nov 22 2020
a(p) is a lower bound for cardinality of clique of MODLS for all odd prime orders p: a(p) <= A328873(p). - Eduard I. Vatutin, Apr 02 2021
Also number of solutions for n-queens problem on toroidal chessboard (see A051906, A007705 or A370672), given by knight with (dx,dy) movement parameters starting from top left corner (more generally: from one cell fixed for all solutions). - Eduard I. Vatutin, Mar 13 2024
REFERENCES
József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, chapter 3, p. 276.
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Vahid Dabbaghian and Tiankuang Wu, Constructing non-cyclic pandiagonal Latin squares of prime orders, Journal of Discrete Algorithms, Vol. 30 (2015), pp. 70-77.
Colin Defant, On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions, J. Int. Seq., Vol. 18 (2015), Article # 15.2.1.
A. Hedayat, A complete solution to the existence and nonexistence of Knut Vik designs and orthogonal Knut Vik designs, J. Comb. Theory, Ser. A 22(3) (1977) 331-337.
Victor Schemmel, Ueber relative Primzahlen, Journal für die reine und angewandte Mathematik, Vol. 70 (1869), pp. 191-192.
Eduard I. Vatutin, Enumerating cyclic Latin squares and Euler totient function calculating using them, High-performance computing systems and technologies, 2020, Vol. 4, No. 2, pp. 40-48. (in Russian)
Eduard I. Vatutin, Arranging of N queens on toroidal board and generating pandiagonal Latin squares using them (in Russian).
FORMULA
Multiplicative with a(2^e) = 0 and a(p^e) = (p-3)*p^(e-1) for odd primes p. - Amiram Eldar, Nov 22 2020
a(2*n+1) = A338562(n) / (2*n+1)!. - Eduard I. Vatutin, Apr 02 2021
Sum_{k=1..n} a(k) ~ c * n^2, where c = Product_{p prime} (1 - 3/p^2) = 0.125486... (A206256). - Amiram Eldar, Nov 18 2022
a(n) = A370672((n-1)/2) / n. - Eduard I. Vatutin, Mar 13 2024
EXAMPLE
The positive integers which are both coprime to 25 and are <= 25 are 1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24. Of these integers there are 10 integers k where (k-1) and (k+1) are also coprime to 25. These integers k are 2,3,7,8,12,13,17,18,22,23. So a(25) = 10.
Example of a cyclic diagonal Latin square of order 5:
0 1 2 3 4
2 3 4 0 1
4 0 1 2 3
1 2 3 4 0
3 4 0 1 2
Example of a cyclic diagonal Latin square of order 7:
0 1 2 3 4 5 6
2 3 4 5 6 0 1
4 5 6 0 1 2 3
6 0 1 2 3 4 5
1 2 3 4 5 6 0
3 4 5 6 0 1 2
5 6 0 1 2 3 4
From Eduard I. Vatutin, Mar 13 2024: (Start)
Example of a(5)=2 solutions for n-queens problem on toroidal chessboard, given by knight with (+1,+2) and (+1,+3) movement parameters starting from top left corner:
.
+-----------+ +-----------+
| Q . . . . | | Q . . . . |
| . . Q . . | | . . . Q . |
| . . . . Q | | . Q . . . |
| . Q . . . | | . . . . Q |
| . . . Q . | | . . Q . . |
+-----------+ +-----------+
.
Example of a(7)=4 solutions for n-queens problem on toroidal chessboard, given by knight with (+1,+2), (+1,+3), (+1,+4), (+1,+5) movement parameters starting from top left corner:
.
+---------------+ +---------------+ +---------------+ +---------------+
| Q . . . . . . | | Q . . . . . . | | Q . . . . . . | | Q . . . . . . |
| . . Q . . . . | | . . . Q . . . | | . . . . Q . . | | . . . . . Q . |
| . . . . Q . . | | . . . . . . Q | | . Q . . . . . | | . . . Q . . . |
| . . . . . . Q | | . . Q . . . . | | . . . . . Q . | | . Q . . . . . |
| . Q . . . . . | | . . . . . Q . | | . . Q . . . . | | . . . . . . Q |
| . . . Q . . . | | . Q . . . . . | | . . . . . . Q | | . . . . Q . . |
| . . . . . Q . | | . . . . Q . . | | . . . Q . . . | | . . Q . . . . |
+---------------+ +---------------+ +---------------+ +---------------+
(End)
MAPLE
f:= proc(n) local V, R;
V:= map(igcd, [$1..n], n);
R:= V[1..n-2] + V[2..n-1] + V[3..n];
numboccur(3, R);
end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Mar 15 2024
MATHEMATICA
f[n_] := Length[Select[Range[n], GCD[ #, n] == 1 && GCD[ # - 1, n] == 1 && GCD[ # + 1, n] == 1 &]]; Table[f[n], {n, 100}] (* Ray Chandler, Nov 19 2006 *)
Join[{1}, Table[Count[Boole[Partition[CoprimeQ[Range[n], n], 3, 1]], {1, 1, 1}], {n, 2, 100}]] (* Harvey P. Dale, Apr 09 2017 *)
f[2, e_] := 0; f[p_, e_] := (p - 3)*p^(e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 22 2020 *)
PROG
(PARI) a(n)=if(gcd(n, 6)>1, return(0)); sum(k=1, n, gcd(k^3-k, n)==1) \\ Charles R Greathouse IV, Aug 26 2016
CROSSREFS
KEYWORD
AUTHOR
Leroy Quet, Nov 12 2006
EXTENSIONS
Extended by Ray Chandler, Nov 19 2006
STATUS
approved