login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A261524 Odd numbers n such that degree(gcd( 1 + x^n, 1 + (1+x)^n )) > 1, where the polynomials are over GF(2). 5
3, 7, 9, 15, 21, 27, 31, 33, 35, 39, 45, 49, 51, 57, 63, 69, 73, 75, 77, 81, 85, 87, 91, 93, 99, 105, 111, 117, 119, 123, 127, 129, 133, 135, 141, 147, 153, 155, 159, 161, 165, 171, 175, 177, 183, 189, 195, 201, 203, 207, 213, 217, 219, 225, 231, 237, 243, 245, 249, 255, 259, 261, 267, 273, 279, 285, 287, 291, 297, 301 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

From the Golomb/Lee reference: "Theorem 7 (Welch’s Criterion): For any odd integer t, the irreducible polynomials of primitivity t divide trinomials iff gcd( 1 + x^n, 1 + (1+x)^n ) has degree greater than 1."

All Mersenne numbers (A000225) >= 3 are terms, as all primitive polynomials (over GF(2)) divide some trinomial.

All numbers of the form (2j-1)*(2^k-1); j>=1, k>=2 (A261871), are in the sequence. - Bob Selcoe, Sep 03 2015

From Robert Israel, Sep 03 2015: (Start)

If n is in the sequence, then so is every odd multiple of n, because 1+x^n divides 1+x^(k*n) and 1+(1+x)^n divides 1+(1+x)^(k*n).

The first few members of the sequence that are not multiples of other members are 3, 7, 31, 73, 85, 127, 2047, 3133, 4369, 8191, 11275 (see A261862). (End)

LINKS

Joerg Arndt, Table of n, a(n) for n = 1..23300

Solomon W. Golomb, Pey-Feng Lee, Irreducible Polynomials Which Divide Trinomials over GF(2), IEEE Transactions on Information Theory, vol.53, no.2, pp.768-774 (February-2007).

MAPLE

filter:= proc(n) degree(Gcd(1+x^n, 1+(1+x)^n) mod 2)>1 end proc:

select(filter, [2*i+1 $ i=1..200]); # Robert Israel, Sep 03 2015

MATHEMATICA

okQ[n_] := Exponent[PolynomialGCD[1+x^n, 1+(1+x)^n, Modulus -> 2], x] > 1;

Select[Range[1, 301, 2], okQ] (* Jean-François Alcover, Apr 02 2019 *)

PROG

(PARI) W(n)=my(e=Mod(1, 2)); poldegree(gcd(e*(1+x^n), e*(1+(1+x)^n))) > 1;

forstep(n=1, 301, 2, if( W(n) , print1(n, ", ") ) );

(Sage)

x = polygen(GF(2), 'x')

[n for n in range(1, 10^3, 2) if gcd( 1+x^n, 1+(1+x)^n ).degree() > 1]

# Joerg Arndt, Sep 08 2015

CROSSREFS

Cf. A261871, A261862.

Note that A191131, A261524, A261871, and A282572 are very similar and easily confused with each other.

Sequence in context: A099204 A219608 A070993 * A261871 A191131 A282572

Adjacent sequences:  A261521 A261522 A261523 * A261525 A261526 A261527

KEYWORD

nonn

AUTHOR

Joerg Arndt, Aug 23 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 04:23 EDT 2020. Contains 337264 sequences. (Running on oeis4.)