login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 10
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 (list; graph; refs; listen; history; text; internal format)
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

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.

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)

Index entries for sequences related to Latin squares and rectangles

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

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

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

Cf. A000010, A058026, A241663, A328873.

Sequence in context: A087263 A099894 A048298 * A258701 A246160 A081120

Adjacent sequences:  A123562 A123563 A123564 * A123566 A123567 A123568

KEYWORD

nonn,mult

AUTHOR

Leroy Quet, Nov 12 2006

EXTENSIONS

Extended by Ray Chandler, Nov 19 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 1 14:10 EST 2021. Contains 349430 sequences. (Running on oeis4.)