A003010 -id:A003010 - cp's OEIS frontend

A177874 The number of decimal digits in the Lucas-Lehmer number A003010(n).

1, 2, 3, 5, 10, 19, 37, 74, 147, 293, 586, 1172, 2343, 4686, 9371, 18742, 37484, 74967, 149933, 299866, 599731, 1199461, 2398922, 4797844, 9595688, 19191376, 38382751, 76765501, 153531001, 307062002, 614124003, 1228248006, 2456496012, 4912992024, 9825984047

Offset: 0

G. L. Honaker, Jr., Dec 13 2010

Cf. A003010.

T:=[ n eq 1 select 4 else Self(n-1)^2-2: n in [1..24] ]; [ #Intseq(T[n]): n in [1..#T] ];

a=Sqrt[6]; Table[a=a^2-2; Length[IntegerDigits[a]], {n,0,20}]
IntegerLength/@NestList[#^2-2&,4,33] (* Harvey P. Dale, Jan 19 2018 *)

a(n) = A055642(A003010(n)).

a(21)-a(24) from Klaus Brockhaus, Dec 13 2010
a(25)-a(32) from D. S. McNeil, Dec 13 2010
a(33)-a(34) from Jinyuan Wang, Jan 15 2025

A177879 The smallest odd prime factor of the Lucas-Lehmer number A003010(n).

Original entry on oeis.org

7, 97, 31, 708158977, 127, 22783, 113210499946729046527, 12289, 1049179854847, 22427452848394140276947044397991663611794141183, 8191, 29687809

Offset: 1

G. L. Honaker, Jr., Dec 13 2010

Does this sequence include all of the Mersenne primes greater than 3?
a(8)=12289; a(11)=8191, a(15)=131071.
Also the least prime factor of A002812(n). - Michel Marcus, Dec 16 2022
a(p-2) = 2^p-1 for all odd Mersenne exponents p in A000043? - Thomas Ordowski, Aug 12 2018

			A003010(3)=37634 and its smallest odd prime factor is 31.

Chris Caldwell, Mersenne primes

Cf. A000040, A003010, A000668, A002812.

More terms, using factordb, from Michel Marcus and Hugo Pfoertner, Dec 16 2022

A177875 The number of decimal digits in Lucas-Lehmer numbers A003010(k-2) divisible by 2^k-1.

Original entry on oeis.org

2, 5, 19, 1172, 18742, 74967, 307062002, 329705313529178423, 88504596182827979077122168, 23200948861751257747193113585514, 24327958153659686843520766271043070385

Offset: 1

G. L. Honaker, Jr., Dec 13 2010

The values of k are 3, 5, 7, 13, ..., the odd Mersenne prime exponents A000043.
A003010(n) has A177874(n) decimal digits.
The larger terms can be computed by combining techniques from both integer and real arithmetic. The values of k for which A003010(k-2) is divisible by 2^k-1 are found from computing A003010 recursively mod 2^k-1. Unfortunately this gives no information on the number of decimal digits of A003010(k-2), i.e. A177874(k-2). To determine this, we use arbitrary-precision interval arithmetic -- in which we quickly lose information about divisibility -- to place bounds on the size of A003010(k-2) and find d such that 10^(d-1) <= A003010(k-2) < 10^d. - D. S. McNeil, Dec 14 2010

			k = 3: Lucas-Lehmer number A003010(1) = 14 is divisible by 2^3-1 = 7 and has 2 decimal digits. Hence A177874(1) = 2 is in the sequence.
k = 7: Lucas-Lehmer number A003010(5) = 2005956546822746114 is divisible by 2^7-1 = 127 and has 19 decimal digits. Hence A177874(5) = 19 is in the sequence.

Cf. A003010, A177874, A000043.

T:=[ n eq 1 select 4 else Self(n-1)^2-2: n in [1..24] ]; a003010:=func< n | T[n+1] >; a177874:=func< n | #Intseq(a003010(n)) >; [ a177874(n): n in [0..#T-1] | a003010(n) mod (2^(n+2)-1) eq 0];

a=Sqrt[6]; Reap[Do[a=a^2-2; If[Mod[a, 2^(n+1)-1]==0, Sow[Length[IntegerDigits[a]]]], {n, 26}]][[2, 1]]

a(7)-a(11) from D. S. McNeil, Dec 13 2010

A177876 a(n) is the number of distinct prime factors in Lucas-Lehmer numbers A003010(k-2)/(2^k-1), where k = A000043(n+1).

Original entry on oeis.org

2, 3, 3, 4

Offset: 1

G. L. Honaker, Jr., Dec 13 2010

a(5) of this sequence will require the factorization of A003010(15), an 18742-digit integer divisible by 2^17-1.

			a(1)=2 because A003010(1)=14, contains exactly 2 distinct prime factors;
a(2)=3 because A003010(3)=37634, contains exactly 3 distinct prime factors;
a(3)=3 because A003010(5)=2005956546822746114, contains exactly 3 distinct prime factors;
a(4)=4 because A003010(11)=the associated 1172-digit Lucas-Lehmer number, contains exactly 4 distinct prime factors.

Cf. A000040, A000668, A003010, A177874, A177875, A177879, A177892

Definition corrected by Max Alekseyev, Jul 29 2024

A177892 The number of distinct prime factors in Lucas-Lehmer number A003010(n).

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 6, 3, 5, 5

Offset: 0

G. L. Honaker, Jr., Dec 14 2010

a(10)>2: results from www.factordb.com. - R. J. Mathar, Dec 15 2010

a(11)=4, factorization added to www.factordb.com. - Sean A. Irvine, Mar 25 2011

Dario Alejandro Alpern, Factorization using the Elliptic Curve Method (along with sigma_0, sigma_1 and phi functions)

Cf. A001221, A003010, A177876.

Table[PrimeNu[Ceiling[(2 + Sqrt[3])^(2^n)]], {n,0,5}] (* G. C. Greubel, May 16 2017 *)

a=4; until(a=a^2-2, print1(omega(a)", "))  \\ M. F. Hasler, Dec 14 2010

a(n) = A001221(A003010(n)).

a(9) from Wang Runsen, Oct 26 2020

A227616 Number of bits set to 1 in the binary representation of the n-th term of the Lucas-Lehmer sequence (A003010).

Original entry on oeis.org

1, 3, 3, 5, 12, 30, 58, 128, 237, 476, 975, 1956, 3899, 7798, 15534, 31270, 62262, 124635, 248944, 497797, 995730, 1990576, 3983767, 7969049, 15935289, 31870309, 63739461, 127519282, 254994762, 510016513, 1020092276, 2040066241, 4080236749

Offset: 0

Olivier de Mouzon, Jul 17 2013

			For n = 2, A003010(2) = 11000010 (in binary), so a(2) = 3.

Cf. A003010, A227608, A227615.

read("transforms") :
A227616 := proc(n)
    wt(A003010(n)) ;
end proc: # R. J. Mathar, Jul 20 2013

First@ DigitCount[#, 2] & /@ NestList[#^2 - 2 &, 4, 28] (* Michael De Vlieger, Apr 04 2016 *)

lista(nn) = {a = 4; print1(hammingweight(a), ", "); for (n=1, nn, a = a^2-2; print1(hammingweight(a), ", "););} \\ Michel Marcus, Apr 04 2016

a(n) = A000120(A003010(n)).

Terms from a(19) on from Michel Marcus, Apr 04 2016

A317977 a(n) = A003010(n-2) mod (2^n - 1).

Original entry on oeis.org

1, 0, 14, 0, 23, 0, 149, 205, 95, 1736, 779, 0, 4193, 20400, 25439, 0, 221468, 0, 1036394, 840107, 1751891, 6107895, 5639594, 8772568, 66322529, 60611448, 99083624, 458738443, 989927528, 0, 3038229779, 5238898821, 393215, 11960838285, 27264928469, 117093979072, 274827575393, 276971366821

Offset: 2

Thomas Ordowski, Aug 12 2018

nonn

For n > 2, the Mersenne number 2^n - 1 is a prime if and only if a(n) = 0. See comments in A003010.

Chai Wah Wu, Table of n, a(n) for n = 2..3322

Cf. A000043, A000225, A000668, A003010, A095847.

a(n) = {my(pow = 2^n-1, res = Mod(4, pow)); for(i = 1, n-2, res = res^2 - 2); lift(res)}
first(n) = vector(n, i, a(i+1)) \\ David A. Corneth, Aug 12 2018

def A317977(n):
    m = 2**n-1
    c = 4 % m
    for _ in range(n-2):
        c = (c**2-2) % m
    return c # Chai Wah Wu, Oct 08 2018

a(prime(n)) = A095847(n).

More terms from Michel Marcus and David A. Corneth, Aug 12 2018

A375090 Omit the trailing 4 from the terms of the Lucas-Lehmer sequence A003010.

Original entry on oeis.org

0, 1, 19, 3763, 141631795, 200595654682274611, 402386166774103602282563565610210099, 1619146272111567178177755907012051366495859012549915851432930874097578803

Offset: 0

Stefano Spezia, Jul 29 2024

The next term a(8) has 146 digits.
Proposition: A003010(n) has only a trailing 4.
Proof: the case n = 0 is trivial since a(0) = 4 has only a digit. For n > 0, we need to prove that the terms have at least a trailing 4 and that this is unique. A003010(n) == 4 (mod 10) because A003010(0) = 4 and 4^2 - 2 = 14 == 4 (mod 10). To prove that this is unique, we prove that the tenth digit of A003010(n) is never equal to 4 for n > 0, or equivalently, that it is odd. Considering that (10*h + 4)^2 = 100*h^2 + 80*h + 16 and 80*h + 16 has the tenth digit of the form 8*k + 1 mod 10, it follows that the tenth digit of A003010(n-1)^2 is odd, and therefore, also that of A003010(n-1)^2 - 2 = A003010(n). QED.

Stefano Spezia, Table of n, a(n) for n = 0..10

Cf. A003010, A017077.

A003010[0]=4; A003010[n_]:=A003010[n-1]^2-2; Array[A003010, 9, 0]; a[n_]:=(A003010[n]-4)/10; Array[a,8,0]

a(n) = (A003010(n) - 4)/10.

a(n) = 10*a(n-1)^2 + 8*a(n-1) + 1 for n > 0.

A248755 a(n) is the number of iterations for the Lucas-Lehmer sequence A003010 (mod p_n) to enter a loop, where p_n is the n-th prime number A000040(n).

Original entry on oeis.org

2, 2, 1, 4, 3, 3, 4, 2, 5, 4, 6, 5, 4, 5, 11, 3, 15, 6, 5, 3, 5, 6, 11, 13, 5, 4, 9, 27, 11, 10, 8, 7, 23, 13, 20, 12, 14, 10, 41, 28, 12, 4, 36, 4, 15, 13, 27, 8, 15, 11, 13, 24, 5, 51, 8, 65, 36, 8, 13, 47, 36, 42, 31, 20, 13, 52, 42, 6, 87, 16, 30, 89, 15, 7, 36, 95, 6, 17, 34, 10

Offset: 1

Robert G. Wilson v, Oct 13 2014

The Lucas-Lehmer sequence is used to test for Mersenne primes (A001348), but this is irrelevant for this sequence.

			a(4) is 4 because p_4 = 7, and the sequence A003010 (mod 7) becomes -> 4, 0, 5, 2, 2, 2, 2, 2, 2, .... The term 2 which is the first term of an infinite loop is at position 4.

GIMPS, Great Internet Mersenne Prime Search
Eric W. Weisstein's World of Mathematics, Lucas-Lehmer Test
Wikipedia, Lucas-Lehmer primality test

Cf. A003010, A001348, A095847, A000043.

f[n_] := -1 + Length@ NestWhileList[ Mod[#^2 - 2, Prime[n]] &, 4, UnsameQ[##] &, {2, Infinity}]; Array[f, 80]

A057889 Bijective bit-reverse of n: keep the trailing zeros in the binary expansion of n fixed, but reverse all the digits up to that point.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 12, 11, 14, 15, 16, 17, 18, 25, 20, 21, 26, 29, 24, 19, 22, 27, 28, 23, 30, 31, 32, 33, 34, 49, 36, 41, 50, 57, 40, 37, 42, 53, 52, 45, 58, 61, 48, 35, 38, 51, 44, 43, 54, 59, 56, 39, 46, 55, 60, 47, 62, 63, 64, 65, 66, 97, 68, 81, 98, 113

Offset: 0

Marc LeBrun, Sep 25 2000

The original name was "Bit-reverse of n, including as many leading as trailing zeros." - Antti Karttunen, Dec 25 2024
A permutation of integers consisting only of fixed points and pairs. a(n)=n when n is a binary palindrome (including as many leading as trailing zeros), otherwise a(n)=A003010(n) (i.e. n has no axis of symmetry). A057890 gives the palindromes (fixed points, akin to A006995) while A057891 gives the "antidromes" (pairs). See also A280505.
This is multiplicative in domain GF(2)[X], i.e. with carryless binary arithmetic. A193231 is another such permutation of natural numbers. - Antti Karttunen, Dec 25 2024

			a(6)=6 because 0110 is a palindrome, but a(11)=13 because 1011 reverses into 1101.

N. J. A. Sloane, Table of n, a(n) for n = 0..16384, May 30 2016 [First 8192 terms from _Ivan Neretin_, Jul 09 2015]
Index entries for sequences related to binary expansion of n
Index entries for sequences related to polynomials in ring GF(2)[X]
Index entries for sequences that are permutations of the natural numbers

Cf. A030101, A000265, A006519, A006995, A057890, A057891, A280505, A280508, A331166 [= min(n,a(n))], A366378 [k for which a(k) = k (mod 3)], A369044 [= A014963(a(n))].
Similar permutations for other bases: A263273 (base-3), A264994 (base-4), A264995 (base-5), A264979  (base-9).
Other related (binary) permutations: A056539, A193231.
Compositions of this permutation with other binary (or other base-related) permutations: A264965, A264966, A265329, A265369, A379471, A379472.
Compositions with permutations involving prime factorization: A245450, A245453, A266402, A266404, A293448, A366275, A366276.
Other derived permutations: A246200 [= a(3*n)/3], A266351, A302027, A302028, A345201, A356331, A356332, A356759, A366389.
See also A235027 (which is not a permutation).

Table[FromDigits[Reverse[IntegerDigits[n, 2]], 2]*2^IntegerExponent[n, 2], {n, 71}] (* Ivan Neretin, Jul 09 2015 *)

A030101(n) = if(n<1,0,subst(Polrev(binary(n)),x,2));
A057889(n) = if(!n,n,A030101(n/(2^valuation(n,2))) * (2^valuation(n, 2))); \\ Antti Karttunen, Dec 25 2024

def a(n):
    x = bin(n)[2:]
    y = x[::-1]
    return int(str(int(y))+(len(x) - len(str(int(y))))*'0', 2)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 11 2017

def A057889(n): return int(bin(n>>(m:=(~n&n-1).bit_length()))[-1:1:-1],2)<Chai Wah Wu, Dec 25 2024

a(n) = A030101(A000265(n)) * A006519(n), with a(0)=0.

Clarified the name with May 30 2016 comment from N. J. A. Sloane, and moved the old name to the comments - Antti Karttunen, Dec 25 2024

cp's OEIS Frontend

A177874 The number of decimal digits in the Lucas-Lehmer number A003010(n).

Views

Author

Keywords

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A177879 The smallest odd prime factor of the Lucas-Lehmer number A003010(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A177875 The number of decimal digits in Lucas-Lehmer numbers A003010(k-2) divisible by 2^k-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Magma

Mathematica

Extensions

A177876 a(n) is the number of distinct prime factors in Lucas-Lehmer numbers A003010(k-2)/(2^k-1), where k = A000043(n+1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A177892 The number of distinct prime factors in Lucas-Lehmer number A003010(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A227616 Number of bits set to 1 in the binary representation of the n-th term of the Lucas-Lehmer sequence (A003010).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A317977 a(n) = A003010(n-2) mod (2^n - 1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A375090 Omit the trailing 4 from the terms of the Lucas-Lehmer sequence A003010.

Views

Author

Keywords

Comments