A329152 a(n) = Sum_{i=1..n-1} Sum_{j=1..i-1} [1 == i*j (mod n)], where [] is the Iverson bracket.

0, 0, 0, 0, 1, 0, 2, 0, 2, 1, 4, 0, 5, 2, 2, 2, 7, 2, 8, 2, 4, 4, 10, 0, 9, 5, 8, 4, 13, 2, 14, 6, 8, 7, 10, 4, 17, 8, 10, 4, 19, 4, 20, 8, 10, 10, 22, 4, 20, 9, 14, 10, 25, 8, 18, 8, 16, 13, 28, 4, 29, 14, 16, 14, 22, 8, 32, 14, 20, 10, 34, 8, 35, 17, 18, 16, 28, 10, 38, 12

Offset

1,7

Comments

In other words, a(n) is the number of choices for k, 1 <= k <= n, so that k*n + 1 has the form a*b for 1 < a < b < n.

Solutions exist only when 1 <= k <= n - 3.

Any odd number greater than 3 has at least one solution, 2*ceiling(n/2).

Observations:

- Unique values of a(n) exist, 6 = a(32), 24 = a(240), 126 = a(512), 144 = a(1320), ..., and n mod 8 = 0.

- If a(n) is an odd prime then a(n) = a(2*n) OR a(n) = a(n/2). For example, 1013 = a(2029) = a(2197) = a(4058) = a(4394).

Links

Table of n, a(n) for n=1..80.

Example

a(1)=0 because there is no solution to k*1 + 1 = a*b, 1 < a < b < n, 1 <= k < n.
a(5)=1 because 1 == 3*2 (mod 5).
a(7)=2 because 1 == 4*2 == 5*3 (mod 7).
a(11)=4 because 1 == 4*3 == 6*2 == 8*7 == 9*5 (mod 11).
a(13)=5 because 1 == 7*2 == 8*5 == 9*3 == 10*4 = 11*6 (mod 13).
a(32)=6 because 1 == 11*3 == 13*5 == 23*7 == 25*9 == 27*19 == 29*21 (mod 32).

Mathematica

Array[Sum[Sum[Boole[Mod[i j, #] == 1], {j, i - 1}], {i, # - 1}] &, 80] (* Michael De Vlieger, Mar 15 2020 *)

Prog

(PARI) a(n) = {my(x=0); for (i = 1, n - 1, for (ii = 1, i - 1, if(1 == ((ii*i) % n), x++))); return(x)}
for (n = 1, 100, print1(a(n), ", "))

Crossrefs

Sequence in context: A305804 A053470 A308202 * A368581 A337563 A278648

Adjacent sequences: A329149 A329150 A329151 * A329153 A329154 A329155

Keyword

nonn

Author

Torlach Rush, Feb 25 2020

Status

approved