|
| |
|
|
A320159
|
|
Number of positive integers x < prime(n)/2 such that (x^2 mod prime(n)) > (4*x^2 mod prime(n)).
|
|
1
|
|
|
|
0, 0, 1, 2, 2, 3, 4, 5, 4, 7, 9, 9, 10, 11, 9, 13, 13, 15, 17, 14, 18, 22, 19, 22, 24, 25, 28, 25, 27, 28, 34, 30, 34, 36, 37, 41, 39, 41, 36, 43, 42, 45, 41, 48, 49, 54, 54, 59, 54, 57, 58, 52, 60, 59, 64, 59, 67, 73, 69, 70, 72, 73, 78, 68, 78, 79, 84, 84, 84, 87, 88, 80, 96, 93, 96, 87, 97, 99, 100, 102
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Conjecture: Let p > 3 be a prime and let b be any integer. For a = 2,...,p-1 let I(a,b) denote the number of positive integers x < p/2 with (x^2+b mod p) > (a*x^2+b mod p). Then both S = {I(a,b): 1 < a < p and (a/p) = 1} and T = {I(a,b): 1 < a < p and (a/p) = -1} have cardinality 1 or 2 according as p is congruent to 1 or 3 modulo 4, where (a/p) is the Legendre symbol. Moreover, the set S deos not depend on the value of b.
For any prime p == 1 (mod 4), we have q^2 == -1 (mod p) for some integer q, hence ((q*x)^2 mod p) > (a*(q*x)^2 mod p) if and only if (x^2 mod p) < (a*x^2 mod p). Thus, for each a = 2,...,p-1 there are exactly (p-1)/4 positive integers x < p/2 such that (x^2 mod p) > (a*x^2 mod p). Thus I(a,0) = (p-1)/4 for all a = 2,...,p-1.
The conjecture was confirmed by Q.-H. Hou, H. Pan and Z.-W. Sun in 2021. - Zhi-Wei Sun, Jul 22 2021
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
a(3) = 1 since prime(3) = 5, (1^2 mod 5) < (4*1^2 mod 5) and (2^2 mod 5) > (4*2^2 mod 5).
a(4) = 2 since prime(4) = 7, (1^2 mod 7) < (4*1^2 mod 7), (2^2 mod 7) > (4*2^2 mod 7) and (3^2 mod 7) > (4*3^2 mod 7).
|
|
|
MATHEMATICA
|
Inv[p_]:=Inv[p]=Sum[Boole[Mod[x^2, p]>Mod[4x^2, p]], {x, 1, (p-1)/2}]; Table[Inv[Prime[n]], {n, 1, 80}]
|
|
|
PROG
|
(PARI) a(n) = my(p=prime(n), m=p\2); if (n==1, m--); sum(k=1, m, lift(Mod(k, p)^2) > lift(Mod(2*k, p)^2)); \\ Michel Marcus, Oct 07 2018
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
