login
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.
15

%I #95 Apr 04 2024 10:45:47

%S 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,

%T 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,

%U 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

%N 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.

%C a(p) = p-3 for any odd prime p. a(2n) = a(3n) = 0.

%C a(n) > 0 if and only if n is coprime to 6. - _Chai Wah Wu_, Aug 26 2016

%C Multiplicative by the Chinese remainder theorem. - _Andrew Howroyd_, Aug 07 2018

%C From _Eduard I. Vatutin_, Nov 03 2020: (Start)

%C 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

%C 7 1 0 3 6 5 12 2 8 9 10 11 4

%C 2 3 4 10 0 7 6 9 12 11 5 8 1

%C 4 11 1 7 8 9 10 3 6 0 12 2 5

%C 6 5 8 11 10 4 7 0 1 2 3 9 12

%C 8 9 2 5 12 11 1 4 3 10 0 6 7

%C 3 6 12 0 1 2 8 11 5 4 7 10 9

%C 10 0 3 2 9 12 5 6 7 8 1 4 11

%C 1 7 10 4 3 6 9 8 2 5 11 12 0

%C 11 4 5 6 7 0 3 10 9 12 2 1 8

%C 5 8 7 1 4 10 11 12 0 6 9 3 2

%C 12 2 9 8 11 1 0 7 10 3 4 5 6

%C 9 10 11 12 5 8 2 1 4 7 6 0 3

%C 0 12 6 9 2 3 4 5 11 1 8 7 10

%C that is pandiagonal but not cyclic (Dabbaghian and Wu). (End)

%C Schemmel's totient function of order 3 (Schemmel, 1869; Sándor and Crstici, 2004). - _Amiram Eldar_, Nov 22 2020

%C 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

%C 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

%D József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, chapter 3, p. 276.

%H Charles R Greathouse IV, <a href="/A123565/b123565.txt">Table of n, a(n) for n = 1..10000</a>

%H Vahid Dabbaghian and Tiankuang Wu, <a href="http://dx.doi.org/10.1016/j.jda.2014.12.001">Constructing non-cyclic pandiagonal Latin squares of prime orders</a>, Journal of Discrete Algorithms, Vol. 30 (2015), pp. 70-77.

%H Colin Defant, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Defant/defant5.html">On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions</a>, J. Int. Seq., Vol. 18 (2015), Article # 15.2.1.

%H A. Hedayat, <a href="https://doi.org/10.1016/0097-3165(77)90007-3">A complete solution to the existence and nonexistence of Knut Vik designs and orthogonal Knut Vik designs</a>, J. Comb. Theory, Ser. A 22(3) (1977) 331-337.

%H Victor Schemmel, <a href="https://doi.org/10.1515/crll.1869.70.191">Ueber relative Primzahlen</a>, Journal für die reine und angewandte Mathematik, Vol. 70 (1869), pp. 191-192.

%H Eduard I. Vatutin, <a href="http://evatutin.narod.ru/evatutin_ls_euler_func.pdf">Enumerating cyclic Latin squares and Euler totient function calculating using them</a>, High-performance computing systems and technologies, 2020, Vol. 4, No. 2, pp. 40-48. (in Russian)

%H Eduard I. Vatutin, <a href="https://vk.com/wall162891802_2538">Arranging of N queens on toroidal board and generating pandiagonal Latin squares using them</a> (in Russian).

%H <a href="/index/La#Latin">Index entries for sequences related to Latin squares and rectangles</a>.

%F Multiplicative with a(2^e) = 0 and a(p^e) = (p-3)*p^(e-1) for odd primes p. - _Amiram Eldar_, Nov 22 2020

%F a(2*n+1) = A338562(n) / (2*n+1)!. - _Eduard I. Vatutin_, Apr 02 2021

%F 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

%F a(n) = A370672((n-1)/2) / n. - _Eduard I. Vatutin_, Mar 13 2024

%e 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.

%e Example of a cyclic diagonal Latin square of order 5:

%e 0 1 2 3 4

%e 2 3 4 0 1

%e 4 0 1 2 3

%e 1 2 3 4 0

%e 3 4 0 1 2

%e Example of a cyclic diagonal Latin square of order 7:

%e 0 1 2 3 4 5 6

%e 2 3 4 5 6 0 1

%e 4 5 6 0 1 2 3

%e 6 0 1 2 3 4 5

%e 1 2 3 4 5 6 0

%e 3 4 5 6 0 1 2

%e 5 6 0 1 2 3 4

%e From _Eduard I. Vatutin_, Mar 13 2024: (Start)

%e 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:

%e .

%e +-----------+ +-----------+

%e | Q . . . . | | Q . . . . |

%e | . . Q . . | | . . . Q . |

%e | . . . . Q | | . Q . . . |

%e | . Q . . . | | . . . . Q |

%e | . . . Q . | | . . Q . . |

%e +-----------+ +-----------+

%e .

%e 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:

%e .

%e +---------------+ +---------------+ +---------------+ +---------------+

%e | Q . . . . . . | | Q . . . . . . | | Q . . . . . . | | Q . . . . . . |

%e | . . Q . . . . | | . . . Q . . . | | . . . . Q . . | | . . . . . Q . |

%e | . . . . Q . . | | . . . . . . Q | | . Q . . . . . | | . . . Q . . . |

%e | . . . . . . Q | | . . Q . . . . | | . . . . . Q . | | . Q . . . . . |

%e | . Q . . . . . | | . . . . . Q . | | . . Q . . . . | | . . . . . . Q |

%e | . . . Q . . . | | . Q . . . . . | | . . . . . . Q | | . . . . Q . . |

%e | . . . . . Q . | | . . . . Q . . | | . . . Q . . . | | . . Q . . . . |

%e +---------------+ +---------------+ +---------------+ +---------------+

%e (End)

%p f:= proc(n) local V,R;

%p V:= map(igcd,[$1..n],n);

%p R:= V[1..n-2] + V[2..n-1] + V[3..n];

%p numboccur(3,R);

%p end proc:

%p f(1):= 1:

%p map(f, [$1..100]); # _Robert Israel_, Mar 15 2024

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

%t Join[{1},Table[Count[Boole[Partition[CoprimeQ[Range[n],n],3,1]],{1,1,1}],{n,2,100}]] (* _Harvey P. Dale_, Apr 09 2017 *)

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

%o (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

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

%K nonn,mult,look

%O 1,5

%A _Leroy Quet_, Nov 12 2006

%E Extended by _Ray Chandler_, Nov 19 2006