A139035 -id:A139035 - cp's OEIS frontend

A179858 Least positive primitive root of A139035(n).

3, 5, 5, 7, 3, 5, 5, 19, 3, 7, 5, 6, 17, 7, 6, 5, 3, 13, 3, 5, 7, 3, 5, 11, 5, 3, 3, 11, 5, 5, 5, 5, 6, 14, 3, 3, 3, 17, 5, 3, 3, 6, 13, 5, 7, 3, 5, 11, 5, 19, 3, 5, 5, 3, 6, 10, 5, 5, 14, 6, 3, 7, 5, 5, 7, 5, 3, 3, 11, 5, 5, 3, 5, 6, 7, 3, 5, 7, 3, 7, 5, 5, 5, 17

Offset: 1

Vladimir Shevelev, Jan 11 2011

nonn

If p is a prime, then a is called a semiprimitive root if it has order (p-1)/2 and there is no x for which a^x is congruent to -1 (mod p). So +- a^k, 0 <= k <= (p-3)/2 is a complete set of nonzero residues (mod p). A primitive root has order p-1, so a number cannot be both a primitive root and a semiprimitive root.

A139035 are the primes for which 2 is a semiprimitive root. This sequence gives the smallest positive primitive root corresponding to each term of A139035, so each term is greater than or equal to 3.

			Since A139035(13)=311, 2 is a semiprimitive root of 311 so j=0,...,154, {+-2^j} is a complete set of residues (congruent to {1,...,310}).  The corresponding member of this sequence is a(13)=17 because 17 is the smallest positive integer a for which {a^k}, k=0,...,309 is a complete set of residues.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A001918, A139035.

PrimitiveRoot /@ Reap[For[p = 3, p < 3000, p = NextPrime[p], rp = MultiplicativeOrder[2, p]; rm = MultiplicativeOrder[-2, p]; If[rp != p-1 && rm == p-1, Sow[p]]]][[2, 1]] (* Jean-François Alcover, Sep 03 2016, after Joerg Arndt's code for A139035 *)

More terms from Jean-François Alcover, Sep 03 2016

A345388 a(n) = 0, 1, or 2 according to whether A065091(n), the n-th odd prime, is in A001122, A139035, or A268923, respectively.

Original entry on oeis.org

0, 0, 1, 0, 0, 2, 0, 1, 0, 2, 0, 2, 2, 1, 0, 0, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 0, 2, 2, 2, 0, 2, 0, 0, 2, 2, 0, 1, 0, 0, 0, 1, 2, 0, 1, 0, 2, 0, 2, 2, 1, 2, 2, 2, 1, 0, 1, 2, 2, 2, 0, 2, 1, 2, 0, 2, 2, 0, 0, 2, 1, 1, 0, 0, 1, 0, 2, 2, 2, 0, 0, 2, 2, 2, 0, 2, 2

Offset: 1

Howard Givner, Jun 17 2021

nonn

The three OEIS sequences A001122, A139035, and A268923 are implicitly described in a Zoom lecture that was given May 14, 2021, by James Tanton. Here is a link to the video, followed by a description of how the sequences can be obtained by carrying out the procedure that the speaker described in his talk.
Description of the method:
James Tanton defined GOOD, HALF-GOOD, and BAD odd prime integers and a procedure for determining which of the three categories an odd prime integer belongs to.
Procedure for categorizing an odd prime integer P:
Step 1. Begin with an initial partition (1,P-1) of P.
Step 2. Generate a successor partition, derived from an existing partition.
When (x,y) is an existing partition and x is even, the successor partition is (s,t), where s=x/2 and t=P-s.
When (x,y) is an existing partition and x is odd, the successor partition is (s,t), where t=y/2 and s=P-t.
Step 3. Repeat step 2 until you return to (1,P-1).
He then classified P as either GOOD, HALF-GOOD, or BAD as follows:
P is GOOD when every integer from 1 to P-1 appears among the left parts of the set of generated partitions.
P is HALF-GOOD when P does not meet the requirements for GOOD, but every integer from 1 to P-1 appears somewhere in the set of generated partitions.
P is BAD when P does not meet the requirements for GOOD or HALF-GOOD.
The sequence of GOOD odd prime integers is identical to A001122.
The sequence of HALF-GOOD odd prime integers is identical to A139035.
The sequence of BAD odd prime integers is identical to A268923.

			For P=5, the generated partition set is:
  (1,4), (3,2), (4,1), (2,3), (1,4), and thus 5 is GOOD, so a(2)=0.
For P=7, the generated partition set is:
  (1,6), (4,3), (2,5), (1,6), and thus 7 is HALF-GOOD, so a(3)=1.
For P=17, the generated partition set is:
  (1,16), (9,8), (13,4), (15,2), (16,1), (8,9), (4,13), (2,15), (1,16),
  but 3, 5, 6, 7, 10, 11, 12, and 14 do not appear, and thus 17 is BAD, so a(6)=2.

James Tanton, How to fold things into thirds, sevenths, and thirty-sevenths!, video, May 14, 2021.

Cf. A001122, A065091, A139035, A268923.

Name edited by Felix Fröhlich, Jun 28 2021

A151913 Numbers n for which (8+n!)/8 is prime.

Original entry on oeis.org

7, 9, 10, 12, 14, 20, 23, 24, 29, 44, 108, 2049, 3072, 4862, 8807, 15089

Offset: 1

Artur Jasinski, Apr 07 2008

nonn

a(17) > 25000. - Robert Price, Dec 20 2016

For primes of the form (8+k!!)/8 see A139066.
Cf. A089130, A117141, A139035, A139057, A139059, A139060, A139062, A139064, A139067.
Cf. n!/m-1 is a prime: A002982, A082671, A139056, A139199-A139205; n!/m+1 is a prime: A002981, A082672, A089085, A139061, A139058, A139063, A139065, A151913, A137390, A139071 (1<=m<=10).

a = {}; Do[If[PrimeQ[(n! + 8)/8], AppendTo[a, n]], {n, 1, 500}]; a

is(n)=n>6 && isprime((8+n!)/8) \\ Charles R Greathouse IV, Apr 29 2016

Definition corrected Feb 24 2010
More terms from Serge Batalov, Feb 18 2015
a(15)-a(16) from Robert Price, Dec 20 2016

A133954 Difference between the numbers of nonnegative evil and odious multiples of p_n less than 2^p_n, where p_n = n-th prime.

Original entry on oeis.org

0, 3, 5, -7, 11, 13, 697, 19, -23, 29, -237367, 37, 97129, 44250483, -47, 53, 59, 61, 67, -71, 1325443061345, -79, 83, 6096136101052865, 6711137545, 101, -103, 107, 197096207419453, 1733616652657, -16388345406766785202757351, 131, 904581545

Offset: 1

Vladimir Shevelev, Sep 30 2007, Dec 17 2008

sign

The following statements are true: 1) If prime p_n has a primitive root 2, then a(n)=p_n; 2) If prime p_n has a semiprimitive root 2, then a(n)=-p_n (for definition of semiprimitive root 2 of a prime, see the 2nd link, p. 1).
A comparison of Gerbicz's calculations up to a(46) with A001122 and A139035 shows that one can conjecture that the converse statements are true as well.
Subset of A225855.

			Consider p_2=3; since 0,3,6 are evil, then a(2) = 3 - 0 = 3.

J. Coquet, A summation formula related to the binary digits, Invent. Math. 73 (1983) 107-115.
M. Drmota and M. Skalba, Rarified sums of the Thue-Morse sequence, Trans. of the AMS 352 No. 2 (1999) 609-642.
D. J. Newman, On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc. 21 (1969) 719-721.
V. Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, arXiv:0710.1354 [math.NT], 2007.
V. Shevelev, Generalized Newman phenomena and digit conjectures on primes, Internat. J. of Mathematics and Math. Sciences, 2008 (2008), Article ID 908045, 1-12.
V. Shevelev, Exact exponent of remainder term of Gelfond's digit theorem in the binary case, Acta Arithmetica 136 (2009) 91-100.
I. Shparlinski, On the size of the Gelfond exponent, J. of Number Theory, 130, no.4 (2010), 1056-1060.

Cf. A000069, A001969, A001122, A139035, A225855.

a(p)=o=e=vector(p,i,0);e[p]=1;r=1;for(i=1,p,o2=e2=vector(p);for(j=1,p,w=(j-r)%p;if(w==0,w=p);o2[j]=o[j]+e[w];e2[j]=e[j]+o[w]);o=o2;e=e2;r=(2*r)%p);return(e[p]-o[p]) \\ Robert Gerbicz, Jan 03 2011

a(n) = p_n if 2 is a primitive root of p_n (A001122); a(n) = -p_n if p_n is in A139035, i.e., -2 is a primitive root of p_n [Shevelev, 2007]. No other exact regularity of the sequence is known until now. - Vladimir Shevelev, Oct 26 2014

Extended by Robert Gerbicz, Jan 03 2011

A295835 Numbers k == 3 (mod 4) such that 2^((k-1)/2), 3^((k-1)/2) and 5^((k-1)/2) are congruent to 1 (mod k).

Original entry on oeis.org

71, 191, 239, 311, 359, 431, 479, 599, 719, 839, 911, 1031, 1151, 1319, 1439, 1511, 1559, 1871, 2039, 2111, 2351, 2399, 2591, 2711, 2879, 2999, 3119, 3191, 3359, 3671, 3719, 3911, 4079, 4271, 4391, 4679, 4751, 4799, 4871, 4919, 5039, 5231, 5279, 5351, 5399, 5471

Offset: 1

Jonas Kaiser, Nov 28 2017

nonn

There are very few composite numbers in this sequence: The probability of catching a pseudoprime number (A001567) with this definition is estimated at 1 in 263 billion.
Composite numbers in the sequence include the Carmichael numbers 131314855918751, 23282264781147191, 70122000249565031, 104782993259720471, 583701149409931151, 870012810301712351. - Robert Israel, Nov 28 2017
With the exception of the pseudoprimes, it seems that this is a subsequence of A139035. Primes of this form (A139035) have two special properties. 1. There exists a smallest m of the form m = (A139035 - 1)/2 such that 2^m == 1 (mod A139035). 2. m is odd. The core of this definition is based on these two properties. The term 2^((k-1)/2) == 1 (mod n) is based on the first property, while the term k == 3 (mod 4) is based on the second property. The terms 3^((k-1)/2) == 1 (mod n) and 5^((k-1)/2) == 1 (mod n) I just tried freely to Fermat.
Prime terms are congruent to 71 or 119 modulo 120. - Jianing Song, Nov 22 2018 [This is because 2, 3, and 5 must be quadratic residues modulo every prime number in this sequence. - Jianing Song, Sep 01 2024]
From Jianing Song, Sep 03 2024: (Start)
Compare this sequence to the sequence of absolute Euler pseudoprimes (A033181): odd composite numbers k such that a^((k-1)/2) == +-1 (mod k) for every a coprime to k. Such numbers k satisfy 2*psi(k) | (k-1), where psi = A002322, so we must have k == 1 (mod 4).
All terms in this sequence are congruent to 7 modulo 8. In fact, taking the Jacobi symbol modulo k (which only depends on the remainder modulo k) of both sides of 2^((k-1)/2) == 1 (mod k) yields (2/k)^((k-1)/2) = 1. Since k == 3 (mod 4), we have that (k-1)/2 is odd, so (2/k) = 1, which means that k == 7 (mod 8). (End)
Those numbers given above by Robert Israel are all congruent to 71 modulo 120. There are no known composite terms congruent to 119 modulo 120; cf. A294092. - Bill McEachen and Jianing Song, Sep 05 2024

Robert Israel, Table of n, a(n) for n = 1..10000
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.

Cf. A001567, A293394, A294717, A294993, A294919, A294912.

A294092 is a subsequence.

filter:= proc(n) [2&^((n-1)/2),3&^((n-1)/2), 5&^((n-1)/2)] mod n = [1,1,1]  end proc:
select(filter, [seq(i,i=3..10000,4)]); # Robert Israel, Nov 28 2017, corrected Feb 26 2018

fQ[n_] := PowerMod[{2, 3, 5}, (n - 1)/2, n] == {1, 1, 1}; Select[3 + 4Range@ 1500, fQ] (* Michael De Vlieger, Nov 28 2017 and slightly modified by Robert G. Wilson v, Feb 26 2018 based on the renaming *)

is(n) = n%4==3 && Mod(2, n)^(n\2)==1 && Mod(3, n)^(n\2)==1 && Mod(5, n)^(n\2)==1 && Mod(2, n)^logint(n+1,2)!=1 \\ Charles R Greathouse IV, Nov 28 2017

Definition corrected by Jonas Kaiser, Feb 05 2018

A295196 Numbers n > 1 such that 2^(n-1) and (2n-m)2^(((n-1)/2) - floor(log_2(n))) are congruent to 1 (mod n) for at least one of m = 3, m = 7 and m = 15.

Original entry on oeis.org

7, 23, 31, 47, 71, 79, 263, 271, 1031, 1039, 2063, 4111, 32783, 65543, 65551, 262151, 1048583, 4194319, 8388623, 67108879, 268435463, 1073741831, 1073741839, 4294967311

Offset: 1

Jonas Kaiser, Nov 16 2017

This definition arises from the conjecture that pseudoprime numbers (A001567) occur only at certain distances m from the next smaller number of the form 2^n. So, if we know that a certain distance does not appear with pseudoprime numbers, we are able to calculate these numbers using Fermat's little theorem and we know that it has to be prime. To "plot" the distance of pseudoprime numbers to 2^n use m = A001567(n) - 2^floor(log_2(A001567(n))). So, the first values of m which do not have a "safe prime number distance" (values with "safe prime number distance" are those values for m which pseudoprime numbers never have) should be m = 1, 49, 81, 85, 129, 133, 273, 275, 289, 321, ....
Conjecture 1: There are no composite numbers in this sequence and perhaps infinitely many primes.
Conjecture 2: For m = 7 this definition generates A104066 and for m = 15 this definition generates A144487 (A057197).
Conjecture 3: There are (infinitely many?) m for which this definition generates nothing but (infinitely many?) primes of the form p = 2^k + m.
It appears that this sequence is a subsequence of A139035.

Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.

Cf. A057197, A104066, A139035, A144487, A244626, A294717, A293394.

twoDistableQ[n_] := MemberQ[Mod[(2n - {3, 7, 15}) PowerMod[2, (n - 1)/2 - Floor@ Log2@ n, n], n], 1]; p = 3; twoDistablesList = {}; While[p < 1000000000, If[twoDistableQ@ p, AppendTo[ twoDistablesList, p]]; p = NextPrime@ p]; twoDistablesList (* Robert G. Wilson v, Nov 17 2017 *)

a(n) = (n%2) && lift((Mod(2, n)^(n-1))==1) && (lift((Mod((2*n-3), n)*Mod(2, n)^(((n-1)/2)-floor(log(n)/log(2)))) == 1)||lift((Mod((2*n-7), n)*Mod(2, n)^(((n-1)/2)-floor(log(n)/log(2)))) == 1)||lift((Mod((2*n-15), n)*Mod(2, n)^(((n-1)/2)-floor(log(n)/log(2)))) == 1))

is(n)=if(Mod(2,n)^(n-1)!=1, return(0)); my(m=Mod(2,n)^(n\2-logint(n,2))); ((2*n-3)*m==1 || (2*n-7)*m==1 || (2*n-15)*m==1) && n>1 \\ Charles R Greathouse IV, Nov 17 2017

a(17)-a(24) from Charles R Greathouse IV, Nov 17 2017

cp's OEIS Frontend

A179858 Least positive primitive root of A139035(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A345388 a(n) = 0, 1, or 2 according to whether A065091(n), the n-th odd prime, is in A001122, A139035, or A268923, respectively.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A151913 Numbers n for which (8+n!)/8 is prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A133954 Difference between the numbers of nonnegative evil and odious multiples of p_n less than 2^p_n, where p_n = n-th prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A295835 Numbers k == 3 (mod 4) such that 2^((k-1)/2), 3^((k-1)/2) and 5^((k-1)/2) are congruent to 1 (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A295196 Numbers n > 1 such that 2^(n-1) and (2*n-m)*2^(((n-1)/2) - floor(log_2(n))) are congruent to 1 (mod n) for at least one of m = 3, m = 7 and m = 15.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A295196 Numbers n > 1 such that 2^(n-1) and (2n-m)2^(((n-1)/2) - floor(log_2(n))) are congruent to 1 (mod n) for at least one of m = 3, m = 7 and m = 15.