A241604 -id:A241604 - cp's OEIS frontend

A241568 a(n) = |{0 < k < prime(n)/2: k is not only a quadratic nonresidue modulo prime(n) but also a Fibonacci number}|.

0, 0, 1, 1, 1, 2, 2, 3, 1, 3, 2, 4, 2, 4, 2, 5, 3, 3, 5, 3, 4, 2, 5, 2, 4, 4, 3, 4, 3, 5, 3, 2, 5, 4, 7, 2, 6, 5, 4, 4, 5, 4, 3, 4, 7, 4, 4, 4, 5, 6, 4, 3, 5, 4, 3, 3, 3, 3, 3, 5, 6, 7, 8, 2, 5, 7, 6, 3, 5, 7, 5, 3, 4, 4, 6, 3, 6, 7, 4, 3

Offset: 1

Zhi-Wei Sun, Apr 25 2014

nonn

Conjecture: (i) a(n) > 0 for all n > 2. In other words, for any prime p > 3, there is a Fibonacci number among 1, ..., (p-1)/2 which is a quadratic nonresidue modulo p.
(ii) For any n > 2, there is a prime q < prime(n) such that the q-th Fibonacci number is a quadratic nonresidue modulo prime(n).
(iii) For any odd prime p, there is a Lucas number (i.e., a term of A000032) smaller than p which is a quadratic nonresidue modulo p.
We have checked part (i) for all primes p < 3*10^9, part (ii) for n up to 10^8, and part (iii) for the first 10^7 primes.
See also A241604 for a sequence related to part (i) of the conjecture.

			a(3) = 1 since F(3) = 2 is a quadratic nonresidue modulo prime(3) = 5, where F(n) denotes the n-th Fibonacci number.
a(4) = 1 since F(4) = 3 is a quadratic nonresidue modulo prime(4) = 7.
a(5) = 1 since F(3) = 2 is a quadratic nonresidue modulo prime(5) = 11.
a(9) = 1 since F(5) = 5 is a quadratic nonresidue modulo prime(9) = 23.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Z.-W. Sun, New observations on primitive roots modulo primes, arXiv preprint arXiv:1405.0290 [math.NT], 2014.

Cf. A000040, A000032, A000045, A236966, A239957, A239963, A241492, A241504, A241516, A241604.

f[k_]:=Fibonacci[k]
Do[m=0;Do[If[f[k]>Prime[n]/2,Goto[aa]];If[JacobiSymbol[f[k],Prime[n]]==-1,m=m+1];Continue,{k,2,(Prime[n]+1)/2}]; Label[aa];Print[n," ",m];Continue,{n,1,80}]

A241605 a(n) = |{0 < k < sqrt(prime(n))*log(prime(n)) : k is not only a quadratic nonresidue modulo prime(n) but also a Fibonacci number}|.

Original entry on oeis.org

0, 0, 2, 2, 1, 3, 2, 3, 1, 3, 2, 4, 2, 4, 2, 5, 3, 3, 6, 3, 4, 2, 5, 2, 4, 4, 3, 4, 3, 4, 2, 2, 5, 4, 7, 2, 6, 5, 4, 4, 5, 3, 2, 3, 6, 4, 3, 4, 5, 5, 4, 2, 4, 4, 3, 3, 3, 3, 3, 5, 6, 7, 8, 2, 5, 7, 6, 3, 5, 7, 5, 3, 4, 4, 6, 3, 6, 7, 4, 3

Offset: 1

Zhi-Wei Sun, Apr 26 2014

nonn

It might seem that a(n) > 0 for all n > 2, but this is not true. In fact, for the prime p = prime(139570751) = 2893610639, the integer 1346269 is the least Fibonacci number which is a quadratic nonresidue modulo p, and 1346269/(sqrt(p)*log(p)) is approximately equal to 1.1488.
Conjecture: For any odd prime p, let f(p) be the least Fibonacci number which is a quadratic nonresidue modulo p. Then f(p) = o(p^(0.7)) as p tends to infinity. Moreover,f(p) = O(p^c) for any constant c > c_0 = log_2((1+sqrt(5))/2).
This refinement of the conjecture in A241568 seems reasonable in view of the heuristic arguments described below. Let c be any constant greater than c_0 (which has the approximating value 0.694). Roughly speaking, there are about (log_2(p^c))/c_0 positive Fibonacci numbers below p^c. Suppose that a positive Fibonacci number is a quadratic residue modulo a fixed odd prime p with "probability" 1/2. Then we might expect that the "probability" for all positive Fibonacci numbers below p^c being quadratic residues modulo p is about (1/2)^(c*(log_2 p)/c_0) = 1/p^(c/c_0). As sum_p 1/p^(c/c_0) converges, it seems reasonabale to think that there are only finitely many odd primes p for which all positive Fibonacci numbers below p^c are quadratic residues mod p.

			a(3) = 2 since the Fibonacci numbers F(3) = 2 and F(4) = 3 are quadratic nonresidues modulo prime(3) = 5 which are also smaller than sqrt(5)*log(5).
a(4) = 2 since the Fibonacci numbers F(4) = 3 and F(5) = 5 are quadratic nonresidues modulo prime(4) = 7 which are also smaller than sqrt(7)*log(7).
a(5) = 1 since the Fibonacci number F(3) = 2 is a quadratic nonresidue modulo prime(5) = 11 which is also smaller than sqrt(11)*log(11).
a(9) = 1 since the Fibonacci number F(5) = 5 is a quadratic nonresidue modulo prime(9) = 23 which is also smaller than sqrt(23)*log(23).

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000

Cf. A000040, A000045, A241568, A241604.

f[k_]:=f[k]=Fibonacci[k]
Do[m=0;Do[If[f[k]>=Sqrt[Prime[n]]*Log[Prime[n]],Goto[aa]];If[JacobiSymbol[f[k],Prime[n]]==-1,m=m+1];Continue,{k,2,Prime[n]}];Label[aa];Print[n," ",m];Continue,{n,1,80}]

A241675 a(n) = |{0 < k < n/2: k is a Fibonacci number with x^2 == k (mod n) for no integer x}|.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 1, 3, 2, 2, 3, 3, 2, 4, 3, 3, 4, 2, 1, 4, 4, 3, 4, 4, 3, 5, 2, 5, 4, 2, 5, 4, 4, 4, 3, 5, 2, 5, 4, 5, 6, 2, 2, 6, 4, 5, 4, 5, 5, 5, 5, 5, 6, 4, 3, 5, 3, 3, 6, 6, 6, 5, 5, 3, 5, 6, 3, 7, 4, 4, 5, 6, 7, 5, 2, 7

Offset: 1

Zhi-Wei Sun, Apr 27 2014

nonn

a(n) > 0 for all n > 4 if and only if the conjecture in A241568 holds.

In fact, if n > 0 is a multiple of 4, then x^2 == F(3) = 2 (mod n) for no integer x. If n > 4 is composite with an odd prime divisor p, then by the conjecture in A241568 there should exist a Fibonacci number k < p <= n/2 such that x^2 == k (mod p) for no integer x and hence x^2 == k (mod n) for no integer x.

			a(5) = 1 since x^2 == F(3) = 2 (mod 5) for no integer x, but 1^2 == F(1) = F(2) = 1 (mod 5), where F(n) denotes the n-th Fibonacci number given by A000045.
a(7) = 1 since x^2 == F(4) = 3 (mod 7) for no integer x.
a(22) = 2 since there is no integer x such that x^2 == F(3) = 2 (mod 22) or x^2 == F(6) = 8 (mod 22).
a(23) = 1 since x^2 == F(5) = 5 (mod 23) for no integer x.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Z.-W. Sun, New observations on primitive roots modulo primes, arXiv preprint arXiv:1405.0290 [math.NT], 2014.

Cf. A000045, A000290, A241568, A241604, A241605.

f[k_]:=Fibonacci[k]
Do[m=0;Do[If[f[k]>=n/2,Goto[bb]];Do[If[Mod[i^2,n]==f[k],Goto[aa]],{i,0,n/2}];m=m+1;Label[aa];Continue,{k,2,(n+1)/2}];Label[bb];Print[n," ",m];Continue,{n,1,80}]

A331506 Least primitive root g < prime(n) of the n-th prime with g a product of two Fibonacci numbers, or 0 if such a number g does not exist.

Original entry on oeis.org

1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 13, 5, 3, 2, 3, 5, 2, 5, 2, 6, 3, 3, 2, 3, 2, 2, 6, 5, 2, 5, 2, 2, 2, 21, 5, 2, 3, 2, 3, 2, 6, 3, 13, 13, 6, 3, 5, 2, 6, 5, 3, 3, 2, 5, 34, 10, 2, 3, 10, 2, 2, 3, 13, 6, 2, 2, 5, 2, 5, 3, 21, 2, 2, 13, 5, 15, 2, 3, 13, 2, 3, 2, 13, 3, 2, 10, 5, 2, 3, 2, 2

Offset: 1

Zhi-Wei Sun, Jan 18 2020

nonn

Conjecture 1: a(n) > 0 for all n > 0. In other words, for each prime p there are two Fibonacci numbers F(k) and F(m) with F(k)*F(m) < p such that F(k)*F(m) is a primitive root modulo p.
This implies that for each odd prime p there exists a Fibonacci number F(k) < p which is a quadratic nonresidue modulo p.
It seems that Conjecture 1 can be strengthened as follows: For any prime p, there is a primitive root g < p modulo p such that g/F(2) = g or g/F(3) = g/2 or g/F(4) = g/3 is a Fibonacci number. We have verified this strong version for all primes p < 5*10^9.
We also have the following conjecture similar to Conjecture 1.
Conjecture 2. For any prime p, there are two Lucas numbers L(k) and L(m) with k >= m >= 0 and L(k)*L(m) < p such that L(k)*L(m) is a primitive root modulo p.
This has been verified for all primes p < 10^9.

			a(85) = 15 with 15 = 3*5 = F(4)*F(5) a primitive root modulo prime(85) = 439.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Zhi-Wei Sun, New observations on primitive roots modulo primes, arXiv preprint arXiv:1405.0290 [math.NT], 2014.
Zhi-Wei Sun, Primitive roots modulo primes related to Fibonacci numbers or Lucas numbers, Question 350730 at MathOverflow, Jan. 19, 2020.

Cf. A000032, A000040, A000045, A001918, A239957, A241476, A241504, A241568, A241604.

p[n_]:=p[n]=Prime[n];
Dv[n_]:=Dv[n]=Divisors[p[n]-1];
ls={};
Do[If[Fibonacci[k]Fibonacci[m]=p[n],tab=Append[tab,0];Goto[bb]];Do[If[PowerMod[ff[r],Dv[n][[i]],p[n]]==1,r=r+1;Goto[aa]],{i,1,Length[Dv[n]]-1}];tab=Append[tab,ff[r]];Label[bb],{n,1,100}];Print[tab]

cp's OEIS Frontend

A241568 a(n) = |{0 < k < prime(n)/2: k is not only a quadratic nonresidue modulo prime(n) but also a Fibonacci number}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A241605 a(n) = |{0 < k < sqrt(prime(n))*log(prime(n)) : k is not only a quadratic nonresidue modulo prime(n) but also a Fibonacci number}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A241675 a(n) = |{0 < k < n/2: k is a Fibonacci number with x^2 == k (mod n) for no integer x}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A331506 Least primitive root g < prime(n) of the n-th prime with g a product of two Fibonacci numbers, or 0 if such a number g does not exist.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica