A046932 -id:A046932 - cp's OEIS frontend

A055061 LCM of (2^d - 1) where d runs over the degrees of irreducible factors of x^n + x + 1 over GF(2), divided by A046932(n).

1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 15, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 15, 1, 99, 1, 1, 31, 21, 7, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 17, 1, 3, 1, 1, 1, 19, 1, 1, 1, 1, 1, 3, 1, 1, 1, 63, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 5, 3, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 3, 5, 1, 1, 1, 1, 1, 91, 127, 7

Offset: 2

N. J. A. Sloane, Jun 11 2000

nonn

Max Alekseyev, Table of n, a(n) for n = 2..1223
L. Bartholdi, Lamps, factorizations and finite fields, Amer. Math. Monthly, 107 (No. 5, 2000), 429-436.

Cf. A046932.

Edited and extended by Max Alekseyev, Oct 19 2011

b-file extended by Max Alekseyev, Aug 17 2015

A181046 Indices of records in A046932: numbers n such that A046932(n)>A046932(k) for all k

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 18, 19, 20, 22, 25, 27, 29, 35, 36, 37, 39, 40, 41, 42, 43, 44, 46, 48, 50, 53, 54, 56, 57, 58, 60, 63, 67, 72, 74, 76, 81, 87, 90, 91, 93, 95, 96, 97, 100, 103, 109, 110, 113, 114, 116, 119, 120, 122, 123, 124, 125, 127, 131, 132

Offset: 1

Ben Branman, Sep 30 2010

nonn

			A046932(10)=889, which is greater than A046932(1), A046932(2), etc, so 10 is part of the sequence.
On the other hand, A046932(8)=63, which is less than A046932(7)=127, so 8 is not part of the sequence.

Max Alekseyev, Table of n, a(n) for n = 1..324

Cf. A046932.

More terms with the aid of b046932.txt by R. J. Mathar, Oct 09 2010

Terms a(68) onward in b-file from Max Alekseyev, Aug 17 2015

A038553 Maximum cycle length in differentiation digraph for n-bit binary sequences.

Original entry on oeis.org

1, 1, 3, 1, 15, 6, 7, 1, 63, 30, 341, 12, 819, 14, 15, 1, 255, 126, 9709, 60, 63, 682, 2047, 24, 25575, 1638, 13797, 28, 475107, 30, 31, 1, 1023, 510, 4095, 252, 3233097, 19418, 4095, 120, 41943, 126, 5461, 1364, 4095, 4094, 8388607, 48, 2097151, 51150, 255, 3276, 3556769739, 27594, 1048575

Offset: 1

N. J. A. Sloane

nonn

Length of longest cycle for vectors of length n under the Ducci map.
Also, the period of polynomial (x+1)^n+1 over GF(2) (cf. A046932). - Max Alekseyev, Oct 12 2013
Per the comment by T. D. Noe originally given in A138006, it appears that for an odd n > 1, a(n) <= n*(2^((n-1)/2)-1). - Max Alekseyev, Jul 10 2025

Simmons, G. J., The structure of the differentiation digraphs of binary sequences. Ars Combin. 35 (1993), A, 71-88. Math. Rev. 95f:05052.

Max Alekseyev, Table of n, a(n) for n = 1..2458
Florian Breuer, Igor E. Shparlinski, Lower bounds for periods of Ducci sequences, arXiv:1909.04462 [math.NT], 2019.
N. J. Calkin, J. G. Stevens, D. M. Thomas, A characterization for the lengths of cycles of the n-number Ducci game, Fib. Q., 43 (No. 1, 2005), 53-59.
O. N. Karpenkov, On examples of difference operators for {0,1}-valued functions over finite sets, Funct. Anal. Other Math. 1 (2006), 175-180. [Gives incorrect value 4095 for a(46).]

Cf. A111944, A135547, A136043, A119513.

It appears that whenever b(n) = log2(a(n)/n + 1) is an integer and n > 1, b(n) = A119513(n) = A136043(n). - Andrei Zabolotskii, Jul 28 2025

Entry revised by N. J. A. Sloane, Jun 19 2006, Feb 24 2008
a(46) corrected, terms a(51) onward and b-file added by Max Alekseyev, Oct 12 2013
b-file extended by Max Alekseyev, Sep 24 2019

A088863 Number of prime factors of n-th Mersenne number M(p_n).

Original entry on oeis.org

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

Offset: 1

Jeppe Stig Nielsen, Nov 25 2003

nonn

			a(5)=2 because M(p_5)=M(11)=2047 has 2 (not necessarily distinct) prime factors.

Max Alekseyev, Table of n, a(n) for n = 1..197 (first 137 terms from Herman Jamke)
Herman Jamke, The first 137 terms in detail

Cf. A001348, A003260, A046051, A046932.

seq(nops(ifactor(2^ithprime(n)-1)),n=1..32); # Emeric Deutsch, Dec 23 2004

Do[m = 2^Prime[n] - 1; Print[Plus @@ Last /@ FactorInteger[m]], {n, 1, 50}] (* Ryan Propper, Jul 31 2005 *)

for(n=1,137,print1(bigomega(2^prime(n)-1)",")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 28 2007

a(n) = A001222(A001348(n)) = A001222(A000225(A000040(n))).

14 more terms from Emeric Deutsch, Dec 23 2004
More terms from Ryan Propper, Jul 31 2005
More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 28 2007

A073639 Numbers k such that x^k + x + 1 is a primitive polynomial modulo 2.

Original entry on oeis.org

2, 3, 4, 6, 7, 15, 22, 60, 63, 127, 153, 471, 532, 865, 900, 1366

Offset: 1

Richard P. Brent and Paul Zimmermann, Sep 05 2002

Subsequence of A002475, which gives k for which the polynomial x^k + x + 1 is irreducible modulo 2. Term m of A002475 belongs to this sequence iff A046932(m) = 2^m - 1.
Note that a(16) = 1366 = A002475(23). For k = A002475(24) and A002475(25), polynomial x^k + x + 1 is not primitive modulo 2, so a(17) >= A002475(26) = 4495.
The following large terms of A002475 do not belong here: 53484, 62481, 83406, 103468. - Max Alekseyev, Aug 18 2015

Joerg Arndt, Matters Computational (The Fxtbook), section 40.9.3 "Irreducible trinomials of the form 1 + x^k + x^d", p.850
I. F. Blake, S. Gao and R. J. Lambert, Constructive problems for irreducible polynomials over finite fields, in Information Theory and Applications, LNCS 793, Springer-Verlag, Berlin, 1994, 1-23, See Table 2.
R. P. Brent, Searching for primitive trinomials (mod 2)
R. P. Brent, S. Larvala and P. Zimmermann, A fast algorithm for testing reducibility of trinomials ..., Math. Comp. 72 (2003), 1443-1452.
N. Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 1969 67-69.
N. Zierler, On x^n+x+1 over GF(2), Information and Control 16 1970 502-505.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), Information and Control 13 1968 541-554.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), II, Information and Control 14 1969 566-569.
Index entries for sequences related to trinomials over GF(2)

Cf. A002475, A073571, A057486.

Select[Range[2, 1000], PrimitivePolynomialQ[x^# + x + 1, 2] &] (* Robert Price, Sep 19 2018 *)

A100730 Fundamental difference of Ulam 1-additive sequence starting U(2,2n+1).

Original entry on oeis.org

126, 126, 1778, 6510, 23622, 510, 507842, 1523526, 8388606, 4194302, 597870, 35791394, 21691754, 2046, 511305630, 45678505642, 51539607546, 640638112422, 2748779069430, 25563645345606, 46912496118442, 80418967640942

Offset: 2

Ralf Stephan, Dec 03 2004

nonn

Max Alekseyev, Table of n, a(n) for n = 2..610
M. Akeran, On some 1-additive sequences
S. R. Finch, Patterns in 1-additive sequences, Experimental Mathematics 1 (1992), 57-63.

Cf. A100729 for the period, A001857 for U(2, 3), A007300 for U(2, 5), A003668 for U(2, 7).

a(n) = 2 * A046932(2*n+2)

2 more terms from Balakrishnan V (balaji.iitm1(AT)gmail.com), Nov 15 2007
Further new terms and b-file from Max Alekseyev, Dec 01 2007
b-file extended by Max Alekseyev, Aug 17 2015

A281922 Consider a string of n 1. From left to right for any couple of consecutive numbers apply the transform 11 -> 10, 10 -> 11, 00 -> 00, 01 -> 01. At any further step restart the process considering the value of the rightmost digit as input to the leftmost one to apply the transform again. Sequence gives the number of steps necessary to reach again a string of n 1 or -1 if such a number does not exist.

Original entry on oeis.org

2, 5, 4, 17, -1, 109, 8, 65, 89, 1115, -1, 7297, 2531, 4369, 16, 257, 155174, 195814, 495146, 5201, 1334551, 1725452, 1485482, -1, -1, -1, 17256565, 277691849, 6145997, 2029501, 32, 1025, 67672804, 1157011598, 12054050100, 22287270331, 15597512810, -1

Offset: 2

Paolo P. Lava, Feb 15 2017

a(n) <= 2^n if it exists.
a(2^k) = 2^k.
a(2^k + 1) = 2^(2*k) + 1.
Up to a(34), it appears that if the number does not exist the configuration of the first step is repeated further on: for a(6) it happens after 22 steps (see example), 1086 for a(12), 2192338 for a(25), 22996 for a(26), 41943036 for a(27).

			a(5) = 17. We start with 1 1 1 1 1, then the first two digit at left are 1 1 and applying the transform we get 1 0 1 1 1; again, the second and third digit from left are 0 1 and applying the transform we get 1 0 1 1 1;  the third and fourth digit from left are 1 1 and we get 1 0 1 0 1; the fourth and fifth digit from left are 0 1 and we get 1 0 1 0 1. This is the result of the first step. To start the second one we consider the rightmost digit of the first step, that is 1, as input of the leftmost digit, that is another 1. So, applying the transform 1 1 -> 1 0, we get 0 0 1 0 1; now the first and second digit at left are 0 0 that results in 0 0 1 0 1; the second and third digit at left are 0 1 that results in 0 0 1 0 1; the third and fourth digit at left are 1 0 that results in 0 0 1 1 1; the fourth and fifth digit from left are 1 1 that results in 0 0 1 1 0. This is the result of the second step. Here below the list of all the steps leading back to 1 1 1 1 1:
0    1 1 1 1 1
1    1 0 1 0 1
2    0 0 1 1 0
3    0 0 1 0 0
4    0 0 1 1 1
5    1 1 0 1 0
6    1 0 0 1 1
7    0 0 0 1 0
8    0 0 0 1 1
9    1 1 1 0 1
10   0 1 0 0 1
11   1 0 0 0 1
12   0 0 0 0 1
13   1 1 1 1 0
14   1 0 1 0 0
15   1 1 0 0 0
16   1 0 0 0 0
17   1 1 1 1 1
a(6) = -1 because after 22 steps we get again 1 0 1 0 1 0 (first step):
0    1 1 1 1 1 1
1    1 0 1 0 1 0
2    1 1 0 0 1 1
3    0 1 1 1 0 1
4    1 0 1 0 0 1
5    0 0 1 1 1 0
6    0 0 1 0 1 1
7    1 1 0 0 1 0
8    1 0 0 0 1 1
9    0 0 0 0 1 0
10   0 0 0 0 1 1
11   1 1 1 1 0 1
12   0 1 0 1 1 0
13   0 1 1 0 1 1
14   1 0 1 1 0 1
15   0 0 1 0 0 1
16   1 1 0 0 0 1
17   0 1 1 1 1 0
18   0 1 0 1 0 0
19   0 1 1 0 0 0
20   0 1 0 0 0 0
21   0 1 1 1 1 1
22   1 0 1 0 1 0

Lars Blomberg, Table of n, a(n) for n = 2..42

Cf. A046932.

with(numtheory): P:=proc(q) local a,b,j,k,n,ok,ok2,s,t;
for n from 2 to q do a:=array(1..n); b:=array(1..n);
for k from 1 to n do a[k]:=1; if k mod 2=0 then b[k]:=0; else b[k]:=1; fi; od;
for k from 1 to n-1 do if a[k]=1 then a[k+1]:=(a[k+1]+1) mod 2; fi; od;
t:=1; ok:=1; s:=0; while n>s do t:=t+1; if a[n]=1 then a[1]:=(a[1]+1) mod 2; fi;
for k from 1 to n-1 do if a[k]=1 then a[k+1]:=(a[k+1]+1) mod 2; fi; od;
ok2:=1; for j from 1 to n do if a[j]<>b[j] then ok2:=0; break; fi; s:=add(a[k],k=1..n); od;
if ok2=1 then ok:=0; print(-1); break; fi; od; if ok=1 then print(t); fi; od; end: P(100);

a(35)-a(39) from Lars Blomberg, Apr 20 2017

cp's OEIS Frontend

A055061 LCM of (2^d - 1) where d runs over the degrees of irreducible factors of x^n + x + 1 over GF(2), divided by A046932(n).

Views

Author

Keywords

Links

Crossrefs

Extensions

A181046 Indices of records in A046932: numbers n such that A046932(n)>A046932(k) for all k

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A038553 Maximum cycle length in differentiation digraph for n-bit binary sequences.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A088863 Number of prime factors of n-th Mersenne number M(p_n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A073639 Numbers k such that x^k + x + 1 is a primitive polynomial modulo 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A100730 Fundamental difference of Ulam 1-additive sequence starting U(2,2n+1).

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions