A282572 -id:A282572 - cp's OEIS frontend

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

1, 3, 7, 9, 15, 21, 27, 31, 39, 45, 63, 81, 87, 93, 111, 117, 127, 135, 159, 183, 189, 243, 255, 261, 279, 327, 333, 351, 375, 381, 405, 447, 471, 477, 511, 543, 549, 567, 639, 729, 735, 759, 765, 783, 837, 975, 981, 999, 1023, 1047, 1053, 1119, 1125, 1143, 1215, 1311, 1335, 1341, 1407, 1413, 1431, 1503, 1527, 1533, 1623

Offset: 1

Clark Kimberling, May 27 2011

nonn

See A191113.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A191113, A191186, A191187.

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

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

h = 3; i = 0; j = 4; k = 3; f = 1; g = 9;
a = Union[Flatten[NestList[{h # + i, j # + k} &, f, g]]]   (* A191131 *)
b = a/3; c = (a - 3)/4; r = Range[1, 1500];
d = Intersection[b, r] (* A191186 *)
e = Intersection[c, r] (* A191187 *)

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

A363329 a(n) is the number of divisors of n that are both coreful and infinitary.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Amiram Eldar, May 28 2023

For the definition of a coreful divisor see A307958, and for the definition of an infinitary divisor see A037445.
If e > 0 is the exponent of the highest power of p dividing n (where p is a prime), then for each divisor d of n that is both a coreful and an infinitary divisor, the exponent of the highest power of p dividing d is a number k >= 1 such that the bitwise AND of e and k is equal to k.
The least term that does not equal 1 or 3 is a(128) = 7.
The range of this sequence is A282572.

			a(8) = 3 since 8 has 4 divisors, 1, 2, 4 and 8, all are infinitary and 3 of them (2, 4 and 8) are also coreful.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000120, A005361 (number of coreful divisors), A007947, A037445, A077609, A138302, A282572, A359411.

f[p_, e_] := 2^DigitCount[e, 2, 1] - 1; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = factorback(apply(x -> 2^hammingweight(x) - 1, factor(n)[, 2]));

from math import prod
from sympy import factorint
def A363329(n): return prod((1<Chai Wah Wu, Sep 01 2023

Multiplicative with a(p^e) = 2^A000120(e) - 1.
a(n) = 1 is and only if n is in A138302.
a(n) >= A359411(n).
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = Product_{p prime} (-1/p + (1-1/p)*Product_{k>=0} (1 + 2/p^(2^k))) = 1.29926464312956239535... .

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

A070932 Possible number of units in a finite (commutative or non-commutative) ring.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 31, 32, 36, 40, 42, 44, 45, 46, 48, 49, 52, 54, 56, 58, 60, 62, 63, 64, 66, 70, 72, 78, 80, 81, 82, 84, 88, 90, 92, 93, 96, 98, 100

Offset: 1

Sharon Sela (sharonsela(AT)hotmail.com), May 24 2002

This is a list of the numbers of units in R where R ranges over all finite commutative or non-commutative rings.
By considering the ring Z_n and the finite fields GF(q) this sequence contains the values of the Euler function phi(n) (A000010) and prime powers - 1 (A181062). By taking direct product of rings, if n and m belong to the sequence then so does m*n.
Eric M. Rains has shown that these rules generate all terms of this sequence. More precisely, he shows this sequence (with 0 removed) is the multiplicative monoid generated by all numbers of the form q^n-q^{n-1} for n >= 1 and q a prime power (see Rains link).
Since the number of units of F_q[X]/(X^n) is q^n - q^(n-1), restricting to finite commutative rings gives the same sequence. A296241, which is a proper supersequence, allows the ring R to be infinite. - Jianing Song, Dec 24 2021

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
E. M. Rains, Comments on A070932

Cf. A000010, A002202, A000252, A000961, A181062, A221178.
A000252 is a subsequence.
A282572 is the subsequence of odd terms.
Proper subsequence of A296241.
The main entries concerned with the enumeration of rings are A027623, A037234, A037291, A037289, A038538, A186116.

max = 100; A000010 = EulerPhi[ Range[2*max]] // Union // Select[#, # <= max &] &; A181062 = Select[ Range[max], Length[ FactorInteger[#]] == 1 &] - 1; FixedPoint[ Select[ Outer[ Times, #, # ] // Flatten // Union, # <= max &] &, Union[A000010, A181062] ] (* Jean-François Alcover, Sep 10 2013 *)

list(lim)=my(P=1, q, v, u=List()); forprime(p=2, default(primelimit), if(eulerphi(P*=p)>=lim, q=p; break)); v=vecsort(vector(P/q*lim\eulerphi(P/q), k, eulerphi(k)), , 8); v=select(n->n<=lim, v); forprime(p=2, sqrtint(lim\1+1), P=p; while((P*=p) <= lim+1, listput(u, P-1))); v=vecsort(concat(v, Vec(u)), , 8); u=List([0]); while(#u, v=vecsort(concat(v, Vec(u)),,8); u=List(); for(i=3,#v, for(j=i,#v,P=v[i]*v[j]; if(P>lim,break); if(!vecsearch(v, P), listput(u, P))))); v \\ Charles R Greathouse IV, Jan 08 2013

Entry revised by N. J. A. Sloane, Jan 06 2013, Jan 08 2013

Definition clarified by Jianing Song, Dec 24 2021

A296241 Finite number of units in a commutative ring; nonnegative even numbers together with products of Mersenne numbers.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 31, 32, 34, 36, 38, 40, 42, 44, 45, 46, 48, 49, 50, 52, 54, 56, 58, 60, 62, 63, 64, 66, 68, 70, 72, 74, 76, 78, 80, 81, 82, 84, 86, 88, 90, 92, 93, 94, 96, 98, 100, 102, 104, 105, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126

Offset: 1

Jonathan Sondow, Dec 14 2017

nonn

Zero together with orders of finite abelian groups that appear as the group of units in a commutative ring (Chebolu and Lockridge).
Equals A005843 union A282572.
Also the possible number of units in a (commutative or non-commutative) ring, since every odd number that is the number of units of a ring must be in this sequence (Ditor's theorem, stated in the S. Chebolu and K. Lockridge link). - Jianing Song, Dec 24 2021

			The even integers {0, +-2, +-4, ...} form a commutative ring with no (multiplicative) units, so a(1) = 0.

S. Chebolu and K. Lockridge, How Many Units Can a Commutative Ring Have?, Amer. Math. Monthly, 124 (2017), 960-965; arXiv, arXiv:1701.02341 [math.AC], 2017.

Cf. A005843, A282572.

A070932 is closely related.

A295584 Odd numbers that are not a product of Mersenne numbers (A000225).

Original entry on oeis.org

5, 11, 13, 17, 19, 23, 25, 29, 33, 35, 37, 39, 41, 43, 47, 51, 53, 55, 57, 59, 61, 65, 67, 69, 71, 73, 75, 77, 79, 83, 85, 87, 89, 91, 95, 97, 99, 101, 103, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 129, 131, 133, 137, 139, 141, 143, 145, 149, 151, 153

Offset: 1

N. J. A. Sloane, Dec 15 2017

nonn

Numbers m such that no commutative ring has m units.

Robert Israel, Table of n, a(n) for n = 1..10000
S. Chebolu and K. Lockridge, How Many Units Can a Commutative Ring Have?, Amer. Math. Monthly, 124 (2017), 960-965; arXiv, arXiv:1701.02341 [math.AC], 2017.

Odd numbers not in A282572; complement of A296241.

Cf. A000225.

N:= 1000: # to get all terms <= N
P:= {1}:
for k from 2 do
  m:= 2^k-1;
  if m > N then break fi;
  P:= map(p -> seq(p*m^j, j=0..floor(log[m](N/p))), P);
od:
sort(convert({seq(i,i=1..N,2)} minus P, list)); # Robert Israel, Dec 15 2017

nn == 1000;
P = {1};
For[k = 2, True, k++,
   m = 2^k - 1;
   If[m > nn, Break[]
];
P = (Function[p, Table[p m^j, {j, 0, Log[m, nn/p]}]] /@ P) // Flatten];
Range[1, nn, 2] ~Complement~ P (* Jean-François Alcover, Sep 18 2018, after Robert Israel *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

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

A363329 a(n) is the number of divisors of n that are both coreful and infinitary.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

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

A070932 Possible number of units in a finite (commutative or non-commutative) ring.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A296241 Finite number of units in a commutative ring; nonnegative even numbers together with products of Mersenne numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A295584 Odd numbers that are not a product of Mersenne numbers (A000225).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

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