A027697 -id:A027697 - cp's OEIS frontend

A095005 Number of odious primes (A027697) in range ]2^n,2^(n+1)].

0, 1, 2, 2, 5, 8, 19, 20, 48, 75, 160, 242, 505, 835, 1761, 2799, 5890, 10250, 20921, 36872, 74316, 134816, 267749, 492286, 977207, 1823657, 3598657, 6779899, 13336543, 25358424, 49763462, 95140695, 186504600, 358630024, 702300885, 1356118149, 2654709953, 5142968571

Offset: 1

Antti Karttunen and Labos Elemer, Jun 01 2004

nonn

Antti Karttunen and John Moyer, C-program for computing the initial terms of this sequence.
Index entries for sequences related to occurrences of various subsets of primes in range ]2^n,2^(n+1)].

Cf. A027697, A036378, A095006.

Table[Count[Prime@ Range[PrimePi[2^n] + 1, PrimePi[2^(n + 1) - 1]], k_ /; OddQ@ First@ DigitCount[k, 2]], {n, 24}] (* Michael De Vlieger, Feb 25 2017 *)

a(n) = #select(x->((hammingweight(x)%2)==1),primes([2^n+1,2^(n+1)])); \\ Michel Marcus, Feb 26 2017

a(n) = A036378(n) - A095006(n).

a(34)-a(38) from Amiram Eldar, Jun 20 2024

A177798 First primes of record chains of consecutive primes such that all of them are odious (A027697).

Original entry on oeis.org

2, 7, 167, 199, 6271, 12227, 168713, 579907, 5937157, 6829751, 8059943, 66858173, 167857663, 661416709, 2322857987, 12012698381, 14641587607, 26304771553, 49671709081, 1244930533403, 1922085626009

Offset: 1

Vladimir Shevelev, Dec 12 2010

The corresponding record lengths are: 1,3,6,9,11,15, etc. (A177800).

Cf. A177748 (evil version), A000069, A001969, A027697, A027699, A177800.

back(p,k)=while(k--,p=precprime(p-1));precprime(p-1)
r=s=0;forprime(p=2,1e9,if(hammingweight(p)%2,s++,if(s>r,r=s;print1(back(p,r)", "));s=0)) \\ Charles R Greathouse IV, Mar 29 2013

More terms from D. S. McNeil, Dec 12 2010

a(20)-a(21) from Amiram Eldar, Dec 09 2020

A231254 Odious primes p (A027697) such that p^2 and p^3 are evil (A027699).

Original entry on oeis.org

37, 47, 107, 137, 233, 331, 463, 491, 557, 587, 607, 631, 653, 733, 823, 829, 883, 947, 971, 997, 1153, 1187, 1193, 1231, 1249, 1321, 1327, 1493, 1543, 1567, 1663, 1667, 1669, 1709, 1787, 1801, 1933, 1987, 2011, 2027, 2087, 2143, 2161, 2213, 2269, 2273, 2311

Offset: 1

Vladimir Shevelev and Peter J. C. Moses, Nov 06 2013

Sequence {a(n)^4} is a subsequence of A227891 such that a(1)^4 = 1874161 is the smallest power of an odious prime that is in A227891.

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

Cf. A001969, A027697, A027699, A227891.

evilQ[n_]:=EvenQ[DigitCount[n,2][[1]]];
odiousQ[n_]:=OddQ[DigitCount[n, 2][[1]]];
Select[Range[2000],PrimeQ[#]&&odiousQ[#]&&evilQ[#^2]&&evilQ[#^3]&] (* Peter J. C. Moses, Nov 08 2013 *)

A360648 Fully multiplicative with a(A027697(k)) = A027699(k) and a(A027699(k)) = A027697(k) for any k > 0.

Original entry on oeis.org

1, 3, 2, 9, 7, 6, 5, 27, 4, 21, 17, 18, 23, 15, 14, 81, 11, 12, 29, 63, 10, 51, 13, 54, 49, 69, 8, 45, 19, 42, 43, 243, 34, 33, 35, 36, 53, 87, 46, 189, 71, 30, 31, 153, 28, 39, 83, 162, 25, 147, 22, 207, 37, 24, 119, 135, 58, 57, 89, 126, 101, 129, 20, 729

Offset: 1

Rémy Sigrist, Feb 15 2023

In other words, we replace odious prime numbers with evil prime numbers and vice versa.

This sequence is a self-inverse permutation of the positive integers.

			For n = 84:
- 82 = 2^2 * 3 * 7,
- a(2) = a(A027697(1)) = A027699(1) = 3,
- a(3) = a(A027699(1)) = A027697(1) = 2,
- a(7) = a(A027697(2)) = A027699(2) = 5,
- so a(84) = 3^2 * 2 * 5 = 90.

Rémy Sigrist, Scatterplot of (n, a(n)) such that n, a(n) <= 100000
Rémy Sigrist, PARI program
Index entries for sequences that are permutations of the natural numbers

Cf. A061898, A027697, A027699, A341090.

PARI
```
See Links section.
```

A131122 Even numbers that are not the sum of an evil prime (A027699) and an odious prime (A027697).

Original entry on oeis.org

2, 4, 6, 8, 20, 26, 32, 38, 68, 86, 92, 98, 128, 164, 188, 278, 302, 512, 2048, 8192, 32768, 131072, 524288, 2097152, 8388608, 33554432, 134217728, 536870912

Offset: 1

T. D. Noe, Jun 15 2007

Every power of 2 with an odd exponent is a term.

Every pair of primes that sum to 4^k, with k > 1, consists of an evil prime and an odious prime. The smallest example is 16 = 3+13 = 5+11; 3 and 5 are evil, 11 and 13 are odious.

			32 is here because 32 = 3+29 = 13+19, 3 and 29 are both odious, and 13 and 19 are both evil.

Cf. A004171 (odd powers of 2), A027697, A027699.

isok(n) = {if ((n % 2) == 0, forprime(p=3, n, if ((norml2(binary(p))%2==1) && (isprime(q=n-p)) && (!bittest(norml2(binary(q)), 0)), return (0));); return (1);); return(0);}
lista(nn) = forstep(n=2, nn, 2, if (isok(n), print1(n, ", "))); \\ Michel Marcus, Oct 14 2018

a(23)-a(28) from Michel Marcus, Oct 14 2018

A231253 Terms of A227891 of the form (p*q)^2, where p <= q are odious primes (A027697).

Original entry on oeis.org

582169, 797449, 1874161, 1934881, 2007889, 2181529, 3024121, 3171961, 4879681, 5387041, 6775609, 9174841, 11771761, 16072081, 18653761, 19070689, 20894041, 22762441, 25694761, 26635921, 29953729, 31214569, 33166081, 40081561, 42081169, 45873529, 48177481, 49463089, 50367409

Offset: 1

Vladimir Shevelev and Peter J. C. Moses, Nov 06 2013

a(1) = 582169 is the smallest term > 1 of A227891 which does not have an evil prime divisor.

The sequence lists numbers of the form (p*q)^2 such that either q > p are both odious primes and among the numbers {p^2, p*q, q^2, p^2*q, q^2*p} there is exactly one odious, or q=p is an odious prime, while p^2 and p^3 are both evil.

Cf. A000069, A001969, A027697, A227891.

A000069 Odious numbers: numbers with an odd number of 1's in their binary expansion.

Original entry on oeis.org

1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59, 61, 62, 64, 67, 69, 70, 73, 74, 76, 79, 81, 82, 84, 87, 88, 91, 93, 94, 97, 98, 100, 103, 104, 107, 109, 110, 112, 115, 117, 118, 121, 122, 124, 127, 128

Offset: 1

N. J. A. Sloane

This sequence and A001969 give the unique solution to the problem of splitting the nonnegative integers into two classes in such a way that sums of pairs of distinct elements from either class occur with the same multiplicities [Lambek and Moser]. Cf. A000028, A000379.
In French: les nombres impies.
Has asymptotic density 1/2, since exactly 2 of the 4 numbers 4k, 4k+1, 4k+2, 4k+3 have an even sum of bits, while the other 2 have an odd sum. - Jeffrey Shallit, Jun 04 2002
Nim-values for game of mock turtles played with n coins.
A115384(n) = number of odious numbers <= n; A000120(a(n)) = A132680(n). - Reinhard Zumkeller, Aug 26 2007
Indices of 1's in the Thue-Morse sequence A010060. - Tanya Khovanova, Dec 29 2008
For any positive integer m, the partition of the set of the first 2^m positive integers into evil ones E and odious ones O is a fair division for any polynomial sequence p(k) of degree less than m, that is, Sum_{k in E} p(k) = Sum_{k in O} p(k) holds for any polynomial p with deg(p) < m. - Pietro Majer, Mar 15 2009
For n>1 let b(n) = a(n-1). Then b(b(n)) = 2b(n). - Benoit Cloitre, Oct 07 2010
Lexicographically earliest sequence of distinct nonnegative integers with no term being the binary exclusive OR of any terms. The equivalent sequence for addition or for subtraction is A005408 (the odd numbers) and for multiplication is A026424. - Peter Munn, Jan 14 2018
Numbers of the form m XOR (2*m+1) for some m >= 0. - Rémy Sigrist, Apr 14 2022

			For k=2, x=0 and x=0.2 we respectively have 1^2 + 2^2 + 4^2 + 7^2 = 0^2 + 3^2 + 5^2 + 6^2 = 70;
(1.2)^2 + (2.2)^2 + (4.2)^2 + (7.2)^2 = (0.2)^2 + (3.2)^2 + (5.2)^2 + (6.2)^2 = 75.76;
for k=3, x=1.8, we have (2.8)^3 + (3.8)^3 + (5.8)^3 + (8.8)^3 + (9.8)^3 + (12.8)^3 + (14.8)^3 + (15.8)^3 = (1.8)^3 + (4.8)^3 + (6.8)^3 + (7.8)^3 + (10.8)^3 + (11.8)^3 + (13.8)^3 + (16.8)^3 = 11177.856. - _Vladimir Shevelev_, Jan 16 2012

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 433.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 22.
Vladimir S. Shevelev, On some identities connected with the partition of the positive integers with respect to the Morse sequence, Izv. Vuzov of the North-Caucasus region, Nature sciences 4 (1997), 21-23 (in Russian).
N. J. A. Sloane, A handbook of Integer Sequences, Academic Press, 1973 (including this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10001
Jean-Paul Allouche, The zeta-regularized product of odious numbers, arXiv:1906.10532 [math.NT], 2019.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Jean-Paul Allouche, Jeffrey Shallit and G. Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math. 292 (2005) 1-15.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, Aequationes mathematicae, March 2015, pp 1-13.
Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 19.
E. Fouvry and C. Mauduit, Sommes des chiffres et nombres presque premiers, (French) [Sums of digits and almost primes] Math. Ann. Vol. 305, No. 1 (1996), 571-599, DOI:10.1007/BF01444238, MR1397437 (97k:11029).
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Mathematics, Volume 312, Issue 1, 6 January 2012, Pages 42-46.
Maciej Gawron, and Maciej Ulas, On formal inverse of the Prouhet-Thue-Morse sequence, Discrete Mathematics 339.5 (2016): 1459-1470. Also arXiv preprint, arXiv:1601.04840 [math.CO], 2016.
R. K. Guy, The unity of combinatorics, Proc. 25th Iranian Math. Conf, Tehran, (1994), Math. Appl 329 129-159, Kluwer Dordrecht 1995, Math. Rev. 96k:05001.
R. K. Guy, Impartial games, pp. 35-55 of Combinatorial Games, ed. R. K. Guy, Proc. Sympos. Appl. Math., 43, Amer. Math. Soc., 1991.
Sajed Haque, Chapter 3.2 of Discriminators of Integer Sequences, Thesis, 2017.
Sajed Haque and Jeffrey Shallit, Discriminators and k-Regular Sequences, arXiv:1605.00092 [cs.DM], 2016.
K. Jensen, Aesthetics and quality of numbers using the primety measure, Int. J. Arts and Technology, Vol. 7, Nos. 2/3, 2014.
Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160. [From _N. J. A. Sloane_, Jan 31 2012]
Tanya Khovanova, There are no coincidences, arXiv:1410.2193 [math.CO], 2014.
J. Lambek and L. Moser, On some two way classifications of integers, Canad. Math. Bull. 2 (1959), 85-89.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255-261.
H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.
D. J. Newman, A Problem Seminar, Problem 15 pp. 5; 15 Springer-Verlag NY 1982.
Aayush Rajasekaran, Jeffrey Shallit and Tim Smith, Additive Number Theory via Automata Theory, Theory of Computing Systems (2019) 1-26.
Jeffrey Shallit, Additive Number Theory via Automata and Logic, arXiv:2112.13627 [math.NT], 2021.
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, arXiv:1207.0404 [math.NT], 2012-2014. - From _N. J. A. Sloane_, Dec 17 2012
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, INTEGERS, 14(2014) #64.
Vladimir Shevelev and Peter J. C. Moses, A family of digit functions with large periods, arXiv:1209.5705 [math.NT], 2012.
Andrzej Tomski and Maciej Zakarczemny, A note on Browkin's and Cao's cancellation algorithm, Technical Transections 7/2018.
Eric Weisstein's World of Mathematics, Odious Number
Index entries for sequences related to binary expansion of n
Index entries for "core" sequences

The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.
Complement of A001969 (the evil numbers). Cf. A133009.
a(n) = 2*n + 1 - A010060(n) = A001969(n) + (-1)^A010060(n).
First differences give A007413.
Cf. A000773, A181155, A019568, A059009.
Note that A000079, A083420, A002042, A002089, A132679 are subsequences.
See A027697 for primes, also A230095.
Cf. A005408 (odd numbers), A006068, A026424.
Cf. A010059, A010060.

a000069 n = a000069_list !! (n-1)
a000069_list = [x | x <- [0..], odd $ a000120 x]
-- Reinhard Zumkeller, Feb 01 2012

[ n: n in [1..130] | IsOdd(&+Intseq(n, 2)) ]; // Klaus Brockhaus, Oct 07 2010

s := proc(n) local i,j,k,b,sum,ans; ans := [ ]; j := 0; for i while jA000069 := n->t1[n]; # s(k) gives first k terms.
is_A000069 := n -> type(add(i,i=convert(n,base,2)),odd):
seq(`if`(is_A000069(i),i,NULL),i=0..40); # Peter Luschny, Feb 03 2011

Select[Range[300], OddQ[DigitCount[ #, 2][[1]]] &] (* Stefan Steinerberger, Mar 31 2006 *)
a[ n_] := If[ n < 1, 0, 2 n - 1 - Mod[ Total @ IntegerDigits[ n - 1, 2], 2]]; (* Michael Somos, Jun 01 2013 *)

{a(n) = if( n<1, 0, 2*n - 1 - subst( Pol(binary( n-1)), x, 1) % 2)}; /* Michael Somos, Jun 01 2013 */

{a(n) = if( n<2, n==1, if( n%2, a((n+1)/2) + n-1, -a(n/2) + 3*(n-1)))}; /* Michael Somos, Jun 01 2013 */

a(n)=2*n-1-hammingweight(n-1)%2 \\ Charles R Greathouse IV, Mar 22 2013

[n for n in range(1, 201) if bin(n)[2:].count("1") % 2] # Indranil Ghosh, May 03 2017

def A000069(n): return ((m:=n-1)<<1)+(m.bit_count()&1^1) # Chai Wah Wu, Mar 03 2023

G.f.: 1 + Sum_{k>=0} (t*(2+2t+5t^2-t^4)/(1-t^2)^2) * Product_{j=0..k-1} (1-x^(2^j)), t=x^2^k. - Ralf Stephan, Mar 25 2004
a(n+1) = (1/2) * (4*n + 1 + (-1)^A000120(n)). - Ralf Stephan, Sep 14 2003
Numbers n such that A010060(n) = 1. - Benoit Cloitre, Nov 15 2003
a(2*n+1) + a(2*n) = A017101(n) = 8*n+3. a(2*n+1) - a(2*n) gives the Thue-Morse sequence (1, 3 version): 1, 3, 3, 1, 3, 1, 1, 3, 3, 1, 1, 3, 1, ... A001969(n) + A000069(n) = A016813(n) = 4*n+1. - Philippe Deléham, Feb 04 2004
(-1)^a(n) = 2*A010060(n)-1. - Benoit Cloitre, Mar 08 2004
a(1) = 1; for n > 1: a(2*n) = 6*n-3 -a(n), a(2*n+1) = a(n+1) + 2*n. - Corrected by Vladimir Shevelev, Sep 25 2011
For k >= 1 and for every real (or complex) x, we have Sum_{i=1..2^k} (a(i)+x)^s = Sum_{i=1..2^k} (A001969(i)+x)^s, s=0..k.
For x=0, s <= k-1, this is known as Prouhet theorem (see J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence). - Vladimir Shevelev, Jan 16 2012
a(n+1) mod 2 = 1 - A010060(n) = A010059(n). - Robert G. Wilson v, Jan 18 2012
A005590(a(n)) > 0. - Reinhard Zumkeller, Apr 11 2012
A106400(a(n)) = -1. - Reinhard Zumkeller, Apr 29 2012
a(n+1) = A006068(n) XOR (2*A006068(n) + 1). - Rémy Sigrist, Apr 14 2022

A014499 Number of 1's in binary representation of n-th prime.

Original entry on oeis.org

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

Offset: 1

Ingemar Assarsjo (ingemar(AT)binomen.se)

a(n) is the rank of prime(n) in the base-2 dominance order on the natural numbers. - Tom Edgar, Mar 25 2014

			From _M. F. Hasler_, Mar 03 2023: (Start)
a(n) = 1 only for p(n = 1) = 2, the only prime equal to a power of 2.
a(n) = 2 for n in A159611 = A000720(A019434) = {2, 3, 7, 55, 6543} (probably complete), the Fermat primes F[k] = 2^2^k + 1 with k = 0, 1, 2, 3, 4. (On the graph one can distinctly see a(6543) = 2 corresponding to F[4] = 65537.)
a(n) = 3 for n in A000720(A081091) = (4, 5, 6, 8, 12, 13, 19, 21, 25, 32, 33, 44, 98, 106, 116, 136, 174, 191, 310, 313, 319, 565, 568, ...). (End)

T. D. Noe, Table of n, a(n) for n = 1..10000
Tyler Ball and Daniel Juda, Dominance over N, Rose-Hulman Undergraduate Mathematics Journal, Vol. 13, No. 2, Fall 2013.
Christian Elsholtz, Almost all primes have a multiple of small Hamming weight, arXiv:1602.05974 [math.NT], 2016.
Index entries for sequences related to binary expansion of n

Cf. A035103, A035100, A004676, A090455.
Cf. A027697, A027699
Cf. A180024. - Reinhard Zumkeller, Aug 08 2010
Cf. A072084.
Cf. A159611 (indices of 2s), A000720(A081091) (indices of 3s). - M. F. Hasler, Mar 03 2023

a014499 = a000120 . a000040  -- Reinhard Zumkeller, Feb 10 2013

[&+Intseq(NthPrime(n), 2): n in [1..100] ]; // Vincenzo Librandi, Mar 25 2014

Table[Plus @@ IntegerDigits[Prime[n], 2], {n, 1, 100}] (* Vincenzo Librandi, Mar 25 2014 *)

A014499(n)=hammingweight(prime(n)) \\ M. F. Hasler, Nov 20 2009, updated Mar 03 2023

from sympy import prime
def A014499(n): return prime(n).bit_count() # Chai Wah Wu, Mar 22 2023

[sum(i.digits(base=2)) for i in primes_first_n(200)] # Tom Edgar, Mar 25 2014

a(n) = A000120(A000040(n)).
a(A049084(A061712(n))) = n. - Reinhard Zumkeller, Feb 10 2013
a(n) = [x^prime(n)] (1/(1 - x))*Sum_{k>=0} x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Mar 27 2018

A027699 Evil primes: primes with even number of 1's in their binary expansion.

Original entry on oeis.org

3, 5, 17, 23, 29, 43, 53, 71, 83, 89, 101, 113, 139, 149, 163, 197, 257, 263, 269, 277, 281, 293, 311, 317, 337, 347, 349, 353, 359, 373, 383, 389, 401, 449, 461, 467, 479, 503, 509, 523, 547, 571, 593, 599, 619, 643, 673, 683, 691, 739, 751, 773, 797, 811

Offset: 1

N. J. A. Sloane

Comment from Vladimir Shevelev, Jun 01 2007: Conjecture: If pi_1(m) is the number of a(n) not exceeding m and pi_2(m) is the number of A027697(n) not exceeding m then pi_1(m) <= smaller than pi_2(m) for all natural m except m=5 and m=6. I verified this conjecture up to 10^9. Moreover I conjecture that pi_2(m)-pi_1(m) tends to infinity with records at the primes m=2, 13, 41, 61, 67, 79, 109, 131, 137, ...

T. D. Noe, Table of n, a(n) for n = 1..10000
E. Fouvry, C. Mauduit, Sommes des chiffres et nombres presque premiers, (French) [Sums of digits and almost primes] Math. Ann. 305 (1996), no. 3, 571--599. MR1397437 (97k:11029).
V. Shevelev, A conjecture on primes and a step towards justification, arXiv:0706.0786 [math.NT], 2007.

Cf. A027697, A066148, A066149.
Cf. A001969 (evil numbers), A129771 (evil odd numbers)
Cf. A130911 (prime race between evil primes and odious primes).

Select[Prime[Range[200]], EvenQ[Count[IntegerDigits[ #,2],1]]&] (* T. D. Noe, Jun 12 2007 *)

forprime(p=1,999,norml2(binary(p))%2 || print1(p","))

isA027699(p)=isprime(p) && !bittest(norml2(binary(p)),0) \\ M. F. Hasler, Dec 12 2010

from sympy import isprime
def ok(n): return bin(n).count("1")%2 == 0 and isprime(n)
print([k for k in range(812) if ok(k)]) # Michael S. Branicky, Jun 27 2022

More terms from Erich Friedman

A091206 Primes whose binary representation encodes a polynomial irreducible over GF(2).

Original entry on oeis.org

2, 3, 7, 11, 13, 19, 31, 37, 41, 47, 59, 61, 67, 73, 97, 103, 109, 131, 137, 157, 167, 191, 193, 211, 229, 239, 241, 283, 313, 379, 397, 419, 433, 463, 487, 499, 557, 563, 587, 601, 607, 613, 617, 631, 647, 661, 677, 701, 719, 757, 761, 769, 787, 827, 859

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

"Encoded in binary representation" means that a polynomial a(n)*X^n+...+a(0)*X^0 over GF(2) is represented by the binary number a(n)*2^n+...+a(0)*2^0 in Z (where each coefficient a(k) = 0 or 1).

Subsequence with Hamming weight nonprime starts 2, 1019, 1279, 1531, 1663, 1759, 1783, 1789, 2011, 2027, 2543, 2551, ... [Joerg Arndt, Nov 01 2013]. These are now given by A255569. - Antti Karttunen, May 14 2015

Antti Karttunen, Table of n, a(n) for n = 1..10226; all terms up to 1048357, binary length 20
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences related to binary encoded polynomials over GF(2)

Intersection of A014580 and A000040.
Apart from a(2) = 3 a subsequence of A027697. The numbers in A027697 but not here are listed in A238186.
Also subsequence of A235045 (its primes. Cf. also A235041-A235042).
Cf. A091209 (Primes whose binary expansion encodes a polynomial reducible over GF(2)), A091212 (Composite, and reducible over GF(2)), A091214 (Composite, but irreducible over GF(2)), A257688 (either 1, prime or irreducible over GF(2)).
Subsequence: A255569.

okQ[p_] := Module[{id, pol, x}, id = IntegerDigits[p, 2] // Reverse; pol = id.x^Range[0, Length[id] - 1]; IrreduciblePolynomialQ[pol, Modulus -> 2]];
Select[Prime[Range[1000]], okQ] (* Jean-François Alcover, Feb 06 2023 *)

is(n)=polisirreducible( Mod(1,2) * Pol(digits(n,2)) );
forprime(n=2,10^3,if (is(n), print1(n,", ")));
\\ Joerg Arndt, Nov 01 2013

a(n) = A000040(A091207(n)) = A014580(A091208(n)).

cp's OEIS Frontend

A095005 Number of odious primes (A027697) in range ]2^n,2^(n+1)].

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A177798 First primes of record chains of consecutive primes such that all of them are odious (A027697).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A231254 Odious primes p (A027697) such that p^2 and p^3 are evil (A027699).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A360648 Fully multiplicative with a(A027697(k)) = A027699(k) and a(A027699(k)) = A027697(k) for any k > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A131122 Even numbers that are not the sum of an evil prime (A027699) and an odious prime (A027697).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A231253 Terms of A227891 of the form (p*q)^2, where p <= q are odious primes (A027697).

Views

Author

Keywords

Comments

Crossrefs

A000069 Odious numbers: numbers with an odd number of 1's in their binary expansion.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

A014499 Number of 1's in binary representation of n-th prime.

Views

Author

Keywords