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

Author

Torlach Rush, Feb 25 2020

Keywords

• nonn
• look

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

Examples

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

Links

• David Broadhurst, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A060594, A343292.

Programs

Mathematica

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

PARI

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

PARI

a(n)=sum(i=2,n-2,gcd(i,n)==1&&(1/i)%n>i); \\ David Broadhurst, Feb 20 2025

PARI

a(n)=eulerphi(n)/2-2^(#znstar(n)[3]-1); \\ David Broadhurst, Feb 21 2025

Formula

a(n) = (A000010(n) - A060594(n))/2 = n - A343292(n). - Ridouane Oudra, May 04 2025