A241568 -id:A241568 - cp's OEIS frontend

A241504 a(n) = |{0 < g < prime(n): g is not only a primitive root modulo prime(n) but also a partition number given by A000041}|.

1, 1, 2, 2, 2, 3, 4, 3, 4, 4, 3, 4, 5, 3, 5, 4, 5, 3, 3, 5, 4, 4, 6, 5, 4, 6, 4, 6, 4, 3, 4, 4, 3, 7, 8, 5, 3, 6, 5, 8, 5, 2, 5, 7, 7, 6, 4, 7, 7, 2, 7, 5, 3, 6, 6, 10, 9, 5, 8, 7, 5, 10, 5, 5, 3, 8, 5, 5, 9, 4, 5, 5, 5, 8, 7, 10, 9, 6, 7, 4

Offset: 1

Zhi-Wei Sun, Apr 24 2014

nonn

Conjecture: (i) a(n) > 0 for all n > 0. In other words, any prime p has a primitive root g < p which is also a partition number.
(ii) Any prime p > 3 has a primitive root g < p which is also a strict partition number (i.e., a term of A000009).
We have checked part (i) for all primes p < 2*10^7, and part (ii) for all primes p < 5*10^6. See also A241516.

			a(92) = 1 since p(13) = 101 is a primitive root modulo prime(92) = 479, where p(.) is the partition function (A000041).
a(493) = 1 since p(20) = 627 is a primitive root modulo prime(493) = 3529.
a(541) = 1 since p(20) = 627 is a primitive root modulo prime(541) = 3911.
a(1146) = 1 since p(27) = 3010 is a primitive root modulo prime(1146) = 9241.
a(1951) = 1 since p(35) = 14883 is a primitive root modulo prime(1951) = 16921.
a(2380) = 1 since p(36) = 17977 is a primitive root modulo prime(2380) = 21169.
a(5629) = 1 since p(20) = 627 is a primitive root modulo prime(5629) = 55441.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Zhi-Wei Sun, Problems on combinatorial properties of primes, arXiv:1402.6641, 2014.

Cf. A000009, A000040, A000041, A237121, A239957, A239963, A241476, A241492, A241516, A241568.

f[k_]:=PartitionsP[k]
dv[n_]:=Divisors[n]
Do[m=0;Do[If[f[k]>Prime[n]-1,Goto[bb]];Do[If[Mod[f[k]^(Part[dv[Prime[n]-1],i]),Prime[n]]==1,Goto[aa]],{i,1,Length[dv[Prime[n]-1]]-1}];m=m+1;Label[aa];Continue,{k,1,Prime[n]-1}];Label[bb];Print[n," ",m];Continue,{n,1,80}]

A241604 Least Fibonacci number smaller than prime(n)/2 which is a quadratic nonresidue modulo prime(n), or 0 if such a Fibonacci number does not exist.

Original entry on oeis.org

0, 0, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 2, 2, 2, 13, 5, 3, 2, 3, 5, 2, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 2, 5, 2, 2, 2, 21, 5, 2, 3, 2, 3, 2, 2, 3, 13, 13, 2, 3, 5, 2, 3, 2, 3, 2, 2, 2, 34, 5, 2, 2, 5, 2, 2, 3, 13, 3, 2, 2, 5, 2, 2, 3, 13

Offset: 1

Zhi-Wei Sun, Apr 26 2014

nonn

According to the conjecture in A241568, a(n) should be positive for all n > 2.

			a(4) = 3 since the Fibonacci number F(4) = 3 < prime(4)/2 is a quadratic nonresidue modulo prime(4) = 7, but the Fibonacci numbers F(1) = F(2) = 1 and F(3) = 2 are quadratic residues modulo prime(4) = 7.

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, A000045, A241568.

f[k_]:=Fibonacci[k]
Do[Do[If[f[k]>Prime[n]/2,Goto[bb]];If[JacobiSymbol[f[k],Prime[n]]==-1,Print[n," ",Fibonacci[k]];Goto[aa]];Continue,{k,1,(Prime[n]+1)/2}];Label[bb];Print[n," ",0];Label[aa];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

A241504 a(n) = |{0 < g < prime(n): g is not only a primitive root modulo prime(n) but also a partition number given by A000041}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A241604 Least Fibonacci number smaller than prime(n)/2 which is a quadratic nonresidue modulo prime(n), or 0 if such a Fibonacci number does not exist.

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