A100730 -id:A100730 - cp's OEIS frontend

A135737 Ulam type (1-additive) sequences u[1]=2, u[2]=2n+1, u[k+1] is least unique sum u[i]+u[j]>u[k], 1<=i

2, 3, 2, 5, 5, 2, 7, 7, 7, 2, 8, 9, 9, 9, 2, 9, 11, 11, 11, 11, 2, 13, 12, 13, 13, 13, 13, 2, 14, 13, 15, 15, 15, 15, 15, 2, 18, 15, 16, 17, 17, 17, 17, 17, 2, 19, 19, 17, 19, 19, 19, 19, 19, 19, 2, 24, 23, 19, 20, 21, 21, 21, 21, 21, 21, 2, 25, 27, 21, 21, 23, 23, 23, 23, 23, 23, 23

Offset: 1

M. F. Hasler, Nov 26 2007

Any of the sequences u=U(2,2n+1) has u[1]=2 and u[n+4]=4n+4; in between these there are the odd numbers 2n+1,...,4n-3. For n>1 there are no other even terms and the sequence of first differences becomes periodic for k>=t (transient phase), such that u[k] = u[k-floor((k-t)/p)*p] + floor((k-t)/p)*d, where p is the period (cf. A100729) and d the fundamental difference (cf. A100730). See the cross-references, especially A002858, for more information.

			The sequence contains the terms of the table T[n,k] = U(2,2n+1)[k], read by antidiagonals: a[1]=T[1,1]=2, a[2]=T[1,2]=3, a[3]=T[2,1]=2, a[4]=T[1,3]=5,...
n=1: U(2,3)= 2, 3, 5, 7, 8, 9,13,14...
n=2: U(2,5)= 2, 5, 7, 9,11,12,...
n=3: U(2,7)= 2, 7, 9,11,13,...
n=4: U(2,9)= 2, 9,11,...

M. F. Hasler, Table of n, a(n) for n = 1..1000, Apr 10 2025
Project Euler, Problem 167: Investigating Ulam sequences

Cf. A001857 = U(2, 3) = row 1, A007300 = U(2, 5) = row 2, A003668 = U(2, 7) = row 3; A100729-A100730 (period).
Cf. A002858 = U(1, 2): this would be row 0, with u[1], u[2] exchanged.
See also: A002859 = U(1, 3), A003666 = U(1, 4), A003667 = U(1, 5).

ulam(a,b,Nmax=30,i)=a=[a,b]; b=[a[1]+b]; for( k=3,Nmax, i=1; while(( i<#b && b[i]==b[i+1] && i+=2 ) || ( i>1 && b[i]==b[i-1] && i++),); a=concat(a,b[i]); b=vecsort(concat(vecextract(b,Str("^..",i)),vector(k-1,j,a[k]+a[j]))); i=0; for(j=1,#b-2, if( b[j]==b[j+2], i+=1<A135737(Nmax=100)=local(T=vector(sqrtint(Nmax*2)+1,n, ulam(2,2*n+1, sqrtint(Nmax*2)+2-n)),i,j); vector(Nmax,k,if(j>1,T[i++ ][j-- ],j=i+1;T[i=1][j]))

A046932 a(n) = period of x^n + x + 1 over GF(2), i.e., the smallest integer m>0 such that x^n + x + 1 divides x^m + 1 over GF(2).

Original entry on oeis.org

1, 3, 7, 15, 21, 63, 127, 63, 73, 889, 1533, 3255, 7905, 11811, 32767, 255, 273, 253921, 413385, 761763, 5461, 4194303, 2088705, 2097151, 10961685, 298935, 125829105, 17895697, 402653181, 10845877, 2097151, 1023, 1057, 255652815, 3681400539

Offset: 1

Russell Walsmith

Also, the multiplicative order of x modulo the polynomial x^n + x + 1 (or its reciprocal x^n + x^(n-1) + 1) over GF(2).
For n>1, let S_0 = 11...1 (n times) and S_{i+1} be formed by applying D to last n bits of S_i and appending result to S_i, where D is the first difference modulo 2 (e.g., a,b,c,d,e -> a+b,b+c,c+d,d+e). The period of the resulting infinite string is a(n). E.g., n=4 produces 1111000100110101111..., so a(4) = 15.
Also, the sequence can be constructed in the same way as A112683, but using the recurrence x(i) = 2*x(i-1)^2 + 2*x(i-1) + 2*x(i-n)^2 + 2*x(i-n) mod 3.
From Ben Branman, Aug 12 2010: (Start)
Additionally, the pseudorandom binary sequence determined by the recursion
If xn, f(x)=f(x-1) XOR f(x-n).
The resulting sequence f(x) has period a(n).
For example, if n=4, then the sequence f(x) is has period 15: 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0
so a(4)=15. (End)

Max Alekseyev, Table of n, a(n) for n = 1..1223
Tej Bade, Kelly Cui, Antoine Labelle, and Deyuan Li, Ulam Sets in New Settings, arXiv:2008.02762 [math.CO], 2020. See also Integers (2020) Vol. 20, #A102.
L. Bartholdi, Lamps, Factorizations and Finite Fields, arXiv:math/9910056 [math.CO], 1999; Amer. Math. Monthly (2000), 107(5), 429-436.
Steven R. Finch, Periodicity in Sequences Mod 3 [Broken link]
Steven R. Finch, Periodicity in Sequences Mod 3 [From the Wayback machine]
International Math Olympiad, Problem 6, 1993.
Index entries for sequences related to trinomials over GF(2)

Cf. A010760, A055061, A073639, A100730, A112683.

(* This program is not suitable to compute a large number of terms. *)
a[n_] := Module[{f, ff}, f[x_] := f[x] = If[xJean-François Alcover, Sep 10 2018, after Ben Branman *)

a(n) = {pola = Mod(1,2)*(x^n+x+1); m=1; ok = 0; until (ok, polb = Mod(1,2)*(x^m+1); if (type(polb/pola) == "t_POL", ok = 1; break;); if (!ok, m++);); return (m);} \\ Michel Marcus, May 20 2013

a(2^k) = 2^(2*k) - 1.
a(2^k + 1) = 2^(2*k) + 2^k + 1.
Conjecture: a(2^k - 1) = 2^a(k) - 1. [See Bartholdi, 2000]
More general conjecture: a( (2^(k*m) - 1) / (2^m-1) ) = (2^(a(k)*m) - 1) / (2^m-1). For m=1, it would imply Bartholdi conjecture. - Max Alekseyev, Oct 21 2011

More terms from Dean Hickerson
Entry revised and b-file supplied by Max Alekseyev, Mar 14 2008
b-file extended by Max Alekseyev, Nov 15 2014; Aug 17 2015

A100729 Period of the first difference of Ulam 1-additive sequence U(2,2n+1).

Original entry on oeis.org

32, 26, 444, 1628, 5906, 80, 126960, 380882, 2097152, 1047588, 148814, 8951040, 5406720, 242, 127842440, 11419626400, 12885001946, 160159528116, 687195466408, 6390911336402, 11728121233408, 20104735604736

Offset: 2

Ralf Stephan, Dec 03 2004

nonn

It was proved by Akeran that a(2^k-1) = 3^(k+1) - 1.

Note that a(n)=2^(2n+1) as soon as A100730(n)=2^(2n+3)-2, that happens for n=(m-2)/2 with m>=6 being an even element of A073639.

			For k=2, we have a(3)=3^3-1=26.

Max Alekseyev, Table of n, a(n) for n = 2..31
M. Akeran, On some 1-additive sequences
J. Cassaigne and S. R. Finch, A class of 1-additive sequences and additive recurrences
S. R. Finch, Patterns in 1-additive sequences, Experimental Mathematics 1 (1992), 57-63.

Cf. A100730 for the fundamental difference, A001857 for U(2, 3), A007300 for U(2, 5), A003668 for U(2, 7).

Cf. also A006844.

a(3) corrected from 25 to 26 by Hugo van der Sanden and Bertram Felgenhauer (int-e(AT)gmx.de), Nov 11 2007
More terms from Balakrishnan V (balaji.iitm1(AT)gmail.com), Nov 15 2007
a(21..31) and b-file from Max Alekseyev, Dec 01 2007

A133485 Integers k such that the polynomial x^(2k+2) + x + 1 is primitive and irreducible over GF(2).

Original entry on oeis.org

0, 1, 2, 10, 29, 265, 449, 682

Offset: 1

Max Alekseyev, Dec 02 2007, Feb 15 2008

An integer k > 1 belongs to this sequence iff A100730(k) = 2^(2k+3) - 2.
Also, an integer k belongs to this sequence iff 2k+2 belongs to A073639.
The polynomial x^(2k+2) + x + 1 in the definition can be replaced by its reciprocal x^(2k+2) + x^(2k+1) + 1.
(2*a(n)+2) is a subsequence of A002475. - Manfred Scheucher, Aug 17 2015
a(9) >= (A002475(29) - 2)/2 = 5098.

Cf. A002475, A073639, A100730.

select(n -> (Irreduc(x^(2*n+2)+x+1) mod 2) and (Primitive(x^(2*n+2)+x+1) mod 2), [$0..500]); # Robert Israel, Aug 17 2015

polisprimitive(poli)=np = 2^poldegree(poli)-1; if (type((x^np-1)/poli) != "t_POL", return (0)); forstep(k=np-1, 1, -1, if (type((x^k-1)/poli) == "t_POL", return (0));); return(1);
lista(nn) = {for (n=0, nn, poli = Mod(1,2)*(x^(2*n+2)+x+1); if (polisirreducible(poli) && polisprimitive(poli), print1(n, ", ")););} \\ Michel Marcus, May 27 2013

def is_primitive(p):
    d = 2^(p.degree())-1
    if not p.divides(x^d-1): return False
    for k in (d//q for q in d.prime_factors()):
        if p.divides(x^k-1): return False
    return True
P. = GF(2)[]
for n in range(1,1000):
    p = x^(2*n+2)+x+1
    if p.is_irreducible() and is_primitive(p):
        print(n)
# Modification of the A002475 Script by Ruperto Corso
# Manfred Scheucher, Aug 17 2015

a(2)=1 inserted by Michel Marcus, May 29 2013

cp's OEIS Frontend

A135737 Ulam type (1-additive) sequences u[1]=2, u[2]=2n+1, u[k+1] is least unique sum u[i]+u[j]>u[k], 1<=i

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A046932 a(n) = period of x^n + x + 1 over GF(2), i.e., the smallest integer m>0 such that x^n + x + 1 divides x^m + 1 over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A100729 Period of the first difference of Ulam 1-additive sequence U(2,2n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A133485 Integers k such that the polynomial x^(2k+2) + x + 1 is primitive and irreducible over GF(2).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

PARI

Sage

Extensions