cp's OEIS Frontend

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.

%I A123565 #95 Apr 04 2024 10:45:47
%S A123565 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 A123565 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 A123565 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 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.
%C A123565 a(p) = p-3 for any odd prime p. a(2n) = a(3n) = 0.
%C A123565 a(n) > 0 if and only if n is coprime to 6. - _Chai Wah Wu_, Aug 26 2016
%C A123565 Multiplicative by the Chinese remainder theorem. - _Andrew Howroyd_, Aug 07 2018
%C A123565 From _Eduard I. Vatutin_, Nov 03 2020: (Start)
%C A123565 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 A123565    7  1  0  3  6  5 12  2  8  9 10 11  4
%C A123565    2  3  4 10  0  7  6  9 12 11  5  8  1
%C A123565    4 11  1  7  8  9 10  3  6  0 12  2  5
%C A123565    6  5  8 11 10  4  7  0  1  2  3  9 12
%C A123565    8  9  2  5 12 11  1  4  3 10  0  6  7
%C A123565    3  6 12  0  1  2  8 11  5  4  7 10  9
%C A123565   10  0  3  2  9 12  5  6  7  8  1  4 11
%C A123565    1  7 10  4  3  6  9  8  2  5 11 12  0
%C A123565   11  4  5  6  7  0  3 10  9 12  2  1  8
%C A123565    5  8  7  1  4 10 11 12  0  6  9  3  2
%C A123565   12  2  9  8 11  1  0  7 10  3  4  5  6
%C A123565    9 10 11 12  5  8  2  1  4  7  6  0  3
%C A123565    0 12  6  9  2  3  4  5 11  1  8  7 10
%C A123565 that is pandiagonal but not cyclic (Dabbaghian and Wu). (End)
%C A123565 Schemmel's totient function of order 3 (Schemmel, 1869; Sándor and Crstici, 2004). - _Amiram Eldar_, Nov 22 2020
%C A123565 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 A123565 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 A123565 József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, chapter 3, p. 276.
%H A123565 Charles R Greathouse IV, <a href="/A123565/b123565.txt">Table of n, a(n) for n = 1..10000</a>
%H A123565 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 A123565 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 A123565 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 A123565 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 A123565 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 A123565 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 A123565 <a href="/index/La#Latin">Index entries for sequences related to Latin squares and rectangles</a>.
%F A123565 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 A123565 a(2*n+1) = A338562(n) / (2*n+1)!. - _Eduard I. Vatutin_, Apr 02 2021
%F A123565 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 A123565 a(n) = A370672((n-1)/2) / n. - _Eduard I. Vatutin_, Mar 13 2024
%e A123565 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 A123565 Example of a cyclic diagonal Latin square of order 5:
%e A123565   0 1 2 3 4
%e A123565   2 3 4 0 1
%e A123565   4 0 1 2 3
%e A123565   1 2 3 4 0
%e A123565   3 4 0 1 2
%e A123565 Example of a cyclic diagonal Latin square of order 7:
%e A123565   0 1 2 3 4 5 6
%e A123565   2 3 4 5 6 0 1
%e A123565   4 5 6 0 1 2 3
%e A123565   6 0 1 2 3 4 5
%e A123565   1 2 3 4 5 6 0
%e A123565   3 4 5 6 0 1 2
%e A123565   5 6 0 1 2 3 4
%e A123565 From _Eduard I. Vatutin_, Mar 13 2024: (Start)
%e A123565 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 A123565 .
%e A123565 +-----------+ +-----------+
%e A123565 | Q . . . . | | Q . . . . |
%e A123565 | . . Q . . | | . . . Q . |
%e A123565 | . . . . Q | | . Q . . . |
%e A123565 | . Q . . . | | . . . . Q |
%e A123565 | . . . Q . | | . . Q . . |
%e A123565 +-----------+ +-----------+
%e A123565 .
%e A123565 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 A123565 .
%e A123565 +---------------+ +---------------+ +---------------+ +---------------+
%e A123565 | Q . . . . . . | | Q . . . . . . | | Q . . . . . . | | Q . . . . . . |
%e A123565 | . . Q . . . . | | . . . Q . . . | | . . . . Q . . | | . . . . . Q . |
%e A123565 | . . . . Q . . | | . . . . . . Q | | . Q . . . . . | | . . . Q . . . |
%e A123565 | . . . . . . Q | | . . Q . . . . | | . . . . . Q . | | . Q . . . . . |
%e A123565 | . Q . . . . . | | . . . . . Q . | | . . Q . . . . | | . . . . . . Q |
%e A123565 | . . . Q . . . | | . Q . . . . . | | . . . . . . Q | | . . . . Q . . |
%e A123565 | . . . . . Q . | | . . . . Q . . | | . . . Q . . . | | . . Q . . . . |
%e A123565 +---------------+ +---------------+ +---------------+ +---------------+
%e A123565 (End)
%p A123565 f:= proc(n) local V,R;
%p A123565   V:= map(igcd,[$1..n],n);
%p A123565   R:= V[1..n-2] + V[2..n-1] + V[3..n];
%p A123565   numboccur(3,R);
%p A123565 end proc:
%p A123565 f(1):= 1:
%p A123565 map(f, [$1..100]); # _Robert Israel_, Mar 15 2024
%t A123565 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 A123565 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 A123565 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 A123565 (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 A123565 Cf. A000010, A007705, A051906, A058026, A206256, A241663, A328873, A370672.
%K A123565 nonn,mult,look
%O A123565 1,5
%A A123565 _Leroy Quet_, Nov 12 2006
%E A123565 Extended by _Ray Chandler_, Nov 19 2006