A000225 -id:A000225 - cp's OEIS frontend

A064078 Zsigmondy numbers for a = 2, b = 1: Zs(n, 2, 1) is the greatest divisor of 2^n - 1 (A000225) that is coprime to 2^m - 1 for all positive integers m < n.

1, 3, 7, 5, 31, 1, 127, 17, 73, 11, 2047, 13, 8191, 43, 151, 257, 131071, 19, 524287, 41, 337, 683, 8388607, 241, 1082401, 2731, 262657, 3277, 536870911, 331, 2147483647, 65537, 599479, 43691, 8727391, 4033, 137438953471, 174763, 9588151, 61681

Offset: 1

Jens Voß, Sep 04 2001

nonn

By Zsigmondy's theorem, the n-th Zsigmondy number for bases a and b is not 1 except in the three cases (1) a = 2, b = 1, n = 1, (2) a = 2, b = 1, n = 6, (3) n = 2 and a + b is a power of 2.
Composite terms are the maximal overpseudoprimes to base 2 (see A141232) for which the multiplicative order of 2 mod a(n) equals n. - Vladimir Shevelev, Aug 26 2008
a(n) = 2^n - 1 if and only if either n = 1 or n is prime. - Vladimir Shevelev, Sep 30 2008
a(n) == 1 (mod n), 2^(a(n)-1) == 1 (mod a(n)), A002326((a(n)-1)/2) = n. - Thomas Ordowski, Oct 25 2017
If n is odd, then the prime factors of a(n) are congruent to {1,7} mod 8, that is, they have 2 has a quadratic residue, and are congruent to 1 mod 2n. If n is divisible by 8, then the prime factors of a(n) are congruent to 1 mod 16. - Jianing Song, Apr 13 2019
Named after the Austrian mathematician Karl Zsigmondy (1867-1925). - Amiram Eldar, Jun 20 2021

			a(4) = 5 because 2^4 - 1 = 15 and its divisors being 1, 3, 5, 15, only 1 and 5 are coprime to 2^2 - 1 = 3 and 2^3 - 1 = 7, and 5 is the greater of these.
a(5) = 31 because 2^5 - 1 = 31 is prime.
a(6) = 1 because 2^6 - 1 = 63 and its divisors being 1, 3, 7, 9, 21, 63, only 1 is coprime to all of 3, 7, 15, 31.

T. D. Noe, Table of n, a(n) for n=1..1000
Wikipedia, Zsigmondy's theorem.
Karl Zsigmondy, Zur Theorie der Potenzreste, Monatshefte für Mathematik, Vol. 3 (1892), pp. 265-284.

Cf. A000225, A064079, A064080, A064081, A064082, A064083.

Cf. A019320, A063982.

Table[Cyclotomic[n, 2]/GCD[n, Cyclotomic[n, 2]], {n, 40}] (* Alonso del Arte, Mar 14 2013 *)

a(n) = my(m = polcyclo(n, 2)); m/gcd(m,n); \\ Michel Marcus, Mar 07 2015

Denominator of Sum_{d|n} d*moebius(n/d)/(2^d-1). - Vladeta Jovovic, Apr 02 2004
a(n) = A019320(n)/gcd(n, A019320(n)). - T. D. Noe, Apr 13 2010
a(n) = A019320(n)/(A019320(n) mod n) for n > 1. - Thomas Ordowski, Oct 24 2017

More terms from Vladeta Jovovic, Apr 02 2004

Definition corrected by Jerry Metzger, Nov 04 2009

A255062 Number of steps to reach 0 when starting from (2^n)-1 and iterating the map x -> x - (number of runs in binary representation of x): a(n) = A255072(A000225(n)).

Original entry on oeis.org

0, 1, 2, 4, 7, 12, 21, 37, 66, 119, 216, 394, 722, 1330, 2464, 4590, 8591, 16143, 30435, 57550, 109115, 207389, 395046, 754028, 1441972, 2762765, 5303467, 10200386, 19656529, 37948282, 73384081, 142115377, 275551756, 534790473, 1038702981, 2018626773, 3924923938, 7634733313

Offset: 0

Antti Karttunen, Feb 14 2015

nonn

Also, for n >= 1, the number of steps to reach 0 when starting from 2^n and iterating the map x -> x minus A005811(x), the number of runs in binary representation of x.

One more than A255061.
First differences: A255071 (after the zero term).
Cf. A000079, A000225, A005811, A255071, A255072.
Analogous sequences: A213710 (A218600), A219665.

(define (A255062 n) (A255072 (A000225 n)))
(define (A255062 n) (if (<= n 1) n (+ (A255062 (- n 1)) (A255071 (- n 1))))) ;; Assuming that A255071 has been already computed, with e.g. the PARI-program given in that entry.

a(n) = A255072(A000225(n)).
a(0) = 0, a(1) = 1; for n > 1, a(n) = a(n-1) + A255071(n-1).
Other identities. For all n >= 1:
a(n) = A255072(A000079(n)). [See the Comments section.]
a(n) = 1 + A255061(n).

A246674 Run Length Transform of A000225.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 3, 7, 1, 1, 1, 3, 3, 3, 7, 15, 1, 1, 1, 3, 1, 1, 3, 7, 3, 3, 3, 9, 7, 7, 15, 31, 1, 1, 1, 3, 1, 1, 3, 7, 1, 1, 1, 3, 3, 3, 7, 15, 3, 3, 3, 9, 3, 3, 9, 21, 7, 7, 7, 21, 15, 15, 31, 63, 1, 1, 1, 3, 1, 1, 3, 7, 1, 1, 1, 3, 3, 3, 7, 15, 1, 1, 1, 3, 1, 1, 3, 7, 3, 3, 3, 9, 7, 7, 15, 31, 3, 3, 3, 9, 3, 3, 9, 21, 3, 3, 3, 9, 9, 9, 21, 45, 7, 7, 7, 21, 7, 7, 21, 49, 15, 15, 15, 45, 31, 31, 63, 127, 1

Offset: 0

Antti Karttunen, Sep 08 2014

a(n) can be also computed by replacing all consecutive runs of zeros in the binary expansion of n with * (multiplication sign), and then performing that multiplication, still in binary, after which the result is converted into decimal. See the example below.

			115 is '1110011' in binary. The run lengths of 1-runs are 2 and 3, thus a(115) = A000225(2) * A000225(3) = ((2^2)-1) * ((2^3)-1) = 3*7 = 21.
The same result can be also obtained more directly, by realizing that '111' and '11' are the binary representations of 7 and 3, and 7*3 = 21.
From _Omar E. Pol_, Feb 15 2015: (Start)
Written as an irregular triangle in which row lengths are the terms of A011782:
1;
1;
1,3;
1,1,3,7;
1,1,1,3,3,3,7,15;
1,1,1,3,1,1,3,7,3,3,3,9,7,7,15,31;
1,1,1,3,1,1,3,7,1,1,1,3,3,3,7,15,3,3,3,9,3,3,9,21,7,7,7,21,15,15,31,63;
...
Right border gives 1 together with the positive terms of A000225.
(End)

Antti Karttunen, Table of n, a(n) for n = 0..8192

Cf. A003714 (gives the positions of ones).
Cf. A000225, A051179.
A001316 is obtained when the same transformation is applied to A000079, the powers of two.
Run Length Transforms of other sequences: A071053, A227349, A246588, A246595, A246596, A246660, A246661, A246685, A247282.

f[n_] := 2^n - 1; Table[Times @@ (f[Length[#]]&) /@ Select[ Split[ IntegerDigits[n, 2]], #[[1]] == 1&], {n, 0, 100}] (* Jean-François Alcover, Jul 11 2017 *)

# uses RLT function in A278159
def A246674(n): return RLT(n,lambda m: 2**m-1) # Chai Wah Wu, Feb 04 2022

For all n >= 0, a(A051179(n)) = A247282(A051179(n)) = A051179(n).

A255047 1 together with the positive terms of A000225.

Original entry on oeis.org

1, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295

Offset: 0

Omar E. Pol, Feb 15 2015

Also, right border of A246674 arranged as an irregular triangle.
Essentially the same as A168604, A126646 and A000225.
Total number of lambda-parking functions induced by all partitions of n. a(0)=1: [], a(1)=1: [1], a(2)=3: [1], [2], [1,1], a(4)=7: [1], [2], [3], [1,1], [1,2], [2,1], [1,1,1]. - Alois P. Heinz, Dec 04 2015
Also, the decimal representation of the diagonal from the origin to the corner of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 645", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - Robert Price, Jul 19 2017
Also number of multiset partitions of {1,1} U [n] into exactly 2 nonempty parts.  a(2) = 3: 111|2, 11|12, 1|112. - Alois P. Heinz, Aug 18 2017
Also, the number of unlabeled connected P-series (equivalently, connected P-graphs) with n+1 elements. - Salah Uddin Mohammad, Nov 19 2021

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
R. Stanley, Parking Functions, 2011.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Wolfram Research, Wolfram Atlas of Simple Programs
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A000225, A011782, A028310, A246674, A253909, A265007, A265202, A349276.
Row n=1 of A263159.
Column k=2 of A291117.
Cf. A078485.

[1] cat [2^n -1: n in [1..40]]; // G. C. Greubel, Feb 07 2021

CoefficientList[Series[(1 -2*x +2*x^2)/((1-x)*(1-2*x)), {x, 0, 33}], x] (* or *) LinearRecurrence[{3, -2}, {1,1,3}, 40] (* Vincenzo Librandi, Jul 20 2017 *)
Table[2^n -1 +Boole[n==0], {n, 0, 40}] (* G. C. Greubel, Feb 07 2021 *)

def A255047(n): return -1^(-1<Chai Wah Wu, Dec 21 2022

[1]+[2^n -1 for n in (1..40)] # G. C. Greubel, Feb 07 2021

From Alois P. Heinz, Feb 19 2015: (Start)
O.g.f.: (1 -2*x +2*x^2)/((1-x)*(1-2*x)).
E.g.f.: exp(2*x) - exp(x) + 1. (End)
a(n) = A078485(n+1) for n > 2. - Georg Fischer, Oct 22 2018

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

A188130 Primes p such that 6p+1 divides the Mersenne number M(p)=A000225(p).

Original entry on oeis.org

5, 37, 73, 233, 397, 461, 557, 577, 601, 761, 1013, 1321, 1361, 1381, 1453, 1693, 1777, 1993, 2417, 2593, 2621, 2897, 3037, 3181, 3457, 3581, 3593, 4001, 4273, 4441, 4517, 4597, 4801, 4813, 4861, 4933, 5197, 5393, 5557, 5717, 5801, 6173, 6277, 6353, 6373, 6841, 6977, 7573, 7853, 7901, 8353, 8377, 9613, 10321, 10357

Offset: 1

M. F. Hasler, Mar 21 2011

nonn

These primes are such that p=1 (mod 4) and 6p+1 is prime, but there are other primes with these properties (13, 17, ...) not in this sequence.

There are no primes p such that 4p+1 divides M(p), but those for which 2p+1 divides M(p) are the Lucasian primes A002515, and those for which 10p+1 divides M(p) are listed in A188133.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1313 from M. F. Hasler)

Cf. A002515, A188133.

Primes in A038844.

Select[Range[10^4], PrimeQ[#] && PowerMod[2, #, 6# + 1] == 1 &] (* Amiram Eldar, Nov 13 2019 *)

forprime(p=1,1e5,Mod(2,p*6+1)^p-1||print1(p", "))

A136380 Quotient obtained when A036284(n) is considered as a GF(2)[X]-polynomial and it is divided by (x^3 + 1) ^ A000225(n-1).

Original entry on oeis.org

24, 160, 11968, 49657088, 837028380268032, 237269922100748727235760269312, 18811253173629696438994877569412700111469395859003555753984, 118178826602781220665226658680265194908312590801831513776333330179329649495708436476846379030238467286212637486694400

Offset: 1

Antti Karttunen, Dec 29 2007

A. Karttunen, Table of n, a(n) for n = 1..11
A. Karttunen, C program for computing this sequence

a(n) = 4*A136382(n) = 2*A048724(A136384(n)). A136381 shows the same sequence in octal base. Cf. A036284.

A136386 Quotient obtained when A037097(n) is considered as a GF(2)[X]-polynomial and it is divided by (x + 1) ^ A000225(n-1) (= A051179(n-2)).

Original entry on oeis.org

4, 8, 352, 3728, 7269662752, 761166466256046848, 390022035611646394530728097023856870592, 91600670557117582933643002658167825054614175029432880501373395030525438396928, 13417853484388319477475698658536993288839029124735549539652836318808118017743106800015257954250357092148394821846783842030516713870361254572407216621548672

Offset: 3

Antti Karttunen, Dec 29 2007

A. Karttunen, Table of n, a(n) for n = 3..13
A. Karttunen, C program for computing this sequence

A136387 shows the same sequence in binary base. Cf. A037096, A037097, A136380, A136382, A136384.

A256258 Triangle read by rows in which the row lengths are the terms of A011782 and row n lists the terms of A016969 except for the right border which gives the positive terms of A000225.

Original entry on oeis.org

1, 3, 5, 7, 5, 11, 17, 15, 5, 11, 17, 23, 29, 35, 41, 31, 5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 83, 89, 63, 5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 83, 89, 95, 101, 107, 113, 119, 125, 131, 137, 143, 149, 155, 161, 167, 173, 179, 185, 127, 5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 83, 89, 95, 101, 107, 113, 119, 125, 131, 137

Offset: 1

Omar E. Pol, Apr 04 2015

Row sums give A002001.
The sum of all terms of first n rows gives A000302(n-1).
The rows of triangle A256263 converge to this sequence.
Rows converge to A016969.
First 11 terms agree with A151548.

			Written as an irregular triangle in which the row lengths are the terms of A011782, the sequence begins:
1;
3;
5,7;
5,11,17,15;
5,11,17,23,29,35,41,31;
5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,63;
5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95,101,107,113,119,125,131,137,143,149,155,161,167,173,179,185,127;
...
Illustration of initial terms in the fourth quadrant of the square grid:
------------------------------------------------------------------------
n   a(n)             Compact diagram
------------------------------------------------------------------------
.            _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1    1      |_| | | |_ _  | |_ _ _ _ _ _  | |
2    3      |_ _| | |_  | | |_ _ _ _ _  | | |
3    5      |_ _ _| | | | | |_ _ _ _  | | | |
4    7      |_ _ _ _| | | | |_ _ _  | | | | |
5    5      | | |_ _ _| | | |_ _  | | | | | |
6   11      | |_ _ _ _ _| | |_  | | | | | | |
7   17      |_ _ _ _ _ _ _| | | | | | | | | |
8   15      |_ _ _ _ _ _ _ _| | | | | | | | |
9    5      | | | | | | |_ _ _| | | | | | | |
10  11      | | | | | |_ _ _ _ _| | | | | | |
11  17      | | | | |_ _ _ _ _ _ _| | | | | |
12  23      | | | |_ _ _ _ _ _ _ _ _| | | | |
13  29      | | |_ _ _ _ _ _ _ _ _ _ _| | | |
14  35      | |_ _ _ _ _ _ _ _ _ _ _ _ _| | |
15  41      |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _| |
16  31      |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
.
a(n) is also the number of cells in the n-th region of the diagram.
It appears that A241717 can be represented by a similar diagram.

Ivan Neretin, Table of n, a(n) for n = 1..8192

Cf. A000225, A000302, A002001, A011782, A016969, A141548, A241717, A256260, A256261, A256263, A256264.

Nest[Join[#, Range[Length[#] - 1]*6 - 1, {2 #[[-1]] + 1}] &, {1}, 7] (* Ivan Neretin, Feb 14 2017 *)

A293447 Fully additive with a(p^e) = e * A000225(PrimePi(p)), where PrimePi(n) = A000720(n) and A000225(n) = (2^n)-1.

Original entry on oeis.org

0, 1, 3, 2, 7, 4, 15, 3, 6, 8, 31, 5, 63, 16, 10, 4, 127, 7, 255, 9, 18, 32, 511, 6, 14, 64, 9, 17, 1023, 11, 2047, 5, 34, 128, 22, 8, 4095, 256, 66, 10, 8191, 19, 16383, 33, 13, 512, 32767, 7, 30, 15, 130, 65, 65535, 10, 38, 18, 258, 1024, 131071, 12, 262143, 2048, 21, 6, 70, 35, 524287, 129, 514, 23, 1048575, 9, 2097151, 4096, 17, 257, 46, 67, 4194303, 11, 12

Offset: 1

Antti Karttunen, Nov 09 2017

nonn

Original, equal definition: totally additive with a(p^e) = e * A005187(2^(PrimePi(p)-1)), where PrimePi(n) = A000720(n).

Antti Karttunen, Table of n, a(n) for n = 1..8192
Index entries for sequences computed from indices in prime factorization

Cf. A000225, A000720, A003557, A005187, A087207.

Cf. also A046645, A048675, A293442, A331591, A331740.

A005187(n) = { my(s=n); while(n>>=1, s+=n); s; }; \\ This function from Charles R Greathouse IV
A293447(n) = { my(f = factor(n)); sum(k=1, #f~, f[k, 2] * A005187(2^(primepi(f[k, 1])-1))); }

(define (A293447 n) (cond ((= 1 n) 0) (else (+ (A005187 (A087207 n)) (A293447 (A003557 n))))))
;; Alternatively:
(define (A293447 n) (if (= 1 n) 0 (+ (A005187 (A000079 (+ -1 (A061395 n)))) (A293447 (/ n (A006530 n))))))

Totally additive with a(p^e) = e * A005187(2^(PrimePi(p)-1)), where PrimePi(n) = A000720(n).
a(1) = 0, and for n > 1, a(n) = A005187(A087207(n)) + a(A003557(n)).
Other identities:
For all n >= 1, a(A293442(n)) = A046645(n).
For all n >= 2 and all k >= 0, a(n^k) = k*a(n).
For all n >= 1, a(n) >= A048675(n) >= A331740(n) >= A331591(n).

Definition simplified by Antti Karttunen, Feb 05 2020

cp's OEIS Frontend

A064078 Zsigmondy numbers for a = 2, b = 1: Zs(n, 2, 1) is the greatest divisor of 2^n - 1 (A000225) that is coprime to 2^m - 1 for all positive integers m < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A255062 Number of steps to reach 0 when starting from (2^n)-1 and iterating the map x -> x - (number of runs in binary representation of x): a(n) = A255072(A000225(n)).

Views

Author

Keywords

Comments

Crossrefs

Programs

Scheme

Formula

A246674 Run Length Transform of A000225.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A255047 1 together with the positive terms of A000225.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

Python

Sage

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

A188130 Primes p such that 6p+1 divides the Mersenne number M(p)=A000225(p).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A136380 Quotient obtained when A036284(n) is considered as a GF(2)[X]-polynomial and it is divided by (x^3 + 1) ^ A000225(n-1).

Views

Author

Keywords

Links

Crossrefs

A136386 Quotient obtained when A037097(n) is considered as a GF(2)[X]-polynomial and it is divided by (x + 1) ^ A000225(n-1) (= A051179(n-2)).

Views