A191131 -id:A191131 - cp's OEIS frontend

A191113 Increasing sequence generated by these rules: a(1)=1, and if x is in a then 3x-2 and 4x-2 are in a.

1, 2, 4, 6, 10, 14, 16, 22, 28, 38, 40, 46, 54, 62, 64, 82, 86, 110, 112, 118, 136, 150, 158, 160, 182, 184, 190, 214, 244, 246, 254, 256, 326, 328, 334, 342, 352, 406, 438, 446, 448, 470, 472, 478, 542, 544, 550, 568, 598, 630, 638, 640, 726, 730, 734, 736, 758, 760, 766, 854, 974, 976, 982, 1000, 1014, 1022, 1024, 1054, 1216

Offset: 1

Clark Kimberling, May 27 2011

nonn

This sequence represents a class of sequences generated by rules of the form "a(1)=1, and if x is in a then hx+i and jx+k are in a, where h,i,j,k are integers."  If m>1, at least one of the numbers b(m)=(a(m)-i)/h and c(m)=(a(m)-k)/j is in the set N of natural numbers.  Let d(n) be the n-th b(m) in N, and let e(n) be the n-th c(m) in N.  Note that a is a subsequence of both d and e.  Examples:
A191113: (h,i,j,k)=(3,-2,4,-2); d=A191146, e=A191149
A191114: (h,i,j,k)=(3,-2,4,-1); d=A191151, e=A191121
A191115: (h,i,j,k)=(3,-2,4,0); d=A191113, e=A191154
A191116: (h,i,j,k)=(3,-2,4,1); d=A191155 e=A191129
A191117: (h,i,j,k)=(3,-2,4,2); d=A191157, e=A191158
A191118: (h,i,j,k)=(3,-2,4,3); d=A191114, e=A191138
...
A191119: (h,i,j,k)=(3,-1,4,-3); d=A191120, e=A191163
A191120: (h,i,j,k)=(3,-1,4,-2); d=A191129, e=A191165
A191121: (h,i,j,k)=(3,-1,4,-1); d=A191166, e=A191167
A191122: (h,i,j,k)=(3,-1,4,0); d=A191168, e=A191169
A191123: (h,i,j,k)=(3,-1,4,1); d=A191170, e=A191171
A191124: (h,i,j,k)=(3,-1,4,2); d=A191172, e=A191173
A191125: (h,i,j,k)=(3,-1,4,3); d=A191174, e=A191175
...
A191126: (h,i,j,k)=(3,0,4,-3); d=A191128, e=A191177
A191127: (h,i,j,k)=(3,0,4,-2); d=A191178, e=A191179
A191128: (h,i,j,k)=(3,0,4,-1); d=A191180, e=A191181
A025613: (h,i,j,k)=(3,0,4,0); d=e=A025613
A191129: (h,i,j,k)=(3,0,4,1); d=A191182, e=A191183
A191130: (h,i,j,k)=(3,0,4,2); d=A191184, e=A191185
A191131: (h,i,j,k)=(3,0,4,3); d=A191186, e=A191187
...
A191132: (h,i,j,k)=(3,1,4,-3); d=A191135, e=A191189
A191133: (h,i,j,k)=(3,1,4,-2); d=A191190, e=A191191
A191134: (h,i,j,k)=(3,1,4,-1); d=A191192, e=A191193
A191135: (h,i,j,k)=(3,1,4,0); d=A191136, e=A191195
A191136: (h,i,j,k)=(3,1,4,1); d=A191196, e=A191197
A191137: (h,i,j,k)=(3,1,4,2); d=A191198, e=A191199
A191138: (h,i,j,k)=(3,1,4,3); d=A191200, e=A191201
...
A191139: (h,i,j,k)=(3,2,4,-3); d=A191143, e=A191119
A191140: (h,i,j,k)=(3,2,4,-2); d=A191204, e=A191205
A191141: (h,i,j,k)=(3,2,4,-1); d=A191206, e=A191207
A191142: (h,i,j,k)=(3,2,4,0); d=A191208, e=A191209
A191143: (h,i,j,k)=(3,2,4,1); d=A191210, e=A191136
A191144: (h,i,j,k)=(3,2,4,2); d=A191212, e=A191213
A191145: (h,i,j,k)=(3,2,4,3); d=e=A191145
...
Representative divisibility properties:
if s=A191116, then 2|(s+1), 4|(s+3), and 8|(s+3) for n>1; if s=A191117, then 10|(s+4) for n>1.
For lists of other "rules sequences" see A190803 (h=2 and j=3) and A191106 (h=j=3).

			1 -> 2 -> 4,6 -> 10,14,16,22 ->

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
David Garth and Adam Gouge, Affinely Self-Generating Sets and Morphisms, Journal of Integer Sequences, Article 07.1.5, 10 (2007) 1-13.

Cf. A190803, A191106.

import Data.Set (singleton, deleteFindMin, insert)
a191113 n = a191113_list !! (n-1)
a191113_list = 1 : f (singleton 2)
   where f s = m : (f $ insert (3*m-2) $ insert (4*m-2) s')
             where (m, s') = deleteFindMin s
-- Reinhard Zumkeller, Jun 01 2011

N:= 2000: # to get all terms <= N
S:= {}: agenda:= {1}:
while nops(agenda) > 0 do
  S:= S union agenda;
  agenda:= select(`<=`,map(t -> (3*t-2,4*t-2),agenda) minus S, N)
od:
sort(convert(S,list)); # Robert Israel, Dec 22 2015

h = 3; i = -2; j = 4; k = -2; f = 1; g = 8;
a = Union[Flatten[NestList[{h # + i, j # + k} &, f, g]]]
(* a=A191113; regarding g, see the Mathematica note at A190803 *)
b = (a + 2)/3; c = (a + 2)/4; r = Range[1, 900];
d = Intersection[b, r] (* A191146 *)
e = Intersection[c, r] (* A191149 *)
m = a/2 (* divisibility property *)

a(1)=1, and if x is in a then 3x-2 and 4x-2 are in a; the terms of a are listed in without repetitions, in increasing order.

A282572 Integers that are a product of Mersenne numbers A000225, (i.e., product of numbers of the form 2^n - 1).

Original entry on oeis.org

1, 3, 7, 9, 15, 21, 27, 31, 45, 49, 63, 81, 93, 105, 127, 135, 147, 189, 217, 225, 243, 255, 279, 315, 343, 381, 405, 441, 465, 511, 567, 651, 675, 729, 735, 765, 837, 889, 945, 961, 1023, 1029, 1143, 1215, 1323, 1395, 1519, 1533, 1575, 1701, 1785, 1905, 1953, 2025, 2047, 2187, 2205, 2295, 2401

Offset: 1

Andrew Ivashenko, Feb 18 2017

nonn

Odd orders of finite abelian groups that appear as the group of units in a commutative ring (Chebolu and Lockridge, see A296241). - Jonathan Sondow, Dec 15 2017

Actually, the Chebolu and Lockridge paper states that this sequence gives all odd numbers that are possible numbers of units in a (commutative or non-commutative) ring (Ditor's theorem). Concretely, if k = (2^(e_1)-1)*(2^(e_2)-1)*...(2^(e_r)-1) is a term, let R = (F_2)^s X F_(2^(e_1)) X F_(2^(e_2)) X ... X F_(2^(e_r)) for s >= 0, then the number of units in R is k. - Jianing Song, Dec 23 2021

			63 = 1*3^3*7, 81 = 1*3^4, 93 = 1*3*31, 105 = 1*7*15, 41013 = 1*3^3*7^2*31.

Robert G. Wilson v, Table of n, a(n) for n = 1..10000
Sunil K. Chebolu and Keir Lockridge. How many units can a commutative ring have?, arXiv preprint arXiv:1701.02341 [math.AC], 2017. See Th. 8.

Cf. A000225, A056652, A296241.

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

d:= 15: # for terms < 2^d
N:= 2^d:
S:= {1}:
for m from 2 to d do
  r:= 2^m-1;
  k:= ilog[r](N);
  V:= S;
  for i from 1 to k do
    V:= select(`<`, map(`*`, V, r), N);
    S:= S union V
  od;
od:
sort(convert(S, list)); # Ridouane Oudra, Sep 14 2021

lmt = 2500; a = b = Array[2^# - 1 &, Floor@ Log2@ lmt]; k = 2; While[k < Length@ a, e = 1; While[e < Floor@ Log[ a[[k]], lmt], b = Union@ Join[b, Select[ a[[k]]^e*b, # < 1 + lmt &]]; e++]; k++]; b (* Robert G. Wilson v, Feb 23 2017 *)

forstep(x=1,1000000,2, t=x; forstep(n=20,2,-1, m=2^n-1; while(t%m==0, t=t\m)); if(t==1, print1(x,","))) \\ Dmitry Petukhov, Feb 23 2017

More terms from Michel Marcus, Feb 23 2017

Definition changed by David A. Corneth, Mar 12 2017

A261524 Odd numbers n such that degree(gcd( 1 + x^n, 1 + (1+x)^n )) > 1, where the polynomials are over GF(2).

Original entry on oeis.org

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

Offset: 1

Joerg Arndt, Aug 23 2015

nonn

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)
From Jianing Song, Oct 13 2023: (Start)
Also odd numbers n such that degree(gcd( 1 + x^n, 1 + (1+x)^n )) > 0. This is because degree(gcd( 1 + x^n, 1 + (1+x)^n )) cannot be 1 since gcd( 1 + x^n, 1 + (1+x)^n ) is divisible by neither x nor x+1.
In general, let p be a prime, gcd(m,p) = 1, q > 1 be a power of p that is congruent to 1 modulo m. In the finite field F_q, the roots to x^m-1 are the nonzero ((q-1)/m)-th powers, so gcd(x^m-1, (x+1)^m-1) != 1 if and only if there are two nonzero ((q-1)/m)-th powers in F_q that differ by 1. If we homogenize, this is equivalent to x^((q-1)/m) + y^((q-1)/m) = z^((q-1)/m) having solutions in (F_q)* (dehomogenize by setting y = 1).
Let p be a prime, gcd(m,p) = 1. Suppose that q > 1 is the smallest power of p that is congruent to 1 modulo m, then gcd(x^m-1, (x+1)^m-1) != 1 in F_p[x] if m > q^(3/4): set k = (q-1)/m and A_1, A_2 both be the set of nonzero ((q-1)/m)-th powers in F_q (so |A_1| = |A_2| = m). Let N be the number of solutions to x^((q-1)/m) + y^((q-1)/m) = z^((q-1)/m) has solutions in (F_q)*, then by Theorem 7.1 of the László Babai link, we have N > m^2*(q-1)/q - (q-1)*sqrt(q) >= 0.
In particular, let p and r be distinct primes, r >= 5, t >= 1. Let Zs(d,p,1) is the d-th Zsigmondy number with parameters (p,1), then gcd(x^(Zs(r^t,p,1))-1, (x+1)^(Zs(r^t,p,1))-1) != 1 in F_p[x]. This is because for d != 2, Zs(d,p,1) = Phi_d(p)/r if d is of the form r^{t'}*ord(p,r) and Phi_d(p) otherwise (see A323748), where ord(a,k) is the multiplicative order of a modulo k, Phi_d(x) is the d-th cyclotomic polynomial. Here d = r^t, so Zs(d,p,1) = Phi_d(p)/r if p == 1 (mod r), Phi_d(p) otherwise. Note that Phi_{r^t}(p) = 1 + p^(r^(t-1)) + p^(2*r^(t-1)) + ... + p^((r-1)*r^(t-1)) > q^(3/4) = p^(3/4*r^t) since r >= 5. It is easy to show that Zs(p^r,p,1) <= q^(3/4) can only happen with r = 5, p == 1 (mod 5) and p <= 601, then we can check that gcd(x^(Zs(r^t,p,1))-1, (x+1)^(Zs(r^t,p,1))-1) = gcd(x^((p^4+p^3+p^2+p+1)/5)-1, (x+1)^((p^4+p^3+p^2+p+1)/5)-1) != 1 in F_p[x] in this case.
For another example, m = (2^(2^t)+1)*(2^(2^(t+1))+1) is a term of this sequence for all t >= 0, since in the case we have q = 2^(2^(t+2)), so m = q^(3/4) + 2^(2^(t+1)) + 2^(2^t) > q^(3/4).
Conjecture 1: Zs(d,2,1) is a term if and only if d is odd and d != 1, 15, 21. Verified for odd numbers up to 91.
Conjecture 2: for a prime p >= 3, gcd(x^(Zs(d,p,1))-1, (x+1)^(Zs(d,p,1))-1) != 1 if and only if d is an odd prime power > 1 other than (d,p) = (7,3), (7,9), (13,3), (37,3), (43,3), (79,3).
Note that the comment above shows that both conjectures are true for powers > 1 of a prime r >= 5. (End)

Joerg Arndt, Table of n, a(n) for n = 1..23300
László Babai, The Fourier Transform and Equations over Finite Abelian Groups, Department of Computer Science, University of Chicago.
Solomon W. Golomb and 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).

Cf. A261871, A261862.

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

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

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 *)

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,", ") ) );

isA261524(n,p=2) = my(d=znorder(Mod(p,n)), c=ffgen(p^d,'c), g=ffprimroot(c)); forstep(e=0, p^d-2, (p^d-1)/n, if((g^e+1)^n==1, return(1))); return(0) \\ Jianing Song, Oct 14 2023, based on the equivalence of gcd(x^m-1, (x+1)^m-1) != 1 and two ((q-1)/m)-th powers in F_q differing by 1 (see Comments)

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

A261871 Numbers of the form (2j-1)(2^k-1); j>=1, k>=2.

Original entry on oeis.org

3, 7, 9, 15, 21, 27, 31, 33, 35, 39, 45, 49, 51, 57, 63, 69, 75, 77, 81, 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

Offset: 1

Bob Selcoe, Sep 04 2015

Odd numbers complementary to A185208.

Lim_{n->inf.} a(n)/n > 6/(1 + Sum_{j>=1} (2/(2^(2j+1)-1))) ~ 4.375745.

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

Cf. A185208.

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

lmt = 310; Take[ Union@ Flatten@ Table[ (2j - 1)(2^k - 1), {j, lmt/4}, {k, 2, 1 + Log2[ lmt/(2j)] }], 68] (* Michael De Vlieger, Sep 04 2015 *) (* and modified by Robert G. Wilson v, Sep 05 2015 *)

list(lim)=my(v=List(),t); for(k=2,logint(lim\1+1,2), t=2^k-1; forstep(j=1,lim\t,2, listput(v,t*j))); Set(v) \\ Charles R Greathouse IV, Sep 05 2015

2n < a(n) < 5n. For n > 51, 4.3n < a(n) < 4.5n. - Charles R Greathouse IV, Sep 05 2015

cp's OEIS Frontend

A191186 Integers in (A191131)/3; contains A191131 as a proper subsequence.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A191187 Integers in (-3+A191131)/4; contains A191131 as a proper subsequence.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A191113 Increasing sequence generated by these rules: a(1)=1, and if x is in a then 3x-2 and 4x-2 are in a.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A282572 Integers that are a product of Mersenne numbers A000225, (i.e., product of numbers of the form 2^n - 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A261524 Odd numbers n such that degree(gcd( 1 + x^n, 1 + (1+x)^n )) > 1, where the polynomials are over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

A261871 Numbers of the form (2*j-1)*(2^k-1); j>=1, k>=2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A191184 Integers in (A191130)/3; contains A191130 as a proper subsequence.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A261871 Numbers of the form (2j-1)(2^k-1); j>=1, k>=2.