cp's OEIS Frontend

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

%I A329152 #83 May 04 2025 12:49:17
%S A329152 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,
%T A329152 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,
%U A329152 4,29,14,16,14,22,8,32,14,20,10,34,8,35,17,18,16,28,10,38,12
%N A329152 a(n) = Sum_{i=1..n-1} Sum_{j=1..i-1} [1 == i*j (mod n)], where [] is the Iverson bracket.
%C A329152 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.
%C A329152 Solutions exist only when 1 <= k <= n - 3.
%C A329152 Any odd number greater than 3 has at least one solution, 2*ceiling(n/2).
%C A329152 Observations:
%C A329152 - Unique values of a(n) exist, 6 = a(32), 24 = a(240), 126 = a(512), 144 = a(1320), ..., and n mod 8 = 0.
%C A329152 - 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).
%H A329152 David Broadhurst, <a href="/A329152/b329152.txt">Table of n, a(n) for n = 1..10000</a>
%F A329152 a(n) = (A000010(n) - A060594(n))/2 = n - A343292(n). - _Ridouane Oudra_, May 04 2025
%e A329152 a(1)=0 because there is no solution to k*1 + 1 = a*b, 1 < a < b < n, 1 <= k < n.
%e A329152 a(5)=1 because 1 == 3*2 (mod 5).
%e A329152 a(7)=2 because 1 == 4*2 == 5*3 (mod 7).
%e A329152 a(11)=4 because 1 == 4*3 == 6*2 == 8*7 == 9*5 (mod 11).
%e A329152 a(13)=5 because 1 == 7*2 == 8*5 == 9*3 == 10*4 = 11*6 (mod 13).
%e A329152 a(32)=6 because 1 == 11*3 == 13*5 == 23*7 == 25*9 == 27*19 == 29*21 (mod 32).
%t A329152 Array[Sum[Sum[Boole[Mod[i j, #] == 1], {j, i - 1}], {i, # - 1}] &, 80] (* _Michael De Vlieger_, Mar 15 2020 *)
%o A329152 (PARI) a(n) = {my(x=0); for (i = 1, n - 1, for (ii = 1, i - 1, if(1 == ((ii*i) % n), x++))); return(x)}
%o A329152 (PARI) a(n)=sum(i=2,n-2,gcd(i,n)==1&&(1/i)%n>i); \\ _David Broadhurst_, Feb 20 2025
%o A329152 (PARI) a(n)=eulerphi(n)/2-2^(#znstar(n)[3]-1); \\ _David Broadhurst_, Feb 21 2025
%Y A329152 Cf. A000010, A060594, A343292.
%K A329152 nonn,look
%O A329152 1,7
%A A329152 _Torlach Rush_, Feb 25 2020