A123565 a(n) is the number of positive integers k which are <= n and where k, k-1 and k+1 are each coprime to n.

1, 0, 0, 0, 2, 0, 4, 0, 0, 0, 8, 0, 10, 0, 0, 0, 14, 0, 16, 0, 0, 0, 20, 0, 10, 0, 0, 0, 26, 0, 28, 0, 0, 0, 8, 0, 34, 0, 0, 0, 38, 0, 40, 0, 0, 0, 44, 0, 28, 0, 0, 0, 50, 0, 16, 0, 0, 0, 56, 0, 58, 0, 0, 0, 20, 0, 64, 0, 0, 0, 68, 0, 70, 0, 0, 0, 32, 0, 76, 0, 0, 0, 80, 0, 28, 0, 0, 0, 86, 0, 40, 0, 0

Offset: 1

Author

Leroy Quet, Nov 12 2006

Keywords

• nonn
• mult
• look

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

Examples

			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)
		

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).
• Index entries for sequences related to Latin squares and rectangles.

Crossrefs

Cf. A000010, A007705, A051906, A058026, A206256, A241663, A328873, A370672.

Programs

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

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

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

Extensions

Extended by Ray Chandler, Nov 19 2006