A186891 Numbers m such that the Stern polynomial B(m,x) is irreducible.

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 121, 125, 127, 131, 133, 137, 139, 143, 145, 149, 151, 157, 161, 163, 167, 169, 173, 175, 179, 181, 185, 191, 193, 197, 199

Offset

1,2

Comments

Ulas and Ulas conjecture that all primes are here. The nonprime m are in A186892. See A186886 for the least number having m prime factors.

From Antti Karttunen, Dec 09 2025: (Start)

Apart from 2 and 3, all terms are congruent to 1 or 5 mod 6 (A007310). That there are no even terms after 2 is because B(2,x) = x and that there are no multiples of 3 after 3 follows because a Stern polynomial B(n,x) is a multiple of B(3,x) = (x+1) if and only if n is a multiple of 3. The proof follows below:

Starting from Stern Polynomial B(1,x) and arranging the polynomials in rows of lengths 2^k, computing them with the recurrence B(2*n,x) = x*B(n,x), B(2n+1,x) = B(n,x) + B(n+1,x), we have:

B(1,x) = 1

B(2,x) = x, B(3,x) = x + 1

B(4,x) = x^2, B(5,x) = 2x + 1, B(6,x) = x^2 + x, B(7,x) = x^2 + x + 1

B(8,x) = x^3, B(9,x) = x^2 + 2x + 1, etc.

Reducing these modulo (x+1), we obtain:

1,

-1, 0,

1, -1, 0, 1,

-1, 0, 1, -1, 0, 1, -1, 0,

...

and by induction it is easy to prove that the repeating pattern 1, -1, 0, 1, -1, 0, 1, -1, 0, ... persists forever. Note how B(2*n,x)%(x+1) = -(B(n,x)%(x+1)), as x%(x+1) = -1 and (x^2)%(x+1) = (-x)%(x+1) = 1, while on the other hand, for odd n, B(2n+1,x)%(x+1) = B(n,x)%(x+1) + B(n+1,x)%(x+1), where % stands for modulo operation. Note that similar induction shows that A002487(n) (which is the sum of coefficients of B(n, x)) is even if and only if n is a multiple of 3, and obviously, when we multiply any polynomial with (x+1), the sum of the coefficients of the product is even. (End)

Links

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Maciej Ulas and Oliwia Ulas, On certain arithmetic properties of Stern polynomials, arXiv:1102.5109 [math.CO], 2011.

Formula

From Antti Karttunen, Mar 21 2017: (Start)

A283992(a(1+n)) = n.

A260443(a(1+n)) = A277318(n). (End)

Mathematica

ps[n_] := ps[n] = If[n<2, n, If[OddQ[n], ps[Quotient[n, 2]] + ps[Quotient[n, 2] + 1], x ps[Quotient[n, 2]]]];
selQ[n_] := IrreduciblePolynomialQ[ps[n]];
Join[{1}, Select[Range[200], selQ]] (* Jean-François Alcover, Nov 02 2018, translated from PARI *)

Prog

(PARI) ps(n)=if(n<2, n, if(n%2, ps(n\2)+ps(n\2+1), 'x*ps(n\2)))
is(n)=polisirreducible(ps(n)) \\ Charles R Greathouse IV, Apr 07 2015

Crossrefs

Cf. A057526 (degree of Stern polynomials), A125184, A260443 (Stern polynomials).

Cf. A186892 (subsequence of nonprime terms).

Cf. A186893 (subsequence for self-reciprocal polynomials).

Other subsequences: A391241, A391337 (terms that are odd semiprimes), A391345 (multiples of 5).

Cf. A389916 (complement), A389917 (odd terms in complement).

Positions of 0 and 1's in A277013, Positions of 1 and 2's in A284011.

Cf. A283991 (characteristic function for terms > 1).

Cf. also A186886, A277190, A277318, A283992, A389912, A389914.

Sequence in context: A261271 A335284 A308966 * A206074 A325559 A257688

Adjacent sequences: A186888 A186889 A186890 * A186892 A186893 A186894

Keyword

nonn

Author

T. D. Noe, Feb 28 2011

Status

approved